通过中序和先序遍历构造二叉树

Question

我有以下序列：

顺序：{4,2,5,1,6,3} 预购：{1,2,4,5,3,6}

我想了解如何从这些序列构建二叉树，以及为什么可以使用中序和预序的组合，但不能使用其他一些组合。此外，我有兴趣了解如何在 C++ 中实现算法来实现此目的。

这是我的具体问题：

如何根据给定的中序和预序序列（如 {4, 2, 5, 1, 6, 3} 和 {1, 2, 4, 5, 3, 6}）构建二叉树？ 为什么可以使用 Inorder + Preorder 或 Inorder + Postorder 组合构建树，但不能使用 Preorder + Postorder 构建树？ 有人可以提供详细的 C++ 算法和代码实现，用于使用中序和先序遍历构建二叉树吗？ 我很感激有关此的任何见解和解释。谢谢！

   if (traversal_type == "pre") {
        root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start + 1, t_start + left_len, orderIndex, traversal_type);
        root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start + left_len + 1, t_end, orderIndex, traversal_type);
    }
    else if (traversal_type == "post") {
        root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start, t_end - 1, orderIndex, traversal_type);
        root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start, t_start + left_len - 1, orderIndex, traversal_type);
    }

Answer 1

重申遍历的定义以方便参考。对于具有根 R 和子树 T_L 和 T_r 的给定树，您有：

• 预序遍历的形式为

  R T_l... T_r...

• 中序遍历的形式为

  T_l... R T_r...

如果您查看前序遍历，您会看到根为 1，但您不知道 T_l 在哪里停止，T_r 在哪里开始。两者都可以是空的。 这就是中序遍历的用武之地：

1

左边的所有内容都是 T_l 的一部分，右边的所有内容都是 T_r 的一部分。 由于 1 位于中序遍历的位置 4，因此 T_l 包含 3 个项目，T_r 包含 2 个项目。

您现在可以获取输入数组的切片并递归地应用此过程，直到最终得到长度为 1（叶节点）或 0（空子树）的切片。

对于后序遍历，您从数组末尾开始读取根，但其他方面没有任何变化。

实现留给读者了。