为什么先序遍历和后序遍历不能确定唯一的二叉树?

xia962521280 · 2018-4-30 01:48:25

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。
由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树，由前序和后序遍历则不能唯一确定一棵二叉树。
由二叉树的中序和后序遍历序列可以唯一确定一棵二叉树，由前序和后序遍历则不能唯一确定一棵二叉树。
先序遍历，按照最优先顺序沿一定路径经过路径上所有的站。在二叉树中，先根后左再右。巧记：根左右。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
后序遍历是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根。首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。

为什么先序遍历和后序遍历不能确定唯一的二叉树?

1 个回复