03-树2. Tree Traversals Again (25)
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 (<=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
Pop
Sample Output:
3 4 2 6 5 1
这题要做的是树的中缀转后缀，一开始思路有问题，没想明白，只过了两组数据，后来静下来好好想发现也不难。
题目中给出了中缀遍历树的过程，根据题目给出的过程用栈模拟建立树，然后后缀输出。
2 #include <stack>
3 using namespace std;
4
5 struct node //树节点
6 {
7 int left;
8 int right;
9 node ()//结点初始化左右儿子为-1，表示左右结点都不存在
10 {
11 left=-1;
12 right=-1;
13 }
14 };
15 node no[50];
16
17 stack<int> s;//用栈模拟题目中给出的建树过程，栈顶元素为正在处理的结点，很方便的把每个结点的左右儿子构造好
18
19 int t;
20 void print(int first)//后缀输出结点
21 {
22 if (first==-1)
23 return;
24 print(no[first].left);
25 print(no[first].right);
26 if (t==0)
27 {
28 t=1;
29 cout <<first;
30 }
31 else
32 cout<<" "<<first;
33 }
34 int main()
35 {
36 int m,n,now,first;//now代表当前处理的结点，first代表树根
37 string str;
38 while (cin>>n)
39 {
40 t=0;
41 while (!s.empty())//第一个肯定是树根
42 s.pop();//入栈
43
44 cin>>str>>m;
45 first=m;
46 s.push(m);
47 now=m;
48 for (int i=1;i<2*n;i++)
49 {
50
51 cin>>str;
52 if (str=="Push")
53 {
54 cin>>m;
55 if (no[now].left==-1)
56 no[now].left=m;
57 else
58 no[now].right=m;
59 now=m;//下一个要处理的结点为m
60 s.push(m);
61 }
62 else
63 {
64 now=s.top();//下一个要处理的结点为s.top
65 s.pop();
66 }
67 }
68 print(first);
69 cout <<endl;
70 }
71 return 0;
72 }