专栏首页五分钟学算法【图解数据结构】 一组动画彻底理解二叉树遍历

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

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

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

前提

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

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

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

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

前序遍历

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

  • 先访问根节点
  • 再序遍历左子树
  • 最后序遍历右子树

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

  • 首先访问了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
  • 。。。

代码实现:

本文分享自微信公众号 - 五分钟学算法(blgczzz),作者:菠了个菜

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一算:Contains Duplicate II

    五分钟学算法
  • 初识广度优先搜索与解题套路

    先来看看其中比较简单的数据结构 - 链表,它和数组类似,也是一个线性的结构,简单来说就是一条路径,你从头开始遍历,最终会将链表上面的节点都访问到,到达终点。

    五分钟学算法
  • 每天一算:二叉树的层次遍历

    五分钟学算法
  • 遍历

    前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    Centy Zhao
  • 图的深度遍历和广度遍历

    图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的...

    233333
  • 前序遍历中序遍历求后序遍历-数组篇

    如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

    chain
  • LeetCode | 100.相同的树

    上面的题就是 相同的树 题目的截图,同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义,然后在其中实现 相同的树 的解题过程。这次我使用 ...

    码农UP2U
  • 如何根据二叉树的两种遍历方式重建二叉树(理论篇)

    我们知道,二叉树有三种不同的遍历方式:先序遍历,中序遍历和后序遍历。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就...

    青南
  • 5分钟轻松理解二叉树的深度遍历策略

    我们知道普通的线性数据结构如链表,数组等,遍历方式单一,都是从头到尾遍历就行,但树这种数据结构却不一样,我们从一个节点出发,下一个节点却有可能遇到多个分支路径,...

    我是攻城师
  • 每日一题 | QQ群撩妹问题

    codeforces的B题,链接:https://codeforces.com/contest/1395/problem/B

    TechFlow-承志

扫码关注云+社区

领取腾讯云代金券