已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍因序列是多少，请详解（图解）

最好是加图解，谢谢

李希欠 · 2018-4-30 01:54:23

前序遍因序列是cedba。
二又树的遍历有3种：前序、中序和后序。
①前序首先遍历访问根结点，然后按左右顺序遍历子结点。
②中序遍历首先访问左子树，然后访问根结点，最后遍历右子树。
③后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。本题根据后序和中序遍历的结果可以得出二叉树的结构，然后再对其进行前序遍历。
二叉树
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点。
深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
[/url][url=https://gss0.baidu.com/-4o3dSag_xI4khGko9WTAnF6hhy/zhidao/pic/item/b8389b504fc2d562f1cce233ec1190ef77c66c23.jpg]

maa04 · 2018-4-30 01:54:24

cedba
方法很简单
dabec是后序遍历
则c是根节点
将中序遍历以c为中心分为两边
如此操作即可得到一棵树
(dabec),(debac)
((dabe)c),((deba)c)
(((dab)e)c),(((d)e(ba))c)
((((d)(a)b)e)c),(((d)e(b(a)))c)
这样就把树给构造了出来

ycsxm · 2018-4-30 01:54:25

这种简单的递归算法不知被问了多少次了。搜一下就有方法，很简单

已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍因序列是多少，请详解（图解）

3 个回复