我的数据结构和算法课上的两个练习听起来是这样的
构造预序遍历为:1,2,5,3,6,10,7的树，11、12、4、8、9，下轴遍历是5、2、1、10、6、3、11、7、12，8、4、9.
构造后向遍历为:5,2,10,6,11,12的树，7,3,8,9,4,1，下轴遍历是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的左边，所以我将它"向上"提升，因为我为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的子元素…满足上述约束的树不是唯一的