全部问题 > 当前问题

某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,求大神给出二叉树的排列

有过程最好了,谢谢

张凯欣 2016-8-4 11:09:50

共 3 个回答

赛赛 2016-8-4 11:29:17


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

最佳答案

纪念& 2016-8-4 15:01:22

      由先序序列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为右子树。

如下图所示:


满意请采纳,谢谢!


纪念& 2016-8-4 15:05:14

   由先序序列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


满意请采纳,谢谢!


问题来自: 二叉树的遍历