0

如何从给定的遍历方法（中序、后序或前序）中找到二叉树？

4

4 回答 4

4

您不能仅通过一次遍历（Inorder、Preorder 或 Postorder）来做到这一点。

如果给出了树的中序和前序遍历，则可以这样做：

  1. 预购的第一个元素将是树的根。（假设是A）
  2. 在 Inorder 中搜索根，因此根左侧的所有节点都是左子树的 Inorder，右节点是右子树的 Inorder。计算根左侧的节点数，例如 L。
  3. 在第二个 L 节点的后序中，将是左子树的前序，之后是右子树的前序。

所以我们找到了根元素，将我们的Inorder分为左子树的Inorder、右子树的Inorder和Preorder到左子树的前序和右子树的前序。所以我们可以通过递归来做到这一点，直到只剩下一个节点。

类似地，我们可以为 Inorder 和 Postorder 做，其中 root 将是 post order 的最后一个元素。

于 2009-09-06T16:36:13.390 回答
3

关于中序、后序、前序树遍历的维基百科文章在这里：

http://en.wikipedia.org/wiki/Tree_traversal。

您要查找的树从与您的搜索词匹配的节点开始。

于 2009-09-06T16:11:14.687 回答
2

（好的，既然我们已经决定修改后的问题应该在这里，我也在那里发布我的答案）

下面给出二叉树的后序和中序遍历。是否有可能从这些遍历中获得唯一的二叉树？

有可能的。

在后序遍历（左-右-根）中，整个树的根节点始终是最后一个（在您的情况下是 A）。在中序遍历（左-根-右）中，根之前的节点属于左子树，根之后的节点属于右子树。由于我们已经确定了根，我们可以确定左子树和右子树中的节点。

确定后，我们可以在后序列表中分离左右子树。所以，现在我们已经确定了左右子树和根节点：

postorder: left|right|root
inorder  : left|root|right

现在我们只需要递归地构造左右子树。鳍。

于 2009-09-06T16:42:24.690 回答
1

如果您想使用遍历结果恢复原始树，那么我有一些坏消息要告诉您 - 没有明确的解决方案。会有几棵树可以产生相同的遍历结果。

例如，对于以下树的中序遍历，将产生相同的结果：1, 2, 3

    2           3       1
   / \         /         \
  1   3       2           2
             /             \
            1               3
于 2009-09-06T16:27:52.597 回答