跳到主要内容

利用遍历序列还原二叉树

二叉树的前序、中序和后序遍历是数据结构中的基本操作，利用这些遍历序列可以唯一地还原出原始的二叉树。本文将详细讲解如何通过前序和中序遍历、后序和中序遍历来还原二叉树，并提供相应的C语言代码实现。

基本概念​

在开始之前，我们需要理解三种遍历方式：

  1. 前序遍历（Preorder Traversal）： 顺序为：根节点 -> 左子树 -> 右子树。
  2. 中序遍历（Inorder Traversal）： 顺序为：左子树 -> 根节点 -> 右子树。
  3. 后序遍历（Postorder Traversal）： 顺序为：左子树 -> 右子树 -> 根节点。

前序和中序遍历还原二叉树​

给定一个二叉树的前序和中序遍历序列，可以唯一地还原该二叉树。具体步骤如下：

算法步骤​

  1. 确定根节点： 前序遍历的第一个元素是根节点。
  2. 划分左右子树： 在中序遍历中找到根节点的位置，其左侧的元素属于左子树，右侧的元素属于右子树。
  3. 递归构建左右子树： 使用相应的前序和中序序列递归构建左子树和右子树。

公式表示​

设前序遍历为P=[P1,P2,…,Pn]P = [P_1, P_2, \ldots, P_n]，中序遍历为I=[I1,I2,…,In]I = [I_1, I_2, \ldots, I_n]，则：

  1. 根节点为R=P1R = P_1。
  2. 在中序遍历中找到RR的位置，设为kk，则：
    • 左子树的中序遍历为IL=[I1,…,Ik−1]I_L = [I_1, \ldots, I_{k-1}]
    • 右子树的中序遍历为IR=[Ik+1,…,In]I_R = [I_{k+1}, \ldots, I_n]
    • 左子树的前序遍历为PL=[P2,…,Pk]P_L = [P_2, \ldots, P_{k}]
    • 右子树的前序遍历为PR=[Pk+1,…,Pn]P_R = [P_{k+1}, \ldots, P_n]

C语言代码实现​

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

// 前序和中序构建二叉树的递归函数
TreeNode* buildTreePreIn(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0 || inorderSize == 0) {
        return NULL;
    }

    int rootVal = preorder[0];
    TreeNode* root = newNode(rootVal);

    int rootIndexInorder;
    for (rootIndexInorder = 0; rootIndexInorder < inorderSize; ++rootIndexInorder) {
        if (inorder[rootIndexInorder] == rootVal) {
            break;
        }
    }

    root->left = buildTreePreIn(preorder + 1, rootIndexInorder, inorder, rootIndexInorder);
    root->right = buildTreePreIn(preorder + 1 + rootIndexInorder, preorderSize - 1 - rootIndexInorder, inorder + rootIndexInorder + 1, inorderSize - 1 - rootIndexInorder);

    return root;
}

后序和中序遍历还原二叉树​

类似地，给定一个二叉树的后序和中序遍历序列，也可以唯一地还原该二叉树。具体步骤如下：

算法步骤​

  1. 确定根节点： 后序遍历的最后一个元素是根节点。
  2. 划分左右子树： 在中序遍历中找到根节点的位置，其左侧的元素属于左子树，右侧的元素属于右子树。
  3. 递归构建左右子树： 使用相应的后序和中序序列递归构建左子树和右子树。

公式表示​

设后序遍历为P=[P1,P2,…,Pn]P = [P_1, P_2, \ldots, P_n]，中序遍历为I=[I1,I2,…,In]I = [I_1, I_2, \ldots, I_n]，则：

  1. 根节点为R=PnR = P_n。
  2. 在中序遍历中找到RR的位置，设为kk，则：
    • 左子树的中序遍历为IL=[I1,…,Ik−1]I_L = [I_1, \ldots, I_{k-1}]
    • 右子树的中序遍历为IR=[Ik+1,…,In]I_R = [I_{k+1}, \ldots, I_n]
    • 左子树的后序遍历为PL=[P1,…,Pk−1]P_L = [P_1, \ldots, P_{k-1}]
    • 右子树的后序遍历为PR=[Pk,…,Pn−1]P_R = [P_{k}, \ldots, P_{n-1}]

C语言代码实现​

// 后序和中序构建二叉树的递归函数
TreeNode* buildTreePostIn(int* postorder, int postorderSize, int* inorder, int inorderSize) {
    if (postorderSize == 0 || inorderSize == 0) {
        return NULL;
    }

    int rootVal = postorder[postorderSize - 1];
    TreeNode* root = newNode(rootVal);

    int rootIndexInorder;
    for (rootIndexInorder = 0; rootIndexInorder < inorderSize; ++rootIndexInorder) {
        if (inorder[rootIndexInorder] == rootVal) {
            break;
        }
    }

    root->left = buildTreePostIn(postorder, rootIndexInorder, inorder, rootIndexInorder);
    root->right = buildTreePostIn(postorder + rootIndexInorder, postorderSize - 1 - rootIndexInorder, inorder + rootIndexInorder + 1, inorderSize - 1 - rootIndexInorder);

    return root;
}

前序和后序遍历能否唯一确定二叉树？​

前序遍历和后序遍历不能唯一确定一棵二叉树。原因是，仅通过前序和后序遍历无法唯一确定节点的左右子树结构。举个例子，假设有以下两种不同结构的树：

树1：
    1
   /
  2
   \
    3

树2：
    1
     \
      2
     /
    3

这两棵树的前序遍历和后序遍历都是相同的，但它们的结构不同。因此，仅有前序和后序遍历是不能唯一确定一棵二叉树的。