如何构建基于前序和中序或者后序和中序遍历的非二叉树？的练习

Question

两个用于我的数据结构和算法类的声音这样

构建其序遍历是树：1，2,5，3，6，10，7， 11，12，4 ，8,9，并且inoder遍历是5,2,1,10,6,3,11,7,12, 8，4，9。

构造树的后序遍历是：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。

我只需绘制树的结构，而不用编程语言实现它。让这项工作更难的事情是树不是二叉树。我可以用什么技术来建造树木？

Answer 1

我不知道我能给出一个确切的算法解决了这个，但我可以给一个概念上的一个应该是足够的。我认为，如果你可以将它精确地调整为一个明确的算法，那么它对你有用，并使（中间的）微不足道。

首先，考虑一个序遍历如何穿越一棵树。如果绘制树使得最左边的孩子在左边（视觉上）并且其他孩子在右边（视觉上），那么中间遍历松散地从左边到右边。你可能会遇到一个问题，它不完全左到右（因为一个节点的子节点和父节点之间有某种重叠或类似的情况），但你总是可以伸出树来使它明显地“从左到右”。于是我利用这一点通过 开始我的树与序遍历：

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 

然后你就看到了前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 

依此类推。请注意，3最终可能是2或1的孩子......满足上述约束条件的树不是唯一的。