二叉树的遍历

遍历(traverse),按照一定顺序依次访问二叉树各个节点,在二叉树的各个operation中均有重要应用.

下面我来总结一下课程内教到的各种二叉树遍历算法.

一.遍历顺序

二叉树遍历的顺序可分为以下四种:

• 1.先序遍历(preorder)
• 2.中序遍历(inorder)
• 3.后序遍历(postorder)
• 4.层序遍历

前三者是以”左子树,右子树,root”先后访问的思想来执行的,由于默认先左后右,所以有三种顺序.层序遍历则是按照一层一层地来遍历.

二.先序遍历

1.先序遍历序列与其特点

以这么一棵树为例1

先序遍历是一个递归定义:若结点非空,先访问结点,再先序访问左子树,再先序访问右子树.

按照这种定义,将上面的二叉树先序遍历,得到:ABDECFHIGJ

注意到:先序遍历序列的第一个结点一定是root.

2.先序遍历递归算法

二叉树的先序算法定义是一个递归定义,按照定义可以写出如下递归算法:

• 1.若root不为空,访问
• 2.先序遍历左子树
• 3.先序遍历右子树

3.先序遍历非递归算法

可将上述的递归算法改成非递归算法

3.1.双循环非递归

借用一个栈的辅助空间,将未处理的结点先入栈,然后再依次出栈.以下是详细算法:

• 1.p一开始指向root,栈一开始为空
• 2.while(p!=null),访问p,将p入栈,同时p=p->leftchild
• 3.若栈不为空,pop(top),同时p指向该元素右子树
• 4.重复2,3,直到p=null且栈为空.

以例1为例

• P指向A,然后p不为空,A入栈,p指向A左子树B;
• p不为空,B入栈,p指向D;
• p不为空,D入栈,p指向D左子树(空);
• p为空,栈不空,栈顶元素D出栈,p指向D右子树(也为空)
• ……

该算法时间复杂度是2n,空间复杂度最差需要n(一条线,所有元素都要入栈),最优需要log₂n(类似完全二叉树,只要入栈层数个元素)

3.2.单循环非递归

上述循环中有两个循环:while(p!=NULL)和while(stack!=NULL),可将上面的算法改成一个循环,具体实现如下:

• 1.p一开始指向root,栈一开始为空
• 2.p不为空,将p入栈
• 3.若栈不空,pop(top),p指向该元素,访问p,将p的右子树入栈,再将p的左子树入栈
• 4.循环执行3,直到栈为空,结束

以例1为例:

• p指向A
• p不为空,A入栈
• 栈不空,pop(A),p指向A,访问A,将C入栈,再将B入栈
• 栈不空,pop(B),p指向B,访问B,将E入栈,再将D入栈
• 栈不空,pop(D),p指向D,访问D,D左右子树都为空,不入栈
• ……

时间也是O(n),空间是O(logn)到O(n)

三.中序遍历

1.中序遍历序列与其特点

中序遍历与先序一样，也是递归定义：先中序遍历左子树，再访问结点，再中序访问右子树

例1的序列应该是这样：DBEAHFICGJ

中序序列的顺序十分有趣：

• 1.中序序列写成a₁,a₂,.,a_n，中间存在一个a_i为root,从a₁到a_i-1,是root左子树中序序列;从a_i+1到a_n,是root右子树中序序列
• 2.对中序序列的图像作画做点规定:每个结点的左子树整体位于它左侧,右子树整体位于它右侧.这样一来整棵树结点的水平位置就能区分.将这个树上的结点一一投影到横坐标上,形成的序列即为中序序列(可以用数学归纳法证明，证明略)

2.中序遍历递归算法

按照定义,可得出以下算法:

• 1.若结点不空,中序遍历左子树
• 2.访问root
• 3.中序遍历右子树

3.中序遍历非递归算法

可将上述算法改成非递归模式:

3.1 双循环实现

实际上和先序的基本一致,只是visit结点的时间不同.详细如下:

• 1.p一开始指向root,栈一开始为空
• 2.while(p!=null),将p入栈,同时p=p->leftchild
• 3.若栈不为空,pop(top),访问p,同时p指向该元素右子树
• 4.重复2,3,直到p=null且栈为空.

时间空间复杂度一样

3.2 单循环实现

由于要先要处理左子树,再访问结点,我们需要一个标号来记录结点的状态.

比如采用如下的标号策略:0表示未访问左子树,1表示已访问左子树.

• 当程序读到X₀的时候,先将X右子树Y₀入栈,然后将X改成X₁再次入栈,再将X左子树Z₀入栈;
• 当读到X₁的时候,程序会访问X结点;

具体算法如下:

• 1.p一开始指向root,栈一开始为空
• 2.将root₀入栈
• 3.若栈不空,pop(top),p指向该元素
• 4.若p的标号是0,将p->lch以标号0入栈,p以标号1入栈,p->lch以标号0入栈
• 5.若p的标号是1,visit(p)
• 5.循环执行3,4,5,直到栈为空,结束

四.后序遍历

1.后序遍历序列与其特点

还是以这么一棵树为例

后序遍历也是一个递归定义:若结点非空,先后序访问左子树,再后序访问右子树,最后访问节点.

按照这种定义,将上面的二叉树后序遍历,得到:DEBHIFJGCA

注意到:后序遍历序列的最后一个结点一定是root

2.后序遍历递归算法

按照定义,给出以下算法:

• 1.后序遍历左子树
• 2.后序访问右子树
• 3.访问root

3.后序遍历非递归算法

3.1 双循环后序遍历

在采用类似于先序和中序的显式栈方法时,我们会发现存在一个问题:在p=null后,我们pop(top)来访问top的右子树,但是此时还并未访问top,直接出栈会导致记录的信息缺失.

为此,我们同样用对入栈元素标号来解决这个问题:

• 标号为0,表示右子树还没有访问.指针指向它时,应访问右子树;
• 标号为1,表示右子树已经访问,指针指向它时,应该访问节点;

按照这种标号,我们给出如下算法:

• 1.p一开始指向root,栈一开始为空
• 2.while (p!=null),将p以标号0入栈,同时p=p->leftchild
• 3.若栈不为空,pop(top),p指向top
• 4.若p的标号是0,将p以标号1再次入栈,然后p=p->rch
• 5.若p的标号是1,visit(p),p=null
• 6.重复2,3,4,5,直到p=null且栈为空.

时间O(n),空间O(logn)到O(n)

3.2 单循环后序遍历