Tree Traversals Again

- 日理万妓 2021-09-30 03:04 242阅读 0赞

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

![30][]  
Figure 1

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains a positive integer N (≤) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2 lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

### Output Specification: ###

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

### Sample Input: ###

6
    Push 1
    Push 2
    Push 3
    Pop
    Pop
    Push 4
    Pop
    Pop
    Push 5
    Push 6
    Pop
    Pop

### Sample Output: ###

3 4 2 6 5 1

可以使用堆栈以非递归方式实现顺序二进制树遍历。你的任务是给出这棵树的后序遍历序列。

每个输入文件包含一个测试用例。对于每种情况，第一行包含正整数N（≤ 3 0），它是节点的总数量在树（并且因此节点编号从1到N）。然后接下来是N行，每行描述一种堆栈操作，格式为：“Push X”，其中X是被推入堆栈的节点的索引; 或“Pop”表示从堆栈中弹出一个节点。

对于每个测试用例，在一行中打印相应树的后序遍历序列。保证存在解决方案。所有数字必须用一个空格分隔，并且在行的末尾不能有额外的空格。

先给出大神的思路

对二叉树的中序遍历可以通过使用栈来避免迭代的方法，对于figure1中的6节点树而言，它的栈操作为push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop()。依据这个输入可以生成这个二叉树，要求打印出该树的后序遍历。

解法：

该题要求我们通过中序遍历的栈实现的栈操作来生成二叉树。  
![1592233-20190417013510052-490553216.png][]

如上图，中序遍历的操作流程（其中箭头代表遍历流），我们可以看出：

1.每次push都指向一个新的节点。

2.每次pop都指向一个被抛出的节点。

3.连续的pop-pop或push-push流的方向都相同。

4.连续的push-pop指向同一个叶节点，同时执行方向转弯。（节点3）

5.连续的pop-push经过一个父节点，同时执行方向转弯。（节点2）

6.每个节点只能pop指向一次，push指向一次。（节点4到2直接跳到1）

于是我们就可以通过这些特性来构建二叉树：

1.读入第一次push构建根节点，根节点入栈。

2.读入下一个操作,有两种情况:

（1）push

说明有一个新节点出现，构建一个节点。如果上次操作为push,把该节点设为栈顶的左儿子，节点入栈。如果上次是pop，经过一个父节点，说明应该是生成了父节点的一个儿子，所以将该节点设为上次pop出来的节点的右儿子。

（2）pop

说明正在pop一个节点，不论上次操作是，该次都抛出一个节点。

这是我写的，有点菜

1 #include <iostream>
      2 #include <stack>
      3 #include <string>
      4 #include <algorithm>
      5 #define MaxTree 31
      6 #define Null -1 
      7 using namespace std;
      8 
      9 int P[MaxTree];
     10 int num=1;
     11 int NUM=0;
     12 stack<int> st;
     13 
     14 struct TreeNode
     15 {
     16     int date;
     17     int Left;
     18     int Right; 
     19 }T[MaxTree];
     20 
     21 int BuildTree(struct TreeNode T[])
     22 {
     23     int N,m,p,i;
     24     string str,pre;
     25     int Root;
     26     cin>>N;
     27     for(i=0;i<2*N;i++)
     28     {
     29         cin>>str;
     30         if(str=="Push")
     31         {
     32             cin>>m;
     33             if(i==0)
     34             {
     35                 Root=1;
     36                 T[num].date=m;
     37                 T[num].Left=Null;
     38                 T[num].Right=Null;
     39                 st.push(num);
     40                 pre=str;
     41             }
     42             else if(pre=="Push")
     43             {
     44                 T[num].Left=num+1;
     45                 num++;
     46                 T[num].date=m;
     47                 T[num].Left=Null;
     48                 T[num].Right=Null;
     49                 st.push(num);
     50                 pre=str;
     51             }
     52             else if(pre=="Pop")
     53             {
     54                 T[p].Right=num+1;
     55                 num++;
     56                 T[num].date=m;
     57                 T[num].Left=Null;
     58                 T[num].Right=Null;
     59                 st.push(num);
     60                 pre=str;
     61             }
     62         }
     63         else if(str=="Pop")
     64         {
     65             p=st.top();
     66             st.pop();
     67             pre=str;
     68         }
     69     }
     70     if(N==0)
     71     {
     72         Root=Null;
     73     }
     74     return Root;
     75 }
     76 
     77 
     78 void search(int Tree)
     79 {
     80     if(Tree==Null)
     81         return;
     82     search(T[Tree].Left);
     83     search(T[Tree].Right);
     84     P[NUM++]=T[Tree].date;
     85 }
     86 
     87 
     88 int main()
     89 {
     90     int Tree;
     91     Tree=BuildTree(T);
     92     search(Tree);
     93     int i;
     94     for(i=0;i<NUM;i++)
     95     {
     96         if(i==0)
     97             cout<<P[i];
     98         else 
     99             cout<<' '<<P[i]; 
    100     }
    101     return 0;
    102 }

