PTA第六章二叉树：根据后序和中序遍历输出前序遍历_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

思路：根据后序和中序遍历，可以得知该二叉树的结构，因为，后序遍历的最后一个元素，一定是根节点，在通过后序遍历求出根节点以后，找出根节点在中序遍历中的位置，该位置前为左子树的中序遍历，该位置后为右子树的中遍历；同时，后序遍历中左子树的遍历与中序遍历左子树的遍历位置是对应的，而后序遍历中右子树的遍历与中序遍历中右子树的遍历位置相差一个元素（即中序遍历多出一个根节点的位置，而后序遍历根节点在最后）。找出左子树和右子树在后序遍历和中序遍历中的位置后，再运用递归的思想，对左右子树进行进行同样的分析。

 	#include <bits/stdc++.h>        
    using namespace std;
    
    typedef struct TNode{//创建一个结点
        int data;
        TNode *lchild;
        TNode *rchild;
    }TNode,*Tree;
    
    //递归创建二叉树，三个形参，第一个是储存后序遍历的数组，第二个是中序遍历的数
    //组，第三个是组数的长度
    Tree Createtree(int *postder,int *order,int n)
    {
        Tree T;
        if(n<=0)
            return NULL;
        T=(TNode*)malloc(sizeof(TNode));
        int mid;
        for(int i=0;i<n;i++)//找到根节点在中序中的位置
        {
            if(order[i]==postder[n-1])
            {
                mid=i;
                break;
            }
        }
        T->data=postder[n-1];
        T->lchild=Createtree(postder,order,mid);//递归创建左子树
        T->rchild=Createtree(postder+mid,order+mid+1,n-mid-1);//递归创建右子树
        return T;
    }
    
    int flag=0;
    void preprint(Tree T)//前序遍历的递归方法
    {
        if(!T)
            return;
        if(!flag)
        {
            printf("%d",T->data);
            flag=1;
        }
        else
            printf(" %d",T->data);
        preprint(T->lchild);
        preprint(T->rchild);
    }
    
    int main()
    {
        int n;
        Tree T;
        scanf("%d",&n);
        int postder[n];
        int order[n];
        for(int i=0;i<n;i++)
        {
            cin>>postder[i];
        }
        for(int i=0;i<n;i++)
        {
            cin>>order[i];
        }
        T=Createtree(postder,order,n);
        printf("Preorder: ");
        preprint(T);
        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