首页 > 试题广场 >

一个二叉树,先序遍历的结果是ABDECFG,中序遍历的结果是

[问答题]
一个二叉树,先序遍历的结果是ABDECFG,中序遍历的结果是DBEAFGC,后序遍历的结果是:______________。

楼上画的那个图是有问题的。
首先可以肯定:
1.已知中序和前序,或中序和后序,可以唯一确定一棵二叉树
2.前序遍历的第一个结点是树(子树)根节点
3.后序遍历的最后一个结点是树(子树)根节点

知道上面三点就可以了,具体做法如下:
1.A是整棵树的根节点
2.在中序序列中找到A的位置,位于A左边的序列是整棵树的左子树结点,位于A右边的是整棵树的右子树结点。
3.再选择前序遍历的下一个结点B,重复上述过程,直到遍历完为止。

确定树的过程可以用以下图来描述:

不难看出,后序遍历:DEBGFCA
编辑于 2017-03-03 17:09:01 回复(0)
                                    A
                                 /      \
                              B         C
                            /            /
                         D           F
                            \            \
                             E            G

EDBGFCA
发表于 2016-12-31 00:50:12 回复(0)