主题:[讨论]帮我计算下这个二叉树的前序序列,拜托大家啦。。
依然饰我
[专家分:0] 发布于 2008-11-19 18:07:00
某二叉树中序序列为A,B,C,D,E,F,G,后序序列为。 B,D,C,A,F,G,E 则前序序列是?
是不是题目有错呢,但这是老师的课件的题目,拜托大家和我讲讲。。
沙发
nw0220 [专家分:20] 发布于 2008-11-26 07:57:00
解题思路:根据二叉树的中序和后序的性质来解。
中序:左-根-右 后序:左-右-根
1、从后序序列的最后一个节点确定根节点是E
2、根据E是根点,从中序序列可分为E的两颗子树:左子树1(A、B、C、D)、右子树1(F、G)
3、右子树1的后序序列是(F、G),所以G是右子树1的根
4、右子树1的中序序列是(F、G),所以F是G的左叶子
....
以此类推,求得左子树1的架构。
最后得出的二叉树是这样的:
E
A G
C F
B D
所以前序序列是:EACBDGF