二叉树(2)- 遍历二叉树

有任何问题,欢迎交流!微博@HelloWorld-_-
接着创建二叉树文章说一说遍历二叉树的几种方法


二叉树遍历方法

众所周知,二叉树的遍历方法分为4类,分别为先序遍历、中序遍历、后序遍历和分层遍历。记得当初学习二叉树的时候,对先序遍历、中序遍历和后序遍历总是混淆(上课时没认真听讲),忘记访问的顺序,后来自己归纳总结了两点,然后就再也没忘记过,下面来介绍下我的记忆小窍门

  1. 先、中、后代表的位置
  2. 子节点的顺序是从左至右不变

先序遍历:根、左子树、右子树
中序遍历:左子树、根、右子树
后序遍历:左子树、右子树、根

好了下面通过示例,再描述下二叉树遍历的过程。


分层遍历

最容易理解的就是分层遍历分层遍历按照从上至下、从左至右的顺序依次访问每个结点。下面通过一个示意图来表示二叉树分层遍历顺序

分层遍历二叉树结果:ABCDEF
分层遍历访问结点顺序

先序遍历

首先回忆下先序遍历的规则:根、左子树、右子树。根据规则,首先访问根A,然后是左子节点B,再访问完B后,并不是直接去访问A右子节点C,因为A的左子树还没有访问完,所以下面访问的节点是D节点D没有子节点,所以接着访问结点E。当访问完节点E后,根A的整个左子树访问完毕,接下来开始访问A右子节点C,后面的访问顺序同节点B

先序遍历二叉树结果:ABDECFG
先序遍历访问节点顺序

中序遍历

回忆下中序遍历的规则:左子树、根、右子树。根据规则,首先判断节点A,因为A根节点,所以接下来判断其左子结点B节点B相对于节点D、E来说,也是根节点,所以继续判断节点B左子结点D节点D是叶子节点,所以第一个访问的是节点D。访问完节点D后,节点B左子树都访问完成,然后紧接着访问结点B节点E。访问完节点E后,节点A左子树都访问完成,然后访问节点A,紧接着同理访问节点A的右子树。

中序遍历二叉树结果:DBEAFCG 
中序遍历访问结点顺序

后序遍历

后序遍历的规则:左子树、右子树、根。同理中序遍历的分析过程。

后序遍历二叉树结果:DEBFGCA
后序遍历访问结点顺序

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,491评论 1 31
  • 数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比,二叉树有如下特点: 每个结点最多只有两棵子...
    sunhaiyu阅读 6,532评论 0 14
  • 四、树与二叉树 1. 二叉树的顺序存储结构 二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有...
    MinoyJet阅读 1,592评论 0 7
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,355评论 0 25
  • 树和二叉树 1、树的定义 树(Tree)是由一个 或 多个结点 组成的有限集合T,且满足: ①有且仅有一个称为根的...
    利伊奥克儿阅读 1,399评论 0 1