首页 / 软件开发 / 数据结构与算法 / UVa 11234 Expressions：二叉树 层次遍历 广搜

UVa 11234 Expressions：二叉树 层次遍历 广搜2014-10-06 csdn博客 shuangde800题目链接：

题目类型： 数据结构， 二叉树

题目大意：

一般情况下，都是中缀操作符， 如x+y。然后题目给出了一种后缀操作符的形式， 变成 x y +。 进行后缀操作可以用栈模拟，使用push,pop， 过程和经典的“括号匹配”差不多。 然后要求我们转换成队列的方式，用队列的push和pop（队列的和栈的区别）.

解体思路：

一开始没思路， 后来觉得听说是要建树。 这题也是我写的第一道二叉树题。

题目的最关键部分是进行二叉树建树，  以及层次遍历逆序输出，还有利用栈的“括号匹配”思想。 二叉树的基本结构是，父结点都是操作符，子节点都是数字。 对于给出的序列， 从左到右遍历，遇到代表数字的小写则建立一个无儿子的树，然后把根结点指针入栈， 遇到代表操作符的大写字母，则从栈中弹出两个根结点，然后建立一个以大写字母为根，弹出的两个操作数为左右儿子的树，再把这个新树的根结点指针压入栈。如此循环下去。 最后，在栈顶的那个指针就是最后建成的树的根结点。  然后对这颗树进行层次遍历把字母取出来，最后逆序输出即可。

样例输入：

2
xyPzwIM
abcABdefgCDEF

样例输出：

wzyxIPM
gfCecbDdAaEBF

代码：

1. 数组版

10278049  11234  Expressions  Accepted  C++  1.512  2012-07-01 12:59:01

#include<iostream>#include<cstdio>#include<cctype>#include<cstring>#include<stack>#include<queue>using namespace std;class Node{public:char data;int left;int right;};stack<int>st;queue<int>qu;Node arr[10005];char str[10005];int result[10005], resultIndex;// 进行广搜层次遍历void bfs（int root）{while（！qu.empty（）） qu.pop（）;qu.push（root）;result[resultIndex++]=arr[root].data;while（！qu.empty（））{int t = qu.front（）;qu.pop（）;if（arr[t].left ！= -1）{result[resultIndex++] = arr[arr[t].left].data;qu.push（arr[t].left）;}if（arr[t].right ！= -1）{result[resultIndex++] = arr[arr[t].right].data;qu.push（arr[t].right）;}}}void Solve（）{while（！st.empty（）） st.pop（）;for（int i=0; i<strlen（str）; ++i）{if（islower（str[i]））{st.push（i）;arr[i].data= str[i];arr[i].left= -1;arr[i].right = -1;}else{int right = st.top（）;st.pop（）;int left= st.top（）;st.pop（）;arr[i].data = str[i];arr[i].left = left;arr[i].right = right;st.push（i）; }}// 按层次遍历，把字母存在一个栈上（为了逆序输出），然后输出 resultIndex = 0;bfs（st.top（））; // 按广搜结果的逆序输出for（int i=resultIndex-1; i>=0; --i）printf（"%c",result[i]）;printf（"
"）;}int main（）{freopen（"input.txt","r",stdin）;int T;scanf（"%d",&T）;while（T--）{scanf（"%s",str）;Solve（）;}return 0;}

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45534.htm

2. 指针动态内存分配版

#include<iostream>#include<cstdio>#include<cctype>#include<cstring>#include<stack>#include<queue>using namespace std;class Node{public:char data;Node* left;Node* right;};stack<Node*>st;queue<Node*>qu;char str[10005];int result[10005], resultIndex;// 进行广搜层次遍历void bfs（Node* root）{while（！qu.empty（）） qu.pop（）;qu.push（root）;result[resultIndex++]=root->data;while（！qu.empty（））{Node* t = qu.front（）;qu.pop（）;if（t->left ！= NULL）{result[resultIndex++] = t->left->data;qu.push（t->left）;}if（t->right ！= NULL）{result[resultIndex++] = t->right->data;qu.push（t->right）;}}}void Solve（）{while（！st.empty（）） st.pop（）;for（int i=0; i<strlen（str）; ++i）{if（islower（str[i]））{Node *temp = new Node;temp->data = str[i];temp->left = NULL;temp->right = NULL;st.push（temp）;}else{Node* right = st.top（）;st.pop（）;Node* left= st.top（）;st.pop（）;Node* parent = new Node;parent->data = str[i];parent->left = left;parent->right = right;st.push（parent）; }}// 按层次遍历，把字母存在一个栈上（为了逆序输出），然后输出 resultIndex = 0;bfs（st.top（））; // 按广搜结果的逆序输出for（int i=resultIndex-1; i>=0; --i）printf（"%c",result[i]）;printf（"
"）;}int main（）{freopen（"input.txt","r",stdin）;int T;scanf（"%d",&T）;while（T--）{scanf（"%s",str）;Solve（）;}return 0;}