当前位置:   article > 正文

PTA 树的遍历(玩转二叉树)_7-3 玩转二叉树

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

“`

下图为样例的二叉树形态:
这里写图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/681825
推荐阅读
相关标签
  

闽ICP备14008679号