【图解数据结构】 一组动画彻底理解二叉树三种遍历

栏目: 数据库 · 发布时间: 5年前

内容简介:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。接下来我将尝试着用三组动画向读者详细的介绍这三种遍历方式的逻辑思路,希望让读者看到任何的二叉树都能在脑海中快速的勾勒出动画。在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。接下来我将尝试着用三组动画向读者详细的介绍这三种遍历方式的逻辑思路,希望让读者看到任何的二叉树都能在脑海中快速的勾勒出动画。

前提

在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。

【图解数据结构】 一组动画彻底理解二叉树三种遍历

如图所示是二叉树中的一个节点,这个节点有左子树与右子树,通过两根绿色的连接线,将此节点划分成了三个区域,我们分别用前、中、后这三个辅助点来表示。

这三个点表明在二叉树的遍历中什么时候要取出此节点的值。

任何一个节点去遍历都是 前-左绿线-中-右绿线-后 这样的顺序遍历的。

前序遍历

使用递归方式实现前序遍历的具体过程为:

  • 先访问根节点
  • 再序遍历左子树
  • 最后序遍历右子树
【图解数据结构】 一组动画彻底理解二叉树三种遍历

我们来对上面的动画进行一个充分的说明来理解前序遍历的递归实现方式。

  • 首先访问了 28 这个节点,我们看 前辅助点 ,由于是前序遍历,那么此刻我们取出该节点的值 28
  • 而后通过左绿线访问 28 的左子树
  • 16 这个节点中,我们看 前辅助点 ,由于是前序遍历,取出该节点的值 16
  • 通过左绿线访问 16 的左子树
  • 13 这个节点中,我们看 前辅助点 ,由于是前序遍历,取出该节点的值 13
  • 13 这个节点左子树为空,那么我们左绿线就没有,然后看 中辅助点 ,由于是前序遍历,因此不做处理
  • 13 这个节点右子树为空,那么我们右绿线就没有,然后看 后辅助点 ,由于是前序遍历,因此不做处理
  • 而后回到 16 这个节点中,看 中辅助点 ,由于是前序遍历,因此不做处理
  • 而后看 16 这个节点的右子树 22 这个节点,看 前辅助点 ,由于是前序遍历,取出该节点的值 22
  • 。。。

代码实现:

【图解数据结构】 一组动画彻底理解二叉树三种遍历

中序遍历

使用递归方式实现中序遍历的具体过程为:

  • 先中序遍历左子树
  • 再访问根节点
  • 最后中序遍历右子树
【图解数据结构】 一组动画彻底理解二叉树三种遍历

我们来对上面的动画进行一个充分的说明来理解中序遍历的递归实现方式。

  • 首先访问了 28 这个节点,我们看 前辅助点 ,由于是中序遍历,因此不做处理
  • 而后通过左绿线访问 28 的左子树
  • 16 这个节点中,我们看 前辅助点 ,由于是中序遍历,因此不做处理
  • 通过左绿线访问 16 的左子树
  • 13 这个节点中,我们看 前辅助点 ,由于是中序遍历,因此不做处理
  • 13 这个节点左子树为空,那么我们左绿线就没有,然后看 中辅助点 ,由于是中序遍历,取出该节点的值 13
  • 13 这个节点右子树为空,那么我们右绿线就没有,然后看 后辅助点 ,由于是中序遍历,因此不做处理
  • 而后回到 16 这个节点中,看 中辅助点 ,由于是中序遍历,取出该节点的值 16
  • 而后看 16 这个节点的右子树 22 这个节点,看 前辅助点 ,由于是中序遍历,因此不做处理
  • 中辅助点 ,由于是中序遍历,取出该节点的值 22
  • 。。。

代码实现:

【图解数据结构】 一组动画彻底理解二叉树三种遍历

后序遍历

使用递归方式实现后序遍历的具体过程为:

  • 先后序遍历左子树
  • 再后序遍历右子树
  • 最后访问根节点
【图解数据结构】 一组动画彻底理解二叉树三种遍历

我们来对上面的动画进行一个充分的说明来理解后序遍历的递归实现方式。

  • 首先访问了 28 这个节点,我们看 前辅助点 ,由于是后序遍历,因此不做处理
  • 而后通过左绿线访问 28 的左子树
  • 16 这个节点中,我们看 前辅助点 ,由于是后序遍历,因此不做处理
  • 通过左绿线访问 16 的左子树
  • 13 这个节点中,我们看 前辅助点 ,由于是后序遍历,因此不做处理
  • 13 这个节点左子树为空,那么我们左绿线就没有,然后看 中辅助点 ,由于是后序遍历,因此不做处理
  • 13 这个节点右子树为空,那么我们右绿线就没有,然后看 后辅助点 ,由于是后序遍历,取出该节点的值 13
  • 而后回到 16 这个节点中,看 中辅助点 ,由于是后序遍历,因此不做处理
  • 而后看 16 这个节点的右子树 22 这个节点,看 前辅助点 ,由于是中序遍历,因此不做处理
  • 中辅助点 ,由于是后序遍历,因此不做处理
  • 后辅助点 ,由于是后序遍历,取出该节点的值 16
  • 。。。

以上所述就是小编给大家介绍的《【图解数据结构】 一组动画彻底理解二叉树三种遍历》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

疯传

疯传

乔纳·伯杰 (Jonah Berger) / 刘生敏、廖建桥 / 电子工业出版社 / 2014-1-1 / CNY 48.00

《疯传:让你的产品、思想、行为像病毒一样入侵》内容简介:是什么让事物变得流行?从买轿车、买衣服、吃三明治,到给孩子取名字,你是否知道为什么某些产品会大卖,某些故事被人们口口相传,某些电子邮件更易被转发,或者某些视频链接被疯狂地点击,某些谣言更具传播力,某些思想和行为像病毒一样入侵你的大脑……《疯传:让你的产品、思想、行为像病毒一样入侵》这本书将为你揭示这些口口相传和社会传播背后的科学秘密,并且告诉......一起来看看 《疯传》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具