风云三国武将技能:已知二叉树的前序和后序,能否写出中序遍历?

来源:百度文库 编辑:神马品牌网 时间:2024/05/05 05:09:44
已知二叉树的

前序遍历为:EGHP
后序遍历为:HPGE

能否写出二叉树的中序遍历?

不能
必须知道中序,再加个前或后序,才能推出另个序列~

当然可以
这道题目我做过,是考题...
结论是正确的

前序的第一个是根节点,第二个是根节点的左节点
后序最后一个是根节点,倒数第二个是根节点的右节点
比如说
前序 1 2 4 5 3
后续 4 5 2 3 1
那么根节点是 1
它的两个孩子是 2 3
然后前序2后面跟的是2的左节点也就是4
后序2后面跟的是2的右节点也就是5
于是2的两个节点是4 5
3没有
这样就可以还原除一棵树了
中序是4 2 5 1 3

是不能得到唯一的二叉树来的!

应该不可以
中序遍历是确定二叉树的一项指标
其他方式的遍历任选一个和中序遍历结合,就可以唯一确定一个二叉树
当然求二叉树是用递归解线性表的

不能。举个最简单的例子,
树A:有结点1,2,3,2是1的左孩子,3是2的右孩子
树B:有结点1,2,3,2是1的右孩子,3是2的左孩子

则A,B的前序都是123,后序都是321,但A的中序是231,B的中序是132

不能