二叉树的遍历问题

论坛 期权论坛 期权     
exulter   2018-4-26 14:01   4289   4
若某二叉树的前序遍历访问顺序为abdgcefh,中序遍历访问顺序是dgbaechf,则后序遍历的结点访问顺序是______。
分享到 :
0 人收藏

4 个回复

倒序浏览
2#
418470439  1级新秀 | 2018-4-30 01:55:02 发帖IP地址来自
你好!首先,我们来看前序遍历为abdgcefh,根据前序遍历的规则(先根节点,其次遍历左子树,最好遍历右子树)可知,a为根节点。又知中序遍历访问顺序是dgbaechf,那么可以判断出左子树的结构:
               a
              /
             g
        /        \
     d            b
又根据中序遍历的规则(先中序遍历左子树,之后为根节点,最好中序遍历右子树)可得到整个二叉树的结构为:
                      a
              /               \
             g                e
        /        \               \
     d            b             h
                             /         \
                            c            f
既然推出了二叉树的结构图,那么要求后序遍历就显而易见了,已知后序遍历规则(先后序遍历左子树,再后序遍历右子树,最好访问根节点):abgcfhea
初学者最容易将中序遍历弄错,特别是在考虑如本题中e和f的位置时往往会把握不住,多练习几次,并且记住你就一定能做对的!因为我就是初学者.....
3#
宋川笨蛋  4级常客 | 2018-4-30 01:55:03 发帖IP地址来自
adbgecfh
4#
可乐堕天猫  4级常客 | 2018-4-30 01:55:04 发帖IP地址来自
前序是先中间后左右
所以a是根节点 用a将右边的中序序列分成两个部分 左边是左子树 右边是右子树
根据这种方式就可以推出树的形状 进而写出后序序列
树的形状是
             a
       b           c
d               e      f
    g                 h
5#
rain_rainsky  2级吧友 | 2018-4-30 01:55:05 发帖IP地址来自
所谓先序 中序和后序遍历都是以根节点分的  先序就是把根节点放在前面 中序为根节点在中间 后序为根节点在后面 对于你的问题 由先序遍历为abdgcefh可以得知该二叉树的根节点为a  由中序遍历为dgbaechf可以dgb在根节点的左边 echf在根节点的右边 再对dgb 可知其跟节点为b   同理可知echf的根节点为c  然后再一层一层的分析下去 可得出该二叉树 最后求出后序遍历
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP