根据后序和中序遍历输出先序遍历_根据后序和中序遍历输出先序遍历总结

根据后序和中序遍历输出先序遍历

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

Preorder: 4 1 3 2 6 5 7
1

//头文件包含
#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;
void Pre(BiTree &T, int *Last, int *Middle, int n)
{
    if(n <= 0) return;
    T = (BiTNode *)malloc(sizeof(BiTNode));
    T -> data = Last[n - 1];
    T -> lchild = NULL;
    T -> rchild = NULL;
    int i;
    for(i = 0; i < n; ++i)
        if(Middle[i] == Last[n - 1]) break;
    Pre(T -> lchild, Last, Middle, i);
    Pre(T -> rchild, Last + i, Middle + i + 1, n - i - 1);
}
void PrintPreTree(BiTree T)
{
    if(!T) return;
    printf(" %d", T -> data);
    PrintPreTree(T -> lchild);
    PrintPreTree(T -> rchild);
}
int main(void)
{
    int Last[1000];
    int Middle[1000];
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &Last[i]);
    for(int j = 0; j < n; ++j)
        scanf("%d", &Middle[j]);
    BiTree T;
    Pre(T, Last, Middle, n);
    printf("Preorder:");
    PrintPreTree(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