PTA 树的遍历（玩转二叉树）_7-3 玩转二叉树

PTA 树的遍历（玩转二叉树）

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

二叉树的前序、中序、后序这三种遍历方式，要想通过其中两种遍历方式求出二叉树的形态，则这两种遍历方式之一一定要有中序遍历，因为二叉树是严格区分左右子树的，若没有中序遍历，无法判断子结点在左子树还是在右子树，也就无法判断哪些子结点是空的。
对于后序遍历来说，最一后一个结点一定是根结点（对于前序而言就是第一个为根结点），对于中序来说，根结点的左边的数都是左子树的，右边数都是右子树的。抓住这两种遍历方式的这个特点，就可以推算出树的形态了。
具体的操作就是利用递归的思想来解决这道题目，最简单就是三个结点的情况，A为根结点，B、C分别为左右子树，那么它的前序遍历为A B C，后序遍历为B C A，中序遍历为B A C。在这里我们拿题目的后序和中序来说，我们先找到后序遍历的最后一个元素就是A，那么就可以确定A是根结点了，然后在中序中找到A，A的左边是只有一个B，那么B就是左子树，A的右边右一个C，那么C就是A的右子树。这是一个比较简单的形式，那么我们利用递归的思想，就是把一颗复杂的二叉树不断的细分，一直到最简单的结构。而这个最简单的结构就是只有根结点，没有左右子树。
那么在这道题里面，样例后序遍历的最后一个元素就是4，所以4是这颗二叉树的根结点，然后在中序中找到4这个数，在4的左边就是左子树，4的右边就是右子树。然后再从后序遍历中左子树的2 3 1中的最后一位数是1，那么1就是左子树的根结点，然后在中序中找到1的位置，1，1是第一个数，也就是说1没有左子树，右边是2和3，所以2 3是1的右子树，继续递归细分，在后序中3是最后一个元素，所以3个根结点，3的左边是2，所以2就是3的左子树，而3没有右子树，只剩下2一个结点，最后可以判断到2没有结点。这时候4这个根结点的左子树递归全部完成，一直返回到4这个结点，同理去递归右子树。第一步划分，如下图。不断重复这个步骤，不再画图了。

把这个推理的过程写成代码也有一定的难度，完整代码段如下：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 31 

struct TNode{
    int Data;
    struct TNode *Left;
    struct TNode *Right;
};

struct TNode *PutBinTree(int s1[], int s2[], int k) {
/*s1为存放后序遍历的数组，s2为存放中序遍历的数组，k代表当前结点的左右子树结点的个数和*/ 
    int i, t;
    if(k == 0) { //如果k为0表示左右子树的个数和为0，即当前结点为叶子结点 
        return NULL;  //叶子结点然后空值。 
    }
    struct TNode *BT = (struct TNode *)malloc(sizeof(struct TNode));
    t = s1[k-1];//t取后序的最后一个结点 
    BT->Data = t;//t即为根结点，所以直接存放在根结点的数据区 
    for(i = 0; i < k; i ++) {
        /*遍历中序中t的位置，i充当一个计数器，
        当找到t时，i的值即为根结点左边的个数，
        也就是左子树的结点个数*/ 
        if(s2[i] == t) {  
            break;
        }
    }
    /*s1、s2即数组的首地址，把左子树看成一个新的二叉树，而这颗全新的树的结点个数就为i*/ 
    BT->Left = PutBinTree(s1, s2, i);
    /*s1+i就得到后序遍历第一个右子树结点的地址，
    s2+i+1同理也是找到中序遍历中第一个结点的地址，
    k-i就去掉了左子树的个数，再-1就去掉了根结点的个数*/ 
    BT->Right = PutBinTree(s1+i, s2+i+1, k-i-1);

    return BT;
}

/*层序遍历，非递归方式(用到队列的思想)*/ 
void putBinTree(struct TNode *BT) {
    struct TNode *s[MAXSIZE];
    int t = 0, k = 1;
    s[t] = BT;
    while(t != k) {
        if(!t) {
            printf("%d", s[t]->Data); //第一个数字不加空格 
        }
        else {
            printf(" %d", s[t]->Data); //非第一个前面加空格，这样保证了最后不会有多于的空格 
        }
        if(s[t]->Left) {
            s[k] = s[t]->Left;
            k = (k+1) % MAXSIZE;
        }
        if(s[t]->Right) {
            s[k] = s[t]->Right;
            k = (k+1) % MAXSIZE;
        }
        t = (t+1) % MAXSIZE;
    }
}

