输出二叉树

coding>C++
975 词

题目描述

我们知道二叉树的先序序列和中序序列或者是中序和后序能够唯一确定一颗二叉树。现在给一颗二叉树的先序序列和中序序列，要求输出它的后序序列。

输入

多组测试数据，每组测试数据格式如下：
第一行为先序序列
第二行为中序序列

输出

     输出该二叉树的后序序列。

样例输入

1
2
ABFCDGHEI
BFAGDHCIE

样例输出

1
FBGHDIECA

题解

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef char ElemType;
typedef struct node {
    ElemType data;
    struct node *lchild;
    struct node *rchild;
} BTNode;
void PostOrder(BTNode *b) {
    if (b != nullptr) {
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        printf("%c", b->data);
    }
}
BTNode *CreatBT(char *pre, char *in, int n) {
    BTNode *b;
    char *p;
    int k;
    if (n <= 0) return nullptr;
    b = (BTNode *) malloc(sizeof(BTNode));
    b->data = *pre;
    for (p = in; p < in + n; p++)
        if (*p == *pre) break;
    k = p - in;
    b->lchild = CreatBT(pre + 1, in, k);
    b->rchild = CreatBT(pre + 1 + k, p + 1, n - 1 - k);
    return b;
}
int main() {
    char a[100];
    char b[100];
    cin >> a >> b;
    int len = strlen(a);
    BTNode *BT = CreatBT(a, b, len);
    PostOrder(BT);
    return 0;
}