内容简介:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。接下来我将尝试着用三组动画向读者详细的介绍这三种遍历方式的逻辑思路,希望让读者看到任何的二叉树都能在脑海中快速的勾勒出动画。在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。接下来我将尝试着用三组动画向读者详细的介绍这三种遍历方式的逻辑思路,希望让读者看到任何的二叉树都能在脑海中快速的勾勒出动画。
前提
在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。
如图所示是二叉树中的一个节点,这个节点有左子树与右子树,通过两根绿色的连接线,将此节点划分成了三个区域,我们分别用前、中、后这三个辅助点来表示。
这三个点表明在二叉树的遍历中什么时候要取出此节点的值。
任何一个节点去遍历都是 前-左绿线-中-右绿线-后 这样的顺序遍历的。
前序遍历
使用递归方式实现前序遍历的具体过程为:
- 先访问根节点
- 再序遍历左子树
- 最后序遍历右子树
我们来对上面的动画进行一个充分的说明来理解前序遍历的递归实现方式。
- 首先访问了
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
- 。。。
以上所述就是小编给大家介绍的《【图解数据结构】 一组动画彻底理解二叉树三种遍历》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数据结构-二叉树遍历
- 【PHP 实现数据结构】遍历二叉查找树
- 数据结构基础:根据先序、中序遍历结果构造二叉树
- 数据结构 2 字符串 数组、二叉树以及二叉树的遍历
- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——遍历和删除
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。