我的数据结构和算法类的两个练习听起来像这样
构造一棵树,它的前序遍历是:1,2,5,3,6,10,7,
11,12,4,8,9,inoder遍历是5,2,1,10,6,3,11,7,12,
八,四,九。
构造后序遍历为:5,2,10,6,11,12的树。
7、3、8、9、4、1,inoder遍历是5、2、1、10、6、3、11、7,
12,8,4,9。
我只需要绘制树的结构,而不用编程语言实现它使这项任务更加困难的是树不是二叉树。我可以用什么技术来建造这些树?

最佳答案

我不确定我是否能给出一个精确的算法解决方案,但我可以给出一个概念性的,应该足够的解决方案我认为如果你能把它微调成一个定义良好的算法,它会对你很有用,并使(这部分)中期变得微不足道。
首先,考虑一个有序遍历如何遍历一棵树。如果您绘制树,使最左边的子项向左(视觉上),而其他子项向右(视觉上),则无序遍历松散地从左向右进行。您可能会遇到这样一个问题:它不是完全从左到右的(因为一个节点的子节点和父节点之间有一些重叠,或者类似的情况),但是您始终可以将树向外拉伸,以使其清晰地显示为“从左到右”。所以我利用这个机会
以顺序遍历开始我的树:

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

然后,我们的想法是根据预序遍历来上下移动节点这部分是很难定义的部分基本上,如果节点是“较早”访问的,则将其向上移动;如果节点是稍后访问的,则将其向下移动。例如,1在2和5的左上,在前序遍历中,所以我把它“举”起来,因为我把2和5的祖先(但不一定是孩子)变成了1所以有点像
   1
5 2 10 6 3 11 7 12 8 4 9

然后你看到5之前的2,所以我提出了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

等等注意三个孩子最终可能是2或1的孩子…满足上述约束的树不是唯一的。

关于algorithm - 如何基于前后顺序或前后顺序遍历构造非二叉树?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/16089489/

10-11 22:23
查看更多