algorithm - 构造一棵树

Question

考虑到它的中序和前序遍历，我如何构造一棵树？我只是在寻找一种有效的算法。

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_j，其中是p_1, ...中的元素。这是原始树的左子树的根。拆分,和...和,和. 现在你有两个子序列代表原始树的两个子树的后序和中序遍历。p_2 ... p_j ... p_n-1p_ji_1i_2i_k-1p_1p_2 ... p_jp_j+1p_n-1i_1i_2 ... i_k-1i_k+1 ... i_n

作者：乔萨。

我已经按照 Jos 的指示实施了该算法，并且效果很好！

Answer 2

由于这是作业，我不会给你一个完整的答案，但希望足以让你感动。

想象一下，你有先序遍历，比如说这棵树。

遍历给你 2-7-2-6-5-11-5 ... 等等。注意 5 实际上是根的右孩子。

显然，你不能仅仅看数字就知道，所以要么你会被告知树的结构，要么你需要存储一些额外的数据（即，a 节点是左孩子还是右孩子， 例如）。

解析树只是一个递归函数，它将前序遍历作为输入（在传递输入时考虑您的范围）。正如我之前提到的，您的预购遍历应该附加一些额外的数据。

---

效率：

考虑构建这棵树时每个节点被访问了多少次，还要考虑读取输入的操作。有没有办法比构建树更快地重新组织输入？如果您需要操作数据，您必须使用什么结构。

---

按顺序：你需要同样的想法来完成它，所以我不会介绍它。我敢肯定，如果您迫切需要，其他人会这样做。