专栏首页孙小白二叉树的先序、中序、后序遍历【重点】

二叉树的先序、中序、后序遍历【重点】

二叉树操作:

  一. 已知两种遍历序列求原始二叉树

  二. 遍历:

    1. 先序遍历(先访问根节点)

      先访问根节点

      再先序访问左子树

      再先序访问右子树

    访问左子树步骤:

      1. 从根节点A开始

      2. 访问A的左子树(以B为根节点的树)

      3. 访问B的左子树(以D为根节点的树)

      4. 访问D的左子树,为空

      5. 访问D的右子树,为空,D访问完毕,意味着B的左子树访问完了

      6. 返回到B,访问B的右子树,为空,B访问完毕,意味着A的左子树访问完了

      7. 返回到A

    即左子树遍历为A-B-D

    访问右子树:

      操作与上相同,最后A的右子树访问完毕,意味着整棵树访问完毕

    最终遍历结果是:A-B-D-C-E-F-G

    2. 中序遍历(中间访问根节点)

      先遍历左子树

      再访问根节点

      再中序遍历右子树

操作:

1. 从根节点A的左子树(以B为根节点)开始

2. 访问B的左子树,为空

3. 访问根节点B

4. 访问B的右子树(以C为根节点)

5. 访问C的左子树(以D为根节点)

6. 访问D的左子树,为空

7. 访问根节点D

8. 访问D的右子树,为空,D访问完毕

9. 返回到C,访问根节点C

10. 访问C的右子树(以E为根节点)

11. 访问E的左子树,为空

12. 访问根节点E

13. 访问E的右子树,为空,E访问完毕

14. 返回到C,C访问完毕

15. 返回到B,B访问完毕

16. 返回到A,访问根节点A

17. 访问A的右子树(以F为根节点)……操作同上

最终结果:B-D-C-E-A-L-F-N-Q-M

    3. 后序遍历(最后访问根节点)

先遍历左子树

再遍历右子树

再访问根节点

操作:

1. 先访问A的左子树(以B为根节点)

2. 访问B的左子树,为空;访问B的右子树,为空;访问根节点B,访问完毕

3. 返回到A,访问A的右子树(以C为根节点)

4. 访问C的左子树(以D为根节点)

5. 访问D的左子树,为空;访问D的右子树,为空;访问根节点D,访问完毕

6. 返回到C,访问C的右子树(以E为根节点)

7. 访问E的左子树(以F为根节点)

8. 访问F的左子树(以M为根节点)

9. 访问M的左子树,为空;访问M的右子树,为空;访问根节点M,访问完毕

10. 返回到F;访问F的右子树,为空;访问根节点F,访问完毕

11. 返回到E;访问E的右子树(以L为根节点)

12. 访问L的左子树,为空;访问L的右子树,为空;访问根节点L,访问完毕

13. 返回到E,访问根节点E,访问完毕

14. 返回到C,访问根节点C,访问完毕

15. 返回到A,访问根节点A,访问完毕

最终结果是:B-D-M-F-L-E-C-A

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 虚拟机centos与主机互相Ping通

    在虚拟机(Vmware Workstation)下,安装了CentOS7,现在想通过SSH工具连接虚拟机中的CentOS7

    爱学习的孙小白
  • 跨函数使用内存案例

    爱学习的孙小白
  • 链式二叉树具体程序演示

    爱学习的孙小白
  • 第3阶段——内核启动分析之make menuconfig内核配置(2)

    目标: 分析make menuconfig内核配置过程 在上1小结中(内核编译试验)讲到了3种不同的配置: (1)通过make menuconfig 直接从头到...

    张诺谦
  • 第3阶段——内核启动分析之make menuconfig内核配置(2)

    目标: 分析make menuconfig内核配置过程 在上1小结中(内核编译试验)讲到了3种不同的配置: (1)通过make menuconfig 直接从头到...

    张诺谦
  • 多态 接口重用,一种接口,多种实现 实例 ? 多态 静态方法 @staticmethod 在函数前边加修饰@ 为了 让这个方法和类没关系 @c...

    98k
  • 趣图:编译代码时,程序员的心跳变化

    编译代码时,程序员的心跳变化 ?

    程序员宝库
  • JavaScript 标准内置对象Promise使用学习总结

    .catch将在new Promise时定义的匿名函数执行失败、.then函数执行失败,并且位于其后的then函数没有显示提供第二个参数(供失败时调用的函数)时...

    授客
  • 【转】记一次TIME_WAIT网络故障

    前段时间,组里遇到个问题:线上某个业务出现了短连接太多,造成tw_bucket溢出。

    二狗不要跑
  • Python函数参数传递机制

            最近在写代码的过程中,发现Python参数传递不是很明白。Python确实很灵活,但是灵活的后果就是要花更多的时间去研究。废话不多说,始めましょ...

    用户2398817

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动