二叉树三种遍历数据结构图解及代码实现

2018-11-1916:50:06数据结构与算法Comments4,092 views字数 1553阅读模式

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。接下来我将尝试着用三组动画向读者详细的介绍这三种遍历方式的逻辑思路,希望让读者看到任何的二叉树都能在脑海中快速的勾勒出动画。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

前提

在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

二叉树三种遍历数据结构图解及代码实现

如图所示是二叉树中的一个节点,这个节点有左子树与右子树,通过两根绿色的连接线,将此节点划分成了三个区域,我们分别用前、中、后这三个辅助点来表示。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

这三个点表明在二叉树的遍历中什么时候要取出此节点的值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

任何一个节点去遍历都是 前-左绿线-中-右绿线-后 这样的顺序遍历的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

前序遍历

使用递归方式实现前序遍历的具体过程为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

  • 先访问根节点
  • 再序遍历左子树
  • 最后序遍历右子树
二叉树三种遍历数据结构图解及代码实现

我们来对上面的动画进行一个充分的说明来理解前序遍历的递归实现方式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

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

代码实现:

二叉树三种遍历数据结构图解及代码实现

中序遍历

使用递归方式实现中序遍历的具体过程为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

  • 先中序遍历左子树
  • 再访问根节点
  • 最后中序遍历右子树
二叉树三种遍历数据结构图解及代码实现

我们来对上面的动画进行一个充分的说明来理解中序遍历的递归实现方式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

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

代码实现:

二叉树三种遍历数据结构图解及代码实现

后序遍历

使用递归方式实现后序遍历的具体过程为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

  • 先后序遍历左子树
  • 再后序遍历右子树
  • 最后访问根节点
二叉树三种遍历数据结构图解及代码实现

我们来对上面的动画进行一个充分的说明来理解后序遍历的递归实现方式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

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

代码实现:

二叉树三种遍历数据结构图解及代码实现

作者:MisterBooo
来源:掘金文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7899.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/7899.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定