7-2 根据后序和中序遍历输出先序遍历 (25 分)

野性酷女 2023-10-04 16:23 15阅读 0赞

## 7-2 根据后序和中序遍历输出先序遍历 (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

#### 思路： ####

先根据后、中序生成二叉树，再前序遍历二叉树

#### 代码： ####

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct BiNode
    {
        
        int data;
        struct BiNode *Left,*Right;
    }*BiTree;
    
    BiTree createtree(int po[],int io[],int N);
    void preoder(BiTree T);
    
    //根据后、中序生成二叉树
    BiTree createtree(int po[],int io[],int N)
    {
        
        int i=0,item=0;
        BiTree T=(BiTree)malloc(sizeof(struct BiNode));
        if(N==0)
        {
        
            return NULL;
        }
        //先找到根
        item=po[N-1];
        T->data=item;
        i=0;
        //确定根左子树中的节点数（间接得知了根右子树中的节点数）
        while(i<N)
        {
        
            if(io[i]==item)
            {
        
                break;
            }
            i++;
        }
        //建立左子树
        T->Left=createtree(po,io,i);
        //建立右子树
        T->Right=createtree(po+i,io+i+1,N-i-1);
        return T;
    }
    
    //前序遍历二叉树
    void preoder(BiTree T)
    {
        
        if(T)
        {
        
            printf(" %d",T->data);
            preoder(T->Left);
            preoder(T->Right);
        }
    }
    
    int main()
    {
        
        BiTree BT;
        int N=0;
        int posorder[36]={
        0};
        int inorder[36]={
        0};
        scanf("%d",&N);
        int i=0;
        while(i<N)
        {
        
            scanf("%d",&posorder[i]);
            i++;
        }
        i=0;
        while(i<N)
        {
        
            scanf("%d",&inorder[i]);
            i++;
        }
        //创建树
        BT=createtree(posorder,inorder,N);
        //前序遍历二叉树
        printf("Preorder:");
        preoder(BT);
    
        return 0;
    }