我们在数据结构的学习中,都接触过二叉树。二叉树常用的遍历方法包括:前序遍历、中序遍历、后序遍历以及层次遍历。其中前三种遍历方法均可以通过递归或者迭代实现。递归实现难度较小,而且写出来的代码简洁明了;迭代实现起来则具有一定难度。在这篇文章中,我就来总结一下利用迭代遍历二叉树的方法。
一、前序遍历
二叉树的前序、中序和后序遍历都是通过栈来实现的,而前序遍历则是其中最简单的。所谓前序遍历,指的是对于每个结点,先访问该结点本身,然后访问左子树,最后访问右子树。为了进行前序遍历,我们初始化一个空栈存储二叉树的结点。首先令根结点入栈。每当栈不为空,弹出栈顶的结点并访问该结点,然后依次将其右儿子、左儿子入栈(如果不为NULL
)。注意入栈的顺序是先右儿子,再左儿子。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
二、中序遍历
所谓中序遍历,指的是对于每个结点,先访问左子树,然后访问该结点本身,最后访问右子树。为了进行中序遍历,我们需要维持两个栈,一个栈存储二叉树的结点,另一个栈则是标记栈,存储结点栈中相应结点的标记,标记的取值可能为0或1。
首先,我们令根结点入栈(标记为0)。每当栈不为空,我们弹出栈顶结点及其标记:如果该结点的标记为0,则令该结点再次入栈(标记为1),并且如果该结点有左儿子,将其左儿子入栈(标记为0);如果该结点的标记为1,则访问该结点,并且如果该结点有右儿子,将其右儿子入栈(标记为0)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
三、后序遍历
所谓后序遍历,指的是对于每个结点,先访问左子树,然后访问右子树,最后访问该结点本身。后序遍历的实现思路和中序遍历类似,仍然是维持一个结点栈和一个标记栈,不同之处在于标记的取值可能为0、1或2。
首先,我们令根结点入栈(标记为0)。每当栈不为空,我们弹出栈顶结点及其标记:如果该结点的标记为0,则令该结点再次入栈(标记为1),并且如果该结点有左儿子,将其左儿子入栈(标记为0);如果该结点的标记为1,则令该结点再次入栈(标记为2),并且如果该结点有右儿子,将其右儿子入栈(标记为0);如果该结点的标记为2,则访问该结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
另外需要注意的是,通过一棵二叉树的前序与中序,或者中序与后序遍历序列是可以重建这棵二叉树的。比如一棵二叉树的前序与中序遍历序列如下:
前序遍历序列:a,b,e,c,f,g
;
中序遍历序列:b,e,a,f,c,g
。
我们知道,前序遍历序列的结点顺序为根结点、左子树、右子树;中序遍历为左子树、根结点、右子树;后序遍历则为左子树、右子树、根结点。通过这个结论,我们可以知道结点a
为二叉树的根结点,所以在中序遍历序列中,位于a
前面的序列b,e
就是左子树的中序遍历序列,位于a
后面的序列f,c,g
则是右子树的中序遍历序列。另外我们可以确定,左右子树的大小分别为2和3,所以在前序遍历序列中,a
后面的2个结点b,e
就是左子树的前序遍历序列,再后面的3个结点c,f,g
就是右子树的前序遍历序列。
然后我们对左右子树分别进行递归调用,即可重建这棵二叉树。
四、层次遍历
如果说前序遍历类似于图的深度优先搜索,那么层次遍历则类似于广度优先搜索。层次遍历指的是按照结点所在层,从根结点开始逐一访问。不同于之前几种遍历方法利用栈来实现,层次遍历是利用队列来实现的。首先我们初始化一个空队列并令根结点进队。每当队列不为空,使队列最前端的结点出队并且访问该结点,然后将该结点的左右儿子依次进队。
扩展:输入一棵二叉树,将其层次遍历序列输出到vector
中,不同层的结点需要输出到不同的vector
中。比如对于如下图所示的二叉树,层次遍历的结果应该是[[1],[2,4],[8,3]]
。

答案:上面的题目要求我们在层次遍历的基础上,将不同层的结点加以区分。我们可以利用两个队列交替放置不同层的结点,也就是说当队列A
中的一个结点出队时,我们将其左右儿子加入到队列B
中,反之亦然。这样,与当前结点同一层的结点就会出现在同一个队列中,而当前结点的上层或下层结点就会在另一个队列中出现,达到了区分不同层结点的目的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|