本文共 2708 字，大约阅读时间需要 9 分钟。

1181

50.55%

471

89.60%

题目链接：

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

题目大意：

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

解体思路：

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

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

样例输入：

2xyPzwIMabcABdefgCDEF

样例输出：

wzyxIPMgfCecbDdAaEBF

代码：

1. 数组版

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;class Node{public: char data; int left; int right;};stack
         
          st;queue
          
           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
           
            =0; --i) printf("%c",result[i]); printf("\n");}int main(){ freopen("input.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%s",str); Solve(); } return 0;}
           
          
         
        
       
      
     
    
   

2. 指针动态内存分配版

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;class Node{public: char data; Node* left; Node* right;};stack
         
          st;queue
          
           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
           
            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("\n");}int main(){ freopen("input.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%s",str); Solve(); } return 0;}
           
          
         
        
       
      
     
    
   

转载地址：http://luzni.baihongyu.com/