int main()
{
    int i, n;
    int s1[MAXSIZE], s2[MAXSIZE];
    scanf("%d", &n);
    for(i = 0; i < n; i ++) {
        scanf("%d", &s1[i]);
    }
    for(i = 0; i < n; i ++) {
        scanf("%d", &s2[i]);
    }
    struct TNode *BT = PutBinTree(s1, s2, n);
    putBinTree(BT);

    return 0;
}
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
72
73
74
75
76
77
78

队列做法如下：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 31

struct TNode {
    int Data;
    struct TNode *Left;
    struct TNode *Right;
};

struct QNode {
    struct TNode *data[MaxSize];
    int Front, Rear;
};

struct QNode *CreatQueue() { //创建队列并初始化
    struct QNode *Q = (struct QNode *)malloc(sizeof(struct QNode));
    Q->Front = 0;
    Q->Rear = 0;
    return Q;
}

void AddQ(struct QNode *Q, struct TNode *BT) { //入队列
    Q->data[Q->Front] = BT;
    Q->Front = (Q->Front+1) % MaxSize;
}

struct TNode *DeleteQ(struct QNode *Q) { //出队列
    struct TNode *BT;
    BT = Q->data[Q->Rear];
    Q->Rear = (Q->Rear+1) % MaxSize;

    return BT;
}

int IsEmptyQ(struct QNode *Q) { //判断队列是否为空
    if(Q->Front == Q->Rear) { //空则返回1
        return 1;
    }
    else {  //否则返回0
        return 0;
    }
}

struct TNode *PutBinTree(int s1[], int s2[], int k) {
/*s1为存放后序遍历的数组，s2为存放中序遍历的数组，k代表当前结点的左右子树结点的个数和*/ 
    int i, t;
    if(k == 0) { //如果k为0表示左右子树的个数和为0，即当前结点为叶子结点 
        return NULL;  //叶子结点然后空值。 
    }
    struct TNode *BT = (struct TNode *)malloc(sizeof(struct TNode));
    t = s1[k-1];//t取后序的最后一个结点 
    BT->Data = t;//t即为根结点，所以直接存放在根结点的数据区 
    for(i = 0; i < k; i ++) {
        /*遍历中序中t的位置，i充当一个计数器，
        当找到t时，i的值即为根结点左边的个数，
        也就是左子树的结点个数*/ 
        if(s2[i] == t) {  
            break;
        }
    }
    /*s1、s2即数组的首地址，把左子树看成一个新的二叉树，而这颗全新的树的结点个数就为i*/ 
    BT->Left = PutBinTree(s1, s2, i);
    /*s1+i就得到后序遍历第一个右子树结点的地址，
    s2+i+1同理也是找到中序遍历中第一个结点的地址，
    k-i就去掉了左子树的个数，再-1就去掉了根结点的个数*/ 
    BT->Right = PutBinTree(s1+i, s2+i+1, k-i-1);

    return BT;
}

void LevelOrderTraversal (struct TNode *BT)
{   
    struct QNode *Q;
    struct TNode *T;
    if ( !BT ) {
        return; /* 若是空树则直接返回 */
    }
    Q = CreatQueue(); /*创建并初始化队列Q*/
    AddQ( Q, BT );
    while ( !IsEmptyQ( Q ) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /*访问取出队列的结点*/
        if ( T->Left ) {
            AddQ( Q, T->Left );
        } 
        if ( T->Right ) {
            AddQ( Q, T->Right );
        }
    }
}

int main()
{
    int i, n;
    int s1[31], s2[31];
    scanf("%d", &n);
    for(i = 0; i < n; i ++) {
        scanf("%d", &s1[i]);
    }
    for(i = 0; i < n; i ++) {
        scanf("%d", &s2[i]);
    }
    struct TNode *BT = PutBinTree(s1, s2, n);
    LevelOrderTraversal(BT);

    return 0;
}
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

“`

下图为样例的二叉树形态：