前言

在准备考研复习专业课数据结构，所以我在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;
}