为什么不可能构造具有预订,后序和级别顺序遍历的二叉树？

Question

鉴于:

一个人不能用12或23或31或甚至123给出二进制树!为什么是这样？为什么InOrder Traversal对于构建原始树非常重要？

Answer 1

没有顺序遍历,我们无法构建树.为什么？假设您仅获得预订和后订单遍历.下面显示了一个简单的示例.
考虑两种不同的树木,

树1:

root=a;  
root->left=b;  
root->left->right=c;

树2:

root=a;  
root->right=b;  
root->right->left=c;

两棵树都不同,但具有相同的预订和后序.

pre-order - a b c  
post-order - c b a

这是因为我们不能单独使用预订或后序遍历来分离左子树和右子树.

预订,作为其名称,始终首先访问根,然后访问左右子树.也就是说,通过预订单列表,我们点击的每个节点将是子树的"根".

后序,作为其名称,始终首先访问左右子树,然后访问根.也就是说,向后遍历一个后序列表,我们点击的每个节点都是子树的"根".

另一方面,有序,总是首先访问左子树,然后是根,然后访问右子树,这意味着给定一个根(我们可以从上面的订单或后序遍历中获得) ),有序遍历告诉我们给定根的左右子树的大小,因此我们可以构造原始树.(想想看)

水平顺序遍历的情况也是如此.因此,如果我们想要获得一个唯一的树,我们需要一个有序遍历以及三个遍历中的任何其他遍历.
注 - 异常当然是一个完整的二叉树,其中可以使用预订序和后序遍历来构造树,因为树结构中没有歧义.