![1592233-20190417155548037-19125428.png][]

下面是别人用动态链表实现的，值得一看

1 #include <cstdio>
     2 #include <stack>
     3 using namespace std;
     4 
     5 int preorder[35], inorder[35];
     6 int n, preid = 0, inid = 0, cnt = 0;
     7 int get(){
     8     char s[10];
     9     scanf("%s", s);
    10     if (s[1] == 'o') return -1;
    11     int a;
    12     scanf("%d", &a);
    13     return a;
    14 }
    15 void build(int preb, int pree, int inb, int ine){
    16     if (preb > pree) return;
    17     int root = preorder[preb];
    18     int inroot = inb;
    19     while (inorder[inroot] != root) ++inroot;
    20     build(preb+1, preb+inroot-inb, inb, inroot-1);
    21     build(preb+inroot-inb+1, pree, inroot+1, ine);
    22     if (cnt++ != 0) putchar(' ');
    23     printf("%d", root);
    24 }
    25 int main(){
    26     scanf("%d", &n);
    27     stack<int> st;
    28     for (int i = 0; i < n*2; ++i){
    29         int a = get();
    30         if (a != -1){
    31             st.push(a);
    32             preorder[preid++] = a;
    33         }else{
    34             inorder[inid++] = st.top();
    35             st.pop();
    36         }
    37     }
    38     build(0, n-1, 0, n-1);
    39     return 0;
    40 }

1 #include <string>
      2 #include <iostream>
      3 #include <stack>
      4 using namespace std;
      5  
      6 const string PUSH("Push");
      7 const string POP("Pop");
      8  
      9 typedef struct Node
     10 {
     11     int data;
     12     Node* left;
     13     Node* right;
     14     Node(int d):data(d), left(NULL), right(NULL){}
     15 }Node;
     16  
     17 void PostOrderTraverse(Node *root)
     18 {
     19     Node* temp = root;
     20     Node* pre = NULL;
     21     stack<Node*> S;
     22     int flag = 0;
     23  
     24     while(temp || !S.empty())
     25     {
     26         if(temp)
     27         {
     28             S.push(temp);
     29             temp = temp->left;
     30         }
     31         else
     32         {
     33             temp = S.top();
     34             if(temp->right && temp->right != pre)
     35                 temp = temp->right;
     36             else
     37             {
     38                 if(!flag)
     39                 {
     40                     flag = 1;
     41                     cout<< temp->data;
     42                 }
     43                 else
     44                     cout<<" "<<temp->data;
     45                 S.pop();
     46                 pre = temp;
     47                 temp = NULL;
     48             }
     49         }
     50     }
     51     cout<<endl;
     52 }
     53  
     54 int main()
     55 {
     56     int n, data;
     57     string act;
     58     stack<Node*> S;
     59     Node* root = NULL, *pre = NULL;
     60     int l = 1, r = 0;
     61     cin >> n;
     62  
     63     //First, build the tree , root of tree is *root.
     64     for(int i=1; i <= 2*n; i++)
     65     {
     66         Node* temp;
     67         cin >> act;
     68         if(act == PUSH)
     69         {
     70             cin >> data;
     71             temp = new Node(data);
     72             if(i == 1)
     73             {
     74                 root = temp;
     75             }
     76  
     77             S.push(temp);
     78             if(pre)
     79             {
     80                 if(l == 1)
     81                     pre->left = temp;
     82                 else
     83                     pre->right = temp;
     84             }
     85             l = 1;
     86             pre = temp;
     87         }
     88         else if(act == POP)
     89         {
     90             pre = S.top();
     91             S.pop();
     92             l = 0;
     93         }
     94     }
     95  
     96     PostOrderTraverse(root);
     97  
     98     system("pause");
     99     return 0;
    100 }

转载于:https://www.cnblogs.com/jiamian/p/10714354.html

[30]: /images/20210725/2eed295e4b83463b94b2dbb553ff3de4.png
[1592233-20190417013510052-490553216.png]: /images/20210725/ceae878b81f44b0f8d84da3feb023292.png
[1592233-20190417155548037-19125428.png]: /images/20210725/630ec8f175ab4300acc2ef3a5824a60b.png