某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,求大神给出二叉树的排列
张凯欣 核心会员 2016-08-04 11:09:50
8891 3 0

有过程最好了,谢谢

问题来自: 二叉树的遍历

共 3 个回答

    赛赛 进阶大师 1431天前


    这个图是这道题的正确画法,满意请采纳,谢谢亲的支持!≥^.^≤

    最佳答案

    纪念& 资深达人 1431天前

          由先序序列ABCDEFG,可知,该树的根为A,由中序DCBAEFG可知,A前面的DCB为该树的左子树,A后面的EFG的其右子树。

          继续分析,原序列先序被分为两组BCD和EFG,中序分别为DCB和EFG,先序BCD,中序DCB,所以这棵以A为根的树的左子树,其根为B,又因为中序DCB,所以D、C为B节点的左子树,又因为先序BCD,所以C为D的节点,D为C的左子树。

           又因为先序EFG,中序EFG,所以这棵以A为根的树的右子树,其根为E,F、G为其右子树,且F为节点,G为右子树。

    如下图所示:


    满意请采纳,谢谢!


    纪念& 资深达人 1431天前

       由先序序列ABCDEFG,可知,该树的根为A,由中序DCBAEFG可知,A前面的DCB为该树的左子树,A后面的EFG的其右子树。

          继续分析,原序列先序被分为两组BCD和EFG,中序分别为DCB和EFG,先序BCD,中序DCB,所以这棵以A为根的树的左子树,其根为B,又因为中序DCB,所以D、C为B节点的左子树,又因为先序BCD,所以C为D的节点,D为C的左子树。

           又因为先序EFG,中序EFG,所以这棵以A为根的树的右子树,其根为E,F、G为其右子树,且F为节点,G为右子树。

    如下图所示:

                       A

                     /   \

                  B        E

                 /           \

              C               F

             /                  \

          D                     G


    满意请采纳,谢谢!


您还没有登录,所以不能回复该问题
我要回复

  • 0

    点赞

  • 扫一扫分享朋友圈

    二维码

  • 分享

相关问题