7-1 后序和中序构造二叉树

分数 5

作者 唐艳琴

单位 中国人民解放军陆军工程大学

本题目要求用后序序列和中序序列构造一棵二叉树（树中结点个数不超过10个），并输出其先序序列。

输入格式:

在第一行中输入元素个数。

第二行中输入后序序列，用空格分隔。

第三行中输入中序序列，用空格分隔。

输出格式:

输出此二叉树的先序序列，用空格分隔，最后也有一个空格。

输入样例:

5
20 40 50 30 10
20 10 40 30 50

输出样例:

10 20 30 40 50 

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

C程序如下：

#include 
#include 
 
// 定义二叉树节点结构体
typedef struct BTree {
    int data;  // 节点数据
    struct BTree* lchild, * rchild;  // 左右子树指针
} BTree, * Btree;
 
// 函数声明
Btree createInorder(int* post, int* mid, int n);
void PreorderTravel(Btree tree);
 
int main() {
    int n;
    // 输入节点数
    scanf("%d", &n);
    int post[n];  // 后序遍历数组
    int mid[n];   // 中序遍历数组
    
    // 输入后序遍历数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    
    // 输入中序遍历数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &mid[i]);
    }
    
    // 创建二叉树
    Btree root = createInorder(post, mid, n);
    
    // 先序遍历二叉树
    PreorderTravel(root);
    
    return 0;
}
 
// 根据后序和中序遍历数组创建二叉树
Btree createInorder(int* post, int* mid, int n) {
    if (n == 0) {
        // 如果没有节点，返回 NULL
        return NULL;
    }
    if (n == 1) {
        // 如果只有一个节点，创建该节点并返回
        Btree root = (Btree)malloc(sizeof(BTree));
        root->data = post[0];
        root->lchild = NULL;
        root->rchild = NULL;
        return root;
    }
 
    int rootValue = post[n - 1];  // 后序遍历数组的最后一个元素是根节点
    int index = 0;
    // 在中序遍历数组中找到根节点的位置
    while (index < n && mid[index] != rootValue) {
        index++;
    }
 
    // 创建根节点
    Btree root = (Btree)malloc(sizeof(BTree));
    root->data = rootValue;
    // 递归创建左子树和右子树
    root->lchild = createInorder(post, mid, index);
    root->rchild = createInorder(post + index, mid + index + 1, n - index - 1);
    return root;
}
 
// 先序遍历二叉树并打印节点数据
void PreorderTravel(Btree tree) {
    if (tree == NULL) {
        // 如果节点为空，返回
        return;
    }
    // 打印节点数据
    printf("%d ", tree->data);
    // 递归遍历左子树
    PreorderTravel(tree->lchild);
    // 递归遍历右子树
    PreorderTravel(tree->rchild);
}