1

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

构造前序遍历为：1、2、5、3、6、10、7、11、12、4、8、9，inode遍历为5、2、1、10、6、3、11的树， 7、12、8、4、9。

构造后序遍历为：5, 2, 10, 6, 11, 12, 7, 3, 8, 9, 4, 1，inode遍历为5, 2, 1, 10, 6, 3, 11的树， 7、12、8、4、9。

我只需要绘制树的结构，而不用编程语言实现它。使这项任务变得更难的是树不是二叉树。我可以使用什么技术来建造树木？

4

1 回答 1

2

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

首先，考虑中序遍历如何遍历树。如果您绘制树，使最左边的孩子在左边（视觉上）而其他孩子在右边（视觉上），那么中序遍历松散地从左到右。你可能会遇到一个问题，它不是从左到右（因为一个节点的子节点和父节点之间有一些重叠或类似的东西），但你总是可以将树拉伸以使其清楚地“从左到右”。因此，我通过使用中序遍历开始我的树来利用这一点：

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

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

   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 的孩子......满足上述约束的树不是唯一的。

于 2013-04-18T18:17:28.503 回答