回 帖 发 新 帖 刷新版面

主题:[讨论]帮我计算下这个二叉树的前序序列,拜托大家啦。。

某二叉树中序序列为A,B,C,D,E,F,G,后序序列为。 B,D,C,A,F,G,E 则前序序列是?
是不是题目有错呢,但这是老师的课件的题目,拜托大家和我讲讲。。

回复列表 (共1个回复)

沙发

解题思路:根据二叉树的中序和后序的性质来解。
中序:左-根-右    后序:左-右-根
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

我来回复

您尚未登录,请登录后再回复。点此登录或注册