构建一棵树

Question

如何根据中序遍历和前序遍历构建一棵树？ 我只是在寻找一个高效的算法。

- Carlin

---

好的，递归地说。我希望你不是我的学生。 - Ritwik Bose

需要一些澄清。输入数据的格式是什么？树是否平衡？你所说的高效是什么意思（Ordo(x)还是只是“不太疯狂”）？你想要构建的结构是什么？使用链接对象的树，还是使用数组的树？ - ron

http://forums.devshed.com/software-design-43/finding-binary-tree-from-inorder-and-preorder-traversals-151147.html - Heinzi

我是一名毕业生。所以，我不再是任何人的学生了 :) - Carlin

Answer 1

以下是从Sun的论坛（现在是Oracle吧...）中抄袭来的：

问题:
有人能帮我讲解如何用中序遍历和后序遍历构建二叉树吗，我只是想知道算法，以便我可以应用它。

答案:
令p_1, p_2 ... p_n为后序遍历，令i_1, i_2 ... i_n为中序遍历。从后序遍历中我们知道树的根节点是p_n。在中序遍历中找到此元素，假设为i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n。从中序遍历中找到左子树中的所有元素，即i_1, i_2 ... i_k-1和右子树中的所有元素，即i_k+1 ... i_n。

移除元素p_n（以及元素i_k == p_n）。在p_1, p_2 ... p_j ... p_n-1中找到最右侧的元素p_j，其中p_j是i_1, i_2 ... i_k-1中的一个元素。这是原树左子树的根节点。 将p_1, p_2 ... p_j和p_j+1 ... p_n-1以及i_1, i_2 ... i_k-1和i_k+1 ... i_n分成两个子序列。现在你有两个子树的后序和中序遍历序列。

作者: JosAH.

我按照Jos的指示实现了一次算法，它工作得非常好！

- Bart Kiers

---

在p_1 ~ p_n-1中查找i_1i_k-1中的最右元素p_j太耗时了，需要O(n^2)的时间。实际上，在删除p_n后，在i_1i_n中找到它的位置。我们已经知道了p_j的位置。这是因为我们已经知道了其左子树和右子树中节点的数量，这可以通过在i_1i_n中计算p_n之后的元素来获得。通过这种方式，我们可以轻松地找到分割p_1p_n-1的位置。 - ibread

Answer 2

由于这是一份作业，我不会给你完整的答案，但希望能够为你提供足够的帮助。

假设你有一个二叉树的前序遍历，比如this。

遍历结果为2-7-2-6-5-11-5 ...等等。请注意，数字5实际上是根节点的右子节点。

显然，仅凭这些数字你无法确定树的结构，因此你需要知道树的结构或者存储一些额外的数据（例如，一个节点是左子节点还是右子节点）。

解析树只需要一个递归函数，该函数以前序遍历作为输入（考虑在传递输入时的作用域）。正如我之前提到的，你的前序遍历应该附带一些额外的数据。

---

效率：

在构建这棵树时，考虑每个节点被访问的次数，同时也要考虑读取输入的操作。有没有一种比构建树更快的重新组织输入的方法？如果需要操作数据，你需要使用什么样的结构。

---

按顺序：你需要相同的想法来帮助你完成它，所以我不会涉及它。如果你非常需要，我相信其他人会提供帮助。

- Ritwik Bose