【图解数据结构】 一组动画彻底理解二叉树遍历
前提
在介绍这三组动画前,我们先用图来介绍一下二叉树的创建以及动画中的一些约定说明。
如图所示是二叉树中的一个节点,这个节点有左子树与右子树,通过两根绿色的连接线,将此节点划分成了三个区域,我们分别用前、中、后这三个辅助点来表示。
这三个点表明在二叉树的遍历中什么时候要取出此节点的值。
任何一个节点去遍历都是 前-左绿线-中-右绿线-后 这样的顺序遍历的。
前序遍历
使用递归方式实现前序遍历的具体过程为:
先访问根节点
再序遍历左子树
最后序遍历右子树
我们来对上面的动画进行一个充分的说明来理解前序遍历的递归实现方式。
首先访问了
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简短而安全的数组遍历
- 为什么推荐使用for-each而不是for循环遍历元素?
- jQuery遍历祖先元素:parentsUntil
- jQuery在点击按钮上迭代/循环遍历数据表
- jQuery遍历----------(遍历、祖先、后代、同胞、过滤)
- jQuery遍历Table tr td td中包含标签