一文弄懂二叉树三种遍历
作者 | 菠了个菜
责编 | 屠敏
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。本文笔者将尝试着以图文结合的方式向读者详细的介绍这三种遍历方式的逻辑思路,希望让读者看到任何的二叉树都能在脑海中快速的勾勒出动画。
前提
在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。
如图所示是二叉树中的一个节点,这个节点有左子树与右子树,通过两根绿色的连接线,将此节点划分成了三个区域,我们分别用前、中、后这三个辅助点来表示。
这三个点表明在二叉树的遍历中什么时候要取出此节点的值。
任何一个节点去遍历都是:前-左绿线-中-右绿线-后,这样的顺序遍历的。
前序遍历
使用递归方式实现前序遍历的具体过程为:
先访问根节点
再序遍历左子树
最后序遍历右子树
我们来对上图进行一个充分的说明来理解前序遍历的递归实现方式。
首先访问了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
代码实现:
作者简介:菠了个菜,本文首发于个人公众号“五分钟学算法”。“五分钟学算法”是致力于通过各种动画的形式来描绘出各种数据结构,并图解 LeetCode 原题的学习平台。
本文系作者投稿,版权归作者所有。
热 文推 荐
喜欢就点击“好看”吧!
相关文章
- 中国移动联通电信停止支持eSIM服务 运营商esim一号双终端最新进展消息! 还会恢复吗?
- 华为新手机最新款2023即将新发布上市5G公认最好的折叠手机价格参数
- 抖音里的商城购物车怎么突然没有了?
- 苹果iPhone总销量公布:共卖出15亿台,卖得最好是哪一款?
- 华为首款5G折叠屏手机什么时候发布的 5G折叠屏手机详细配置参数处理器一览 手机笔记本双形态!
- 三星S10什么时候正式发布价格是多少钱?S10配置参数处理器屏幕外观详细分享 挖孔屏+顶尖屏幕,价格大部分人无法接受!
- 华为5G折叠屏手机什么时候在巴展发布价格是多少钱?5G折叠屏手机配置参数处理器详细分享
- 小米9和小米6很像,米9和米6的设计师是同一个人吗?似乎对米9的颜值多了一丝期待
- 2022年新低价荣耀Magic2乞丐版值得买入手吗?配置参数处理器怎么样
- 神舟RTX2060新品会在开学换新季迎来史上最低价吗?神舟RTX2060冰点价攻略