EC20-根据先序和中序遍历序列构建二叉树¶

代码实现¶

C
// 函数 func：根据先序和中序遍历序列构建二叉树
// 参数：
// pre[] - 先序遍历序列数组
// mid[] - 中序遍历序列数组
// L1,R1 - 先序序列的左右边界索引
// L2,R2 - 中序序列的左右边界索引
// 返回值：构建好的二叉树根节点
BiTree func(char pre[], char mid[], int L1, int R1, int L2, int R2) {
    // 创建新节点并分配内存
    BiTree root = (BiTree)malloc(sizeof(BTNode));

    // 先序序列的第一个元素就是当前子树的根节点
    root->data = pre[L1];

    // 在中序序列中查找根节点的位置
    int i = L2;
    for (; mid[i] != pre[L1]; i++); // 空循环体，只用于查找

    // 构建左子树
    if (i > L2) {
        // 如果根节点在中序序列中不是最左边的元素，则存在左子树
        // 左子树在先序序列中的范围：[L1+1, L1+i-L2]
        // 左子树在中序序列中的范围：[L2, i-1]
        root->lchild = func(pre, mid, L1 + 1, L1 + i - L2, L2, i - 1);
    } else {
        // 不存在左子树
        root->lchild = NULL;
    }

    // 构建右子树
    if (i < R2) {
        // 如果根节点在中序序列中不是最右边的元素，则存在右子树
        // 右子树在先序序列中的范围：[L1+i-L2+1, R1]
        // 右子树在中序序列中的范围：[i+1, R2]
        root->rchild = func(pre, mid, L1 + i - L2 + 1, R1, i + 1, R2);
    } else {
        // 不存在右子树
        root->rchild = NULL;
    }

    return root; // 返回构建好的子树根节点
}

// 函数 func：根据后序和中序遍历序列构建二叉树
// 参数含义与上面类似
BiTree func(char post[], char mid[], int L1, int R1, int L2, int R2) {
    // 创建新节点并分配内存
    BiTree root = (BiTree)malloc(sizeof(BTNode));

    // 后序序列的最后一个元素就是当前子树的根节点
    root->data = post[R1];

    // 在中序序列中查找根节点的位置
    int i = L2;
    for (; mid[i] != post[R1]; i++); // 空循环体，只用于查找

    // 构建左子树
    if (i > L2) {
        // 如果根节点在中序序列中不是最左边的元素，则存在左子树
        // 左子树在后序序列中的范围：[L1, i-L2+L1-1]
        // 左子树在中序序列中的范围：[L2, i-1]
        root->lchild = func(post, mid, L1, i - L2 + L1 - 1, L2, i - 1);
    } else {
        // 不存在左子树
        root->lchild = NULL;
    }

    // 构建右子树
    if (i < R2) {
        // 如果根节点在中序序列中不是最右边的元素，则存在右子树
        // 右子树在后序序列中的范围：[i-L2+L1, R1-1]
        // 右子树在中序序列中的范围：[i+1, R2]
        root->rchild = func(post, mid, i - L2 + L1, R1 - 1, i + 1, R2);
    } else {
        // 不存在右子树
        root->rchild = NULL;
    }

    return root; // 返回构建好的子树根节点
}

代码逻辑解析¶

1. 构建原理¶

先序遍历：根 → 左子树 → 右子树
中序遍历：左子树 → 根 → 右子树
后序遍历：左子树 → 右子树 → 根

2. 核心思想¶

通过先序或后序序列确定根节点
通过中序序列确定左右子树的边界
递归构建左右子树

关键算法理解¶

1. 边界计算详解¶

先序+中序构建：¶

Text Only

当前处理范围：
先序：[L1, R1]  中序：[L2, R2]

步骤：
1. 根节点 = pre[L1]
2. 在中序序列中找到根节点位置 i
3. 左子树节点数 = i - L2
4. 右子树节点数 = R2 - i

左子树边界：
- 先序：[L1+1, L1+i-L2]
- 中序：[L2, i-1]

右子树边界：
- 先序：[L1+i-L2+1, R1]
- 中序：[i+1, R2]

后序+中序构建：¶

Text Only

当前处理范围：
后序：[L1, R1]  中序：[L2, R2]

步骤：
1. 根节点 = post[R1]
2. 在中序序列中找到根节点位置 i
3. 左子树节点数 = i - L2
4. 右子树节点数 = R2 - i

左子树边界：
- 后序：[L1, i-L2+L1-1]
- 中序：[L2, i-1]

右子树边界：
- 后序：[i-L2+L1, R1-1]
- 中序：[i+1, R2]

2. 图解说明¶

假设二叉树结构：

Text Only
1 2 3 4 5	`A // 根节点 / \ B C // 第1层 / \ \ D E F // 第2层`

