二叉树三种遍历方法(根据两种排序求第三种的顺序)
博客专区 > RainOrz 的博客 > 博客详情
二叉树三种遍历方法(根据两种排序求第三种的顺序)
RainOrz 发表于2周前
二叉树三种遍历方法(根据两种排序求第三种的顺序)
  • 发表于 2周前
  • 阅读 20
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

1.已知先序和中序求后序

     先序遍历的节点顺序是:ADCEFGHB,中序遍历是CDFEGHAB,则后序遍历的结果是  CFHGEDBA

解:1)根据先序遍历结果可知A是根节点,根据中序遍历知道A的左子树是(CDFEGH),右子树是(B)

      2)左边中D是根节点,由中序遍历的顺序CD知道,C是D的左子树;

           E是D的右子树,由中序遍历的顺序FE知道,F是E的左子树;

           G是E的右子树,由中序遍历的顺序GH知道,H是G的右子树

      3)故二叉树的图为 

                                         A

                                       /    \

                                     D       B    

                                    /   \ 

                                  C     E

                                       /   \

                                      F    G

                                              \

                                               H

     4)由图知道后序遍历的结果是CFHGEDBA

2. 已知后序和中序求先序

       后序遍历是DABEC,中序遍历是DEBAC,则先序遍历是CEDBA

解:1)根据后序遍历结果知道C是根节点,根据中序遍历知道C的左子树是DEBA,没有右子树

       2)左边E是根节点,由中序遍历DE知道,D是E的左子树

            B是E的右子树,A是B的右子树

       3)故二叉树的图为 

                                       C

                                     /    \

                                   E

                                 /   \

                                D    B

                                        \

                                         A

      4)由图知道先序遍历的结果是CEDBA

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 7
博文 73
码字总数 69345
×
RainOrz
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: