[阿里巴巴2015研发工程师B] 二叉树已知前序中序遍历,求后序

已知一个二叉树的前序遍历结果是(ACDEFHGB) ,中序遍历结果是(DECAHFBG),请问后续遍历结果是 __

A.HGFEDCBA
B.EDCHBGFA
C.BGFHEDCA
D.EDCBGHFA
E.BEGHDFCA
F.BGHFEDCA

感谢您为本话题评分。
共有4个回答
  • 0
    Gonn - 2014-09-29 不喜欢

    先补充点基础知识吧。

    前序遍历(DLR)是二叉树遍历的一种,也叫做先根遍历、先序遍历。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。

    比如以下二叉树:

    它的前序遍历结果为:ABDECF

    而后序遍历首先遍历左子树,然后遍历右子树,最后遍历访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。

    还是上面的二叉树,它的后序遍历结果:DEBFCA

    而中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。

    中序遍历结果:DBEAFC。

  • 0
    Gonn - 2014-09-29 不喜欢

    基础补完之后,我们来讲解解题步骤:
    前序遍历:ACDEFHGB
    中序遍历:DECAHFBG

    1. 第一步,根据前序遍历的特点,我们知道根结点为A。
    2. 第二步,观察中序遍历DECAHFBG,可知,其中root节点A左侧的DEC必然是root的左子树,A右侧的HFBG必然是root的右子树。
    3. 第三步,观察左子树DEC,左子树的中的根节点必然是大树的root的leftchild。在前序遍历中,大树的root的leftchild位于root之后,所以左子树的根节点为C(前序的CDE的首字母)。
    4. 然后DE为C的右子树。
    5. 同样的道理,root的右子树节点HFBG中的根节点也可以通过前序遍历求得。在前序遍历中,一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树,并且遍历的左子树的第一个节点就是左子树的根节点。同理,遍历的右子树的第一个节点就是右子树的根节点。
    6. FHGB中,F为首字母,所以必定是右子树的根节点。
    7. 观察中序里的HFBG,H为F的左子树,BG为右子树。
    8. 观察前序里的GB,G在前面,所以G为节点,B的树。
    9. 至此,整棵树已分析完毕。

                 A
             C         F
          D          H      G
       E                        B

    具体图就不画了,大概就像上面一样。
    所以后序遍历为:EDC H BG FA

  • 0
    Gonn - 2014-09-29 不喜欢

    所以这道题 选B

  • 0
    叶青云 - 2016-07-21 不喜欢

    这个好

以下是预览效果,请确认排版好了再点回复。
如果你认为此话题有广告、灌水的嫌疑,请给此话题评一颗星。平均分低的话题将不会再显示。
良好的讨论氛围由大家共同维护。