理解二叉树的四种遍历-前序、中序、后序、层序

一、易懂的形象理解

其实从名字就可以很好的理解这三种遍历,我在第二点时候说,但是估计能翻到我的文的同学们之前肯定看过好多类似的了,那咱们换个思路~ 先用我想的一种简单易懂的形象思维理解一下前序、中序、后序 +层序!

1、先序遍历

先序遍历可以想象成,小人从树根开始绕着整棵树的外围转一圈,经过结点的顺序就是先序遍历的顺序
先序遍历结果:ABDHIEJCFKG

1

让我们来看下动画,和小人儿一起跑两遍就记住啦,记住是绕着外围跑哦

2

3

2、中序遍历

中序遍历可以想象成,按树画好的左右位置投影下来就可以了
中序遍历结果:HDIBEJAFKCG
4
下面看下投影的过程动画,其实就是按左右顺序写下来就行了
5

3、后序遍历

后序遍历就像是剪葡萄,我们要把一串葡萄剪成一颗一颗的。
还记得我们先序遍历绕圈的路线么?
就是围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄),就把它剪下来,组成的就是后序遍历了。
后序遍历结果:HIDJEBKFGCA
6
让我们来看下动画
7

4、层序遍历

层序遍历太简单了,就是按照一层一层的顺序,从左到右写下来就行了。
后序遍历结果:ABCDEFGHIJK
8

不知道通过这种方式,有没有觉得闭着眼睛都能写出前序、中序、后序 、层序了呀,不过这只是为了大家好理解,我想出的一种形象思维,为了用代码实现,我们还需要具体了解一下前序、中序、后序遍历。

二、真正理解三种遍历

来,让我们先把所有空结点都补上。
还记得我们先序和后序遍历时候跑的顺序么?按照这个顺序再跑一次,就是围着树的外围跑一整圈
让我们来理解一下绕着外围跑一整圈的真正含义是:遍历所有结点时,都先往左孩子走,再往右孩子走。
9
观察一下,你有什么发现?
有没有发现,除了根结点和空结点,其他所有结点都有三个箭头指向它。
一个是从它的父节点指向它,一个是从它的左孩子指向它,一个是从它的右孩子指向它
一个结点有三个箭头指向它,说明每个结点都被经过了三遍。一遍是从它的父节点来的时候,一遍是从它的左孩子返回时,一遍是从它的右孩子返回时

其实我们在用递归算法实现二叉树的遍历的时候,不管是先序中序还是后序,程序都是按照上面那个顺序跑遍所有结点的
先序中序和后序唯一的不同就是,在经过结点的三次中,哪次访问(输出或者打印或者做其他操作)了这个结点。有点像大禹治水三过家门,他会选择一次进去。
先序遍历顾名思义,就是在第一次经过这个结点的时候访问了它。就是从父节点来的这个箭头的时候,访问了它。
中序遍历也和名字一样,就是在第二次经过这个结点的时候访问了它。就是从左孩子返回的这个箭头的时候,访问了它。
后序遍历,就是在第三次经过这个结点的时候访问了它。就是从右孩子返回的这个箭头的时候,访问了它。

怎么样,这样有没有很好的理解?其实不管是前序中序还是后序,在程序里跑的时候都是按照同样的顺序跑的,每个结点经过三遍,第几遍访问这个结点了,就叫什么序遍历。
当我们脑子里有这个概念的时候, 再去看实现代码就很好理解了,下一篇博文我会贴出和讲解具体的实现代码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>