algorithm - 如何根据前序&中序或后序&中序遍历构建非二叉树？

Question

我的数据结构和算法课的两个练习听起来像这样

Construct the tree whose preorder traversal is: 1, 2, 5, 3, 6, 10, 7,11, 12, 4, 8, 9, and inoder traversal is 5, 2, 1, 10, 6, 3, 11, 7, 12,8, 4, 9.

Construct the tree whose postorder traversal is: 5, 2, 10, 6, 11, 12,7, 3, 8, 9, 4, 1, and inoder traversal is 5, 2, 1, 10, 6, 3, 11, 7,12, 8, 4, 9.

我只需要画出树的结构，不需要用编程语言来实现。让这个任务更难的是树不是二叉树。我可以使用哪些技术来构建树？

Answer 1

我不确定我能否为此提供精确的算法解决方案，但我可以提供一个足够的概念性解决方案。我认为，如果您可以将其微调为定义明确的算法，它将对您有用，并使(那部分)期中考试变得微不足道。

首先，想一想中序遍历是如何遍历一棵树的。如果您绘制树，使最左边的 child 在左边(视觉上)而其他 child 在右边(视觉上)，那么中序遍历松散地从左到右。您可能会遇到一个问题，它不是完全从左到右(因为一个节点的子节点和父节点之间有一些重叠或类似的东西)，但您总是可以拉伸(stretch)树以使其清楚地“从左到右”。所以我利用它用中序遍历开始我的树:

5 2 1 10 6 3 11 7 12 8 4 9

然后我们的想法是我们根据先序遍历上下移动节点。这部分是很难定义的部分。基本上，如果“较早”访问节点，则向上移动节点；如果稍后访问节点，则将它们向下移动。因此，例如，在前序遍历中，1 在 2 和 5 的左侧，所以我将它“向上”提升，即我为 1 创建了 2 和 5 个祖先(但不一定是 child )。所以像

   1
5 2 10 6 3 11 7 12 8 4 9

然后你看到 2 出现在 5 之前，所以我加注 2:

    1
  2 
5     10 6 3 11 7 12 8 4 9

然后您会看到在前序遍历中 3 出现在 6 和 10 之前，因此我们可以“提高”它。

    1
  2        3
5     10 6   11 7 12 8 4 9

等等。请注意，3 最终可能是 2 或 1 的子代......满足上述约束的树不是唯一的。