前言

在准备考研复习专业课数据结构,所以我在mooc平台上找了浙江大学的数据结构课程重新学习,感觉老师留的课后题都很有趣,所以想记录下自己的学习过程。

二叉树太难了啊,呜呜呜,太难了家人们。

题目:

03-树3 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.

img
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

1
3 4 2 6 5 1

题解

题目大意

​ 题目给出一个出栈入栈序列,可以通过这个序列确定一棵二叉树,要求输出后序遍历的二叉树。

题目分析

​ 这题有两种思路,第一种是根据入栈出栈序列建立一颗二叉树,然后在对二叉树进行后序遍历。第二种则是根据入栈出栈序列,得到先序遍历和中序遍历的序列,然后在根据这两个序列来推后序遍历序列。

​ 我一开始是想用第一种思路解的,但是太菜了,一直解不出。然后就去查答案,查到了第二种解法的思路。本来想自己根据第二种思路自己写出来,但是还是没写出。唉,我太菜了。最后看了陈越姥姥的样例代码,才做出来的。

​ 对了,看了别人的代码,大家都用c++自带的stl来实现简单的数据结构了,因为我还没学stl,只能傻傻的自己实现这些数据结构。下次得好好学学stl了。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<string.h>
struct SqStack{
int data[31];
int top;
}stack;
bool Init_stack(SqStack &s){
s.top = -1;
return true;
}
bool push(SqStack &s,int x){
if(s.top==30)
return false;
s.data[++s.top] = x;
return true;
}
int pop(SqStack &s){
if(s.top==-1)
return -1;
return s.data[s.top--];
}
bool isempty(SqStack s){
if(s.top==-1)
return true;
else
return false;
}
int front[31]={0},mid[31]={0},post[31]={0};
void solve(int prel,int inl,int postl,int n){
if(n==0)
return ;
if(n==1){
post[postl] = front[prel];
return;
}
int i;
post[postl+n-1] = front[prel];
for(i=0;i<n;i++){
if(mid[inl+i]==front[prel])break;
}
int L=i, R=n-i-1;
solve(prel+1, inl, postl, L);
solve(prel+1+L, inl+L+1, postl+L, R);
}

int main() {
int n,node;
Init_stack(stack);
char act[5];
scanf("%d",&n);
int fcount=0,mcount=0;
for(int i=0;i<2*n;i++){
scanf("%s",act);
if(!strcmp(act,"Push")){
scanf("%d",&node);
front[fcount++] = node;
push(stack,node);
}
else{
mid[mcount++] = pop(stack);
}
}
solve(0,0,0,n);
for(int i=0;i<n;i++){
if(i==0)
printf("%d",post[i]);
else
printf(" %d",post[i]);
}
return 0;
}