为什么不可能用给定的前序、后序和级序遍历构造二叉树? [英] Why it is impossible to construct Binary Tree with Pre-Order, Post Order and Level Order traversals given?

问题描述

给定:

1. 预购遍历.
2. 后序遍历.
3. 层序遍历.

不能用 12、23、31 甚至 123 来构造二叉树！为什么是这样?以及为什么 InOrder Traversal 对构造原始 Tree 非常重要?

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:

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，顾名思义，总是先访问根，然后再访问左右子树.也就是说，遍历一个前序列表，我们命中的每个节点都是一个子树的根".

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屋！