预订和与Inorder遍历的关系

我发现如果我们有Preorder和Inorder Traversal，我们有一棵独特的树。预订和与Inorder遍历的关系

我可以得出结论：

对于每一根遍历，我们有多个序遍历。这是真的还是假的结论？每个人都会帮助我并添加一些细节。

再次感谢。

2014-09-05 user153695

是的，因为从一个预订序列中可以创建多个树。例如：[4,3,1，2]可以被重新定义为具有根4，子3和2的树。然后，您可以插入1作为3的左侧或右侧子视图。根据要插入的位置，顺序会改变。

你也可以这样推理：你有n数字，他们可以得到n！排列。如果排列的数量等于可以使用这些数字创建的树的数量，则可以从遍历生成树。事实并非如此，但正如你可以创建许多树，每个节点只有一个左边的孩子或者只有一个正确的孩子，这会给你2 * n！而且还有更多，所以必须有一个排列可以产生多于一棵树=>多于一次的遍历。

这在一般情况下当然是正确的，BST具有唯一的顺序序列。

来源

2014-09-05 06:23:15

所以我们可以说，一个预购是对应一个订单是假的？ – user153695 2014-09-05 06:26:21

一般情况下，是的。如果我们正在讨论BST，那么1个前序就相当于1个中序。 – 2014-09-05 06:30:46

非常感谢...添加+投票了。 – user153695 2014-09-05 06:36:02

真，例如：给出的前序遍历 ABDEC

 a 
    /\ 
    b c 
/\ 
    d e

许多序遍历是可能的： baedc， dbeac 等等...

来源

2014-09-05 06:27:06 Vishal

预订和与Inorder遍历的关系

回答

相关问题