对应的遍历序列：

Text Only
1 2 3	`先序序列：[A, B, D, E, C, F] // 根-左-右中序序列：[D, B, E, A, C, F] // 左-根-右后序序列：[D, E, B, F, C, A] // 左-右-根`

构建过程示例（先序+中序）：

Text Only

第1步：pre[0]=A 是根节点
       在中序中找到A的位置：index=3
       左子树：中序[D,B,E] 右子树：中序[C,F]

第2步：处理左子树
       pre[1]=B 是左子树根节点
       在中序[D,B,E]中找到B的位置：index=1
       左子树的左子树：[D] 右子树的右子树：[E]

第3步：处理右子树
       pre[5]=C 是右子树根节点
       在中序[C,F]中找到C的位置：index=0
       右子树无左子树，右子树的右子树：[F]

时间复杂度分析¶

1. 递归次数¶

每个节点被处理 exactly 一次：O(n)

2. 每次递归的操作¶

查找根节点在中序序列中的位置：O(n)（最坏情况）
边界计算和赋值操作：O(1)

3. 总时间复杂度¶

O(n²)（最坏情况）

4. 优化方案¶

C
// 使用哈希表预处理中序序列，将查找时间优化为 O(1)
int hash[256]; // 假设字符集大小为256
for (int i = 0; i < n; i++) {
    hash[mid[i]] = i; // 预处理：O(n)
}
// 查找操作：O(1)
int i = hash[pre[L1]];

优化后时间复杂度：O(n)

空间复杂度分析¶

1. 额外空间使用¶

节点创建：O(n)
递归调用栈：O(h)，h为树的高度

2. 总空间复杂度¶

O(n)（节点存储）+ O(h)（递归栈）

最坏情况下（退化为链表）：O(n) 最好情况下（完全二叉树）：O(log n)

边界条件处理¶

1. 空子树判断¶

C
if (i > L2)  // 存在左子树
if (i < R2)  // 存在右子树

2. 单节点子树¶

当 i == L2 且 i == R2 时，说明当前子树只有一个节点

延伸知识点¶

1. 为什么需要中序序列？¶

C
// 仅凭先序序列无法确定树结构
// 先序：[A,B,C] 可能对应多种结构：
// 结构1：    A        结构2：  A
//           / \              /
//          B   C            B
//                          /
//                         C
// 中序序列可以确定左右子树的划分

2. 层序遍历构建二叉树¶

C
// 根据层序序列构建二叉树
BiTree buildFromLevelOrder(char level[], int n) {
    if (n == 0) return NULL;

    BiTree root = createNode(level[0]);
    Queue* queue = createQueue();
    enqueue(queue, root);

    int i = 1;
    while (!isEmpty(queue) && i < n) {
        BiTree node = dequeue(queue);

        // 处理左子节点
        if (i < n) {
            node->lchild = createNode(level[i++]);
            enqueue(queue, node->lchild);
        }

        // 处理右子节点
        if (i < n) {
            node->rchild = createNode(level[i++]);
            enqueue(queue, node->rchild);
        }
    }

    return root;
}

3. 构建算法的完整实现¶

C
// 完整的先序+中序构建函数
BiTree buildTreeFromPreIn(char* preorder, char* inorder, int n) {
    if (n <= 0) return NULL;
    return func(preorder, inorder, 0, n-1, 0, n-1);
}

// 完整的后序+中序构建函数
BiTree buildTreeFromPostIn(char* postorder, char* inorder, int n) {
    if (n <= 0) return NULL;
    return func(postorder, inorder, 0, n-1, 0, n-1);
}

4. 非递归构建方法¶

C
// 使用迭代方法构建二叉树
BiTree buildIterative(char pre[], char in[], int n) {
    if (n == 0) return NULL;

    BiTree root = createNode(pre[0]);
    Stack* stack = createStack();
    push(stack, root);

    int inIndex = 0;

    for (int i = 1; i < n; i++) {
        BiTree node = stackTop(stack);

        if (node->data != in[inIndex]) {
            // 处理左子树
            node->lchild = createNode(pre[i]);
            push(stack, node->lchild);
        } else {
            // 处理右子树
            while (!isEmpty(stack) && 
                   stackTop(stack)->data == in[inIndex]) {
                node = pop(stack);
                inIndex++;
            }
            node->rchild = createNode(pre[i]);
            push(stack, node->rchild);
        }
    }

    return root;
}

5. 实际应用场景¶

表达式解析：将前缀/后缀表达式转换为语法树
编译器设计：语法分析阶段构建抽象语法树
数据库索引：B+树等数据结构的构建
文件系统：目录结构的表示和操作

这些算法体现了分治思想、递归技巧和数据结构映射的核心概念，是计算机科学中非常重要的基础算法。