根据遍历序列还原二叉树

淩亂°似流年 2022-04-22 06:30 135阅读 0赞

首先看一道PTA上的题目：

7-1 根据后序和中序遍历输出先序遍历 （25 分）

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

### 输入格式: ###

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

### 输出格式: ###

在一行中输出`Preorder:`以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

### 输入样例: ###

7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7

### 输出样例: ###

Preorder: 4 1 3 2 6 5 7

已知后序遍历和中序遍历，如何求出二叉树呢？我们知道，后序遍历的顺序是“左、右、根”，因此，最后一个“4”必然是树根。在中序序列中找到这个“4”，它将中序序列分成两部分：“123”和“567”。于是我们就知道，这棵树的左子树含有1、2、3三个元素，右子树含有5、6、7三个元素。即：

1 2 3 4 5 6 7

然后，我们看后序序列倒数第二个元素“6”，它必然是树的右子树的根节点。再到中序序列中找到6，它将右子树分成“5”和“7”两个部分，而后序序列倒数第三个元素为7，则7是右子树的右子树的根节点……以此类推，就可以将二叉树还原。

但是，人用这种方法来做题是可以的，用代码却不太容易实现，以下方法更适合代码实现：

首先找到根节点4，它将中序序列分成左（123）右（567）子树，然后，我们对比观察后序序列和中序序列：

2 3 1 5 7 6 4

1 2 3 4 5 6 7

不难发现规律：如果左子树有m个元素，右子树有n个元素，则后序序列中，前m个元素恰好对应左子树，除去这m个元素以及根节点（最后一个元素），剩下的元素恰好与右子树对应。

于是问题就递归转化为：

已知后序序列为 2 3 1，中序序列为1 2 3，求这棵树（即原树的左子树）；

已知后序序列为 5 7 6，中序序列为5 6 7，求这棵树（即原树的右子树）。

同样的，已知前序序列和中序序列也可用类似方法解决。

//头文件包含
    #include<stdlib.h>
    #include<stdio.h>
    #include<malloc.h>
    
    //函数状态码定义
    #define TRUE       1
    #define FALSE      0
    #define OK         1
    #define ERROR      0
    #define OVERFLOW   -1
    #define INFEASIBLE -2
    
    typedef int Status;
    
    //二叉链表存储结构定义
    typedef int TElemType;
    typedef struct BiTNode{
        TElemType data;
        struct BiTNode  *lchild, *rchild; 
    } BiTNode, *BiTree;
    
    BiTree CreateBiTree(int *in,int *post, int n)
    {
        if(n<=0)
            return NULL;
        int *p = in;
        while(p)
        {
            if(*p==*(post+n-1))
                break;
            p++;
        }
        BiTree T = (BiTree)malloc(sizeof(BiTNode));
    
        T->data = *p;
        int len = p-in;
        T->lchild = CreateBiTree(in,post,len);
        T->rchild = CreateBiTree(p+1,post+len,n-len-1);
        return T;
    }
    Status PreOrderTraverse(BiTree T)
    {
        if(!T)
            return OK;
        else 
        {
            printf(" %d",T->data);
            PreOrderTraverse(T->lchild);
            PreOrderTraverse(T->rchild);
        }
        return OK;
    }
    
    int main()
    {
        int in[35],post[35];
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&post[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&in[i]);
        BiTree T;
        T = CreateBiTree(in,post,n);
        printf("Preorder:");
        PreOrderTraverse(T);
        return 0;
    }