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.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N 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 PopSample Output:
3 4 2 6 5 1
1 #include <iostream> 2 #include <string> 3 #include <stack> 4 5 using namespace std; 6 7 struct Node 8 { 9 int value; 10 int left = 0; 11 int right = 0; 12 }; 13 14 Node tree[31]; //we use tree[0] to devote the null pointer 15 int treeroot; 16 17 void PostTraversal(int root) 18 { 19 if (tree[root].value == 0) 20 return; 21 PostTraversal(tree[root].left); 22 PostTraversal(tree[root].right); 23 cout << tree[root].value; 24 if (tree[root].value != treeroot) 25 cout << " "; 26 } 27 28 int main() 29 { 30 int n; 31 cin >> n; 32 stack<int> s; 33 34 string op, lastOp; 35 int value, lastValue, root; 36 cin >> op >> value; //fist operation must be push 37 //construct the tree 38 treeroot = root = value; 39 tree[value].value = value; 40 s.push(value); 41 lastOp = "Push"; 42 lastValue = value; 43 n *= 2; 44 while (--n) 45 { 46 cin >> op; 47 if (op == "Push") //push 48 { 49 cin >> value; 50 tree[value].value = value; 51 s.push(value); 52 if (lastOp == "Push") 53 tree[lastValue].left = value; 54 else 55 tree[lastValue].right = value; 56 lastValue = value; 57 lastOp = "Push"; 58 } 59 else //pop 60 { 61 lastValue = s.top(); 62 s.pop(); 63 lastOp = "Pop"; 64 } 65 } 66 67 PostTraversal(root); 68 }
PAT 1086. Tree Traversals Again (25)
原文：http://www.cnblogs.com/jackwang822/p/4737448.html