为什么在给出预购，后购和级别订单遍历的情况下构造二叉树是不可能的？ [英] Why it is impossible to construct Binary Tree with Pre-Order, Post Order and Level Order traversals given?
问题描述
给出：
- 订单遍历。
- 订单遍历。
- 级别顺序遍历。
一个人不能用12或23或31构造二叉树，甚至不能给出123！为什么是这样？以及为什么顺序遍历对于构建原始树非常重要？
One can not contruct a Binary Tree with 12 or 23 or 31 or even if 123 are given! Why is this? and Why InOrder Traversal is very important to construct the original Tree?
推荐答案
没有顺序我们就无法构建树遍历。为什么？假设您只获得了预遍历和后遍历，下面是一个简单的示例。
考虑两个不同的树，
We can't build a tree without the in-order traversal. Why? Let's say you are given the pre-order and post-order traversals only.A simple example is shown below.
Consider two different trees,
树1：
TREE 1:
root=a;
root->left=b;
root->left->right=c;
树2：
root=a;
root->right=b;
root->right->left=c;
这两种树都不同，但是具有相同的前序和后序顺序。
Both the trees are different, but have same pre-order and post-order sequence.
pre-order - a b c
post-order - c b a
之所以这样，是因为我们不能仅使用前遍历或后遍历来分离左子树和右子树。
This is so because we cannot separate the left sub-tree and right sub-tree using the pre-order or post-order traversal alone.
预购作为其名称，总是先访问根，然后再访问左和右子树。也就是说，遍历预购列表，我们命中的每个节点将是子树的根。
Pre-order, as its name, always visits root first and then left and right sub-trees. That is to say, walking through a pre-order list, each node we hit would be a "root" of a sub-tree.
后置顺序作为其名称，总是先访问左右子树，然后再访问根。也就是说，向后浏览后置列表，我们命中的每个节点都是子树的根。
Post-order, as its name, always visits left and right sub-trees first and then the root. That is to say, walking through a post-order list backward, each node we hit would be a "root" of a sub-tree.
按顺序另一方面，总是先访问左子树，然后再访问根，然后再访问右子树，这意味着给定一个根（我们可以从如上所述的前序或后序遍历中获得）遍历告诉我们给定根的左右子树的大小，因此我们可以构造原始树。（请考虑一下）
In-order, on the other hand, always visits left sub-tree first and then root and then right sub-tree, which means that given a root(which we can obtain from the pre-order or post-order traversal as stated above), in-order traversal tells us the sizes of the left and right sub-trees of a given root and thus we can construct the original tree.(Think this out)
水平顺序遍历。因此，如果要获得唯一的树，则需要按顺序遍历以及这三个遍历中的任何其他遍历。
注-当然，例外是完整的二叉树，其中的前序和后顺序遍历可用于构造树，因为树结构没有歧义。
Same is the case with level-order traversal. Thus if we want to obtain a unique tree we need an in-order traversal along with any other of the three traversals.
Note - The exception is of course a full binary tree, in which pre-order and post-order traversals can be used to construct the tree, as there is no ambiguity in tree structure.
这篇关于为什么在给出预购，后购和级别订单遍历的情况下构造二叉树是不可能的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
