pta 编程题8 Tree Traversals Again

其它pta数据结构编程题请参见：pta

这次的作业考察的是树的遍历。

题目的输入通过栈的pop给出了树的中序遍历的顺序。根据push和pop的顺序构造树的方法为：定义一个变量father来确定父节点，如果父节点还没有pop，那么push操作就构造父节点的左子树，否则构造父节点的右子树；定义一个栈用来确定pop操作弹出的节点，将father赋值为pop的节点，并将此节点的flag值（用来标记已经pop过）标为1。

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 using namespace std;
 5 
 6 struct Stack
 7 {
 8     int data[31];
 9     int top = -1;
10 };
11 
12 struct Node
13 {
14     int left;
15     int right;
16     int flag;//has poped
17 }tree[31];
18 
19 Node initNode();
20 void push(Stack &s, int i);
21 int pop(Stack &s);
22 void postOrder(int i, vector<int> &v);
23 
24 int main()
25 {
26     int num, t, i;
27     int root, father = -1;
28     cin >> num;
29     string s;
30     Stack stack;
31     for (i = 0; i < 2 * num; i++)
32     {
33         cin >> s;
34         if (s == "Push")
35         {
36             cin >> t;
37             push(stack, t);
38             if (i == 0) root = t;
39             else if (tree[father].flag == 0)
40                 tree[father].left = t;
41             else 
42                 tree[father].right = t;//父节点已经pop过只能向右节点push
43             tree[t] = initNode();
44             father = t;
45         }
46         else
47         {
48             father = pop(stack);
49             tree[father].flag = 1;
50         }
51     }
52     vector<int> v;
53     postOrder(root, v);
54     for (int i = 0; i < v.size(); i++)
55     {
56         if (i) cout << " ";
57         cout << v[i];
58     }
59     return 0;
60 }
61 
62 Node initNode()
63 {
64     Node node;
65     node.left = -1;
66     node.right = -1;
67     node.flag = 0;
68     return node;
69 }
70 
71 void push(Stack &s, int i)
72 {
73     s.data[++s.top] = i;
74 }
75 
76 int pop(Stack &s)
77 {
78     return s.data[s.top--];
79 }
80 
81 void postOrder(int i, vector<int> &v)
82 {
83     if (tree[i].left != -1) postOrder(tree[i].left, v);
84     if (tree[i].right != -1) postOrder(tree[i].right, v);
85     v.push_back(i);
86 }