PTA（树和二叉树）1-9 确定二叉树（先序序列+中序序列）

1-9 确定二叉树（先序序列+中序序列）

分数 3

作者 黄龙军

单位 绍兴文理学院

要求实现函数，根据二叉树的先序序列和中序序列确定二叉树并返回指向二叉树根结点的指针。二叉树采用二叉链表存储，结点结构如下：

1
2
3
4
5
6
7
8
9
struct BiTNode {                                  // 结点结构 
    int data;                                     // 数据域 
    BiTNode *lchild,*rchild;                      // 左右孩子指针 
    BiTNode(int d,BiTNode *left,BiTNode *right) { // 构造函数 
        data=d;
        lchild=left;
        rchild=right;
    }
};

函数接口定义：

1
BiTNode* CreateBT(int* pre, int *in, int n);

其中参数 pre是指向先序序列数组首元素的指针， in是指向中序序列数组首元素的指针 ，n是结点总数。

裁判测试程序样例：

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
#include<iostream>
using namespace std;

struct BiTNode {                                  // 结点结构 
    int data;                                     // 数据域 
    BiTNode *lchild,*rchild;                      // 左右孩子指针 
    BiTNode(int d,BiTNode *left,BiTNode *right) { // 构造函数 
        data=d;
        lchild=left;
        rchild=right;
    }
};

void PostOrder(BiTNode* p, int &cnt)    // 后序遍历
//  根据先序序列和中序序列确定二叉树，pre是指向后序序列数组首元素的指针，in是指向中序序列数组首元素的指针 ，n是结点总数
BiTNode* CreateBT(int* pre, int *in, int n);  

// 根据先序序列和中序序列创建二叉树并后序遍历之
int main() {
    int n;
    while(cin>>n) {
        int pre[n], in[n], cnt=0;
        for(int i=0; i<n; i++) cin>>pre[i];
        for(int i=0; i<n; i++) cin>>in[i];
        BiTNode* root=CreateBT(pre,in,n);
        PostOrder(root, cnt);
        cout<<endl;
    }
    return 0;
}

//请在此处填写答案

void PostOrder(BiTNode* p, int &cnt) {                 // 后序遍历
    if(!p) return;
    PostOrder(p->lchild, cnt);
    PostOrder(p->rchild, cnt);
    cnt++;
    if (cnt>1) cout<<" ";
    cout<<p->data;
}

输入样例：

1
2
3
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

输出样例：

1
7 4 2 8 9 5 6 3 1
  • 我天，这题也好妙，先一直以为只能用脑子想出来
  • 现在可以通过代码实现了

答案

可以根据先序序列和中序序列的特点，使用递归的方法来构建二叉树。先序序列的第一个元素就是根节点，然后在中序序列中找到根节点的位置，根节点左边的元素就是左子树的中序序列，右边的元素就是右子树的中序序列。根据中序序列中左子树和右子树的节点个数，在先序序列中也可以划分出左子树和右子树的先序序列，然后递归地构建左子树和右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BiTNode* CreateBT(int* pre, int *in, int n) {
    if (n == 0) {
        return NULL;
    }
    // 先序序列的第一个元素为根节点
    BiTNode *root = new BiTNode(pre[0], NULL, NULL);
    int rootIndex;
    // 在中序序列中找到根节点的位置
    for (rootIndex = 0; rootIndex < n; rootIndex++) {
        if (in[rootIndex] == pre[0]) {
            break;
        }
    }
    // 递归构建左子树
    root->lchild = CreateBT(pre + 1, in, rootIndex);
    // 递归构建右子树
    root->rchild = CreateBT(pre + rootIndex + 1, in + rootIndex + 1, n - rootIndex - 1);
    return root;
}

为什么创建右子树的第一个参数是pre + rootIndex + 1

  • 核心背景：遍历序列的特性

    二叉树的先序遍历（pre）顺序是：根节点 → 左子树 → 右子树

    二叉树的中序遍历（in）顺序是：左子树 → 根节点 → 右子树

    具体分析

    假设当前递归处理的序列长度为 n，即当前子树包含 n 个节点。

    1. 根节点的确定：

      先序序列的第一个元素 pre[0] 是当前子树的根节点。

    2. 中序序列中根节点的位置：

      在中序序列 in 中找到根节点的索引 rootIndex，则：

      • 中序序列中，[0, rootIndex-1] 是左子树的节点（共 rootIndex 个节点）。
      • 中序序列中，[rootIndex+1, n-1] 是右子树的节点（共 n - rootIndex - 1 个节点）。

    3. 先序序列中右子树的起始位置：

      先序序列的结构是 [根节点][左子树的所有节点][右子树的所有节点]。

      • 根节点占用 pre[0] 位置。
      • 左子树有 rootIndex 个节点，因此左子树在预序序列中占据 pre[1] 到 pre[rootIndex]（共 rootIndex 个元素）。
      • 因此，右子树的第一个节点在预序序列中的位置是 rootIndex + 1（跳过根节点和左子树的所有节点）。

1. 核心依据（序列特性）

  • 先序序列：根节点 → 左子树先序 → 右子树先序（第一个元素必为当前树的根）。
  • 中序序列：左子树中序 → 根节点 → 右子树中序（根节点可分割左右子树）。

2. 步骤拆解

  1. 终止条件：若节点数 n=0（空树 / 子树），返回 NULL。
  2. 创建根节点：取先序序列第一个元素 pre[0] 作为当前树的根。
  3. 定位根节点在中序的位置：遍历中序序列，找到与根节点值相等的索引 rootIndex。
  4. 递归构建左子树：
    • 左子树先序序列：从 pre[1] 开始，长度为 rootIndex（左子树节点数 = 根节点在中序的索引）。
    • 左子树中序序列：从 in[0] 开始，长度为 rootIndex。
  5. 递归构建右子树：
    • 右子树先序序列：从 pre[rootIndex+1] 开始，长度为 n-rootIndex-1（总节点数 - 左子树节点数 - 根节点）。
    • 右子树中序序列：从 in[rootIndex+1] 开始，长度为 n-rootIndex-1。
  6. 返回根节点：当前树构建完成，返回根节点指针，供上层递归使用。