Tree Traversals Again
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.
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()。依据这个输入可以生成这个二叉树，要求打印出该树的后序遍历。
解法：
该题要求我们通过中序遍历的栈实现的栈操作来生成二叉树。
如上图，中序遍历的操作流程（其中箭头代表遍历流），我们可以看出：
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 }
下面是别人用动态链表实现的，值得一看
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 }