遍历二叉树和线索二叉树

6.3　遍历二叉树和线索二叉树

6.3.1　遍历二叉树

二叉树的遍历是指按某种顺序访问二叉树中的所有结点,使得每个结点都被访问,并且仅被访问一次。通过一次遍历,使二叉树中结点的非线性序列转变为线性序列。也就是说,使遍历的结点序列之间产生一对一的关系。

由二叉树的递归定义可知,一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分组成。因此,只要依次遍历这三个部分,就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树,则二叉树的遍历方式有6种不同的组合,即DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右的次序,那么,就只有DLR、LDR和LRD三种遍历方式。

1.先序遍历

先序遍历（DLR）也称为先根遍历,其递归过程如下。

若二叉树为空,则遍历结束。否则,按以下顺序遍历:访问根结点；先序遍历根结点的左子树；先序遍历根结点的右子树。

先序遍历的递归算法如下。

对于图6－10所示的二叉树,按先序遍历所得到的结点序列如下。

A B D G C E F H

2.中序遍历

中序遍历（LDR）也称为中根遍历,其递归过程如下。

若二叉树为空,则遍历结束。否则,按以下顺序遍历:中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。

中序遍历递归算法如下。

对于图6－10所示的二叉树,按中序遍历所得到的结点序列如下。

D G B A E C H F

3.后序遍历

后序遍历（LRD）也称为后根遍历,其递归过程如下。

若二叉树为空,则遍历结束。否则,按以下顺序遍历:后序遍历根结点的左子树；后序遍历根结点的右子树；访问根结点。

后序遍历递归算法如下。

对于图6－10所示的二叉树,按后序遍历所得到的结点序列如下。

G D B E H F C A

4.层次遍历

按照自上而下（从根结点开始）,从左到右（同一层）的顺序逐层访问二叉树上的所有结点,这样的遍历称为按层次遍历。

按层次进行遍历时,当一层结点访问完后,接着访问下一层的结点,先遇到的结点先访问,这与队列的操作原则是一致的。因此,在进行层次遍历时,可设置一个数组来模拟队列,用于保存被访问结点的子结点的地址。遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从队头取出一个元素,每取一个元素,则执行下面的两个操作。

（1）访问该元素所指结点。

（2）若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩子指针和右孩子指针依次入队。

此过程不断进行,直到队空为止。

在下面的层次遍历算法中,二叉树以二叉链表方式存储,一维数组q[MAXLEN]用于实现队列,lchild和rchild分别是被访问结点的左、右指针。

层次遍历算法如下。

对于图6－10所示的二叉树,按层次遍历所得到的结果序列如下。

A B C D E F G H

【例6－1】　如图6－13所示的二叉树,求其先序遍历、中序遍历、后序遍历和层次遍历。

（1）先序遍历的序列为:A B D G E H C F I K

（2）中序遍历的序列为:D G B H E A F K I C

（3）后序遍历的序列为:G D H E B K I F C A

（4）层次遍历的序列为:A B C D E F G H I K

图6－13　例6－1的二叉树

图6－14　例6－2的二叉树

【例6－2】　设表达式A－B＊（C＋D）＋E/（F＋G）的二叉树表示如图6－14所示。试写出它的先序遍历、中序遍历和后序遍历。

（1）先序遍历的结果,即原表达式的前缀表达式为:＋－A＊B＋C D/E＋F G

（2）中序遍历的结果为:A－B＊C＋D＋E/F＋G

（3）后序遍历的结果,即原表达式的后缀表达式为:A B C D＋＊－E F G＋/＋

说明:

如果能根据一般表达式画出二叉树的话,就能方便地使用后序遍历的方法来求得一般表达式的后缀表达式。

6.3.2　恢复二叉树

由上一小节可知,任意一棵二叉树结点的先序序列和中序序列都是唯一的。那么能否根据结点的先序序列和中序序列来唯一地确定一棵二叉树呢？答案是肯定的。

在统一绘图软件或其他绘图软件中存在着这样的问题:如何存储一个用树表示的图形数据结构？在研制统一绘图软件系统时是采用如下办法来处理的。

（1）对于用链表结构表示的图形数据结构,去掉每一个结点的指针项,只按结点的中序序列存储,并给出这棵树的前序（或后序）“序表”。

（2）图形结构调入内存时,由中序的结点表及“序表”形成的前序和中序数组（或后序和中序数组）,来恢复图形数据结构。

二叉树的先序遍历是先访问根结点,然后再遍历根结点的左子树,最后遍历根结点的右子树。即在先序序列中,第一个结点必定是二叉树的根结点。

中序遍历则是先遍历左子树,然后访问根结点,最后再遍历右子树。这样根结点在中序序列中必然将中序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,而后一个子序列则是根结点的右子树的中序序列。

根据这两个子序列,先由先序序列确定第一个结点为根结点；知道根结点后,按中序序列可以划分左、右子树。在先序序列中,左子树序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。这样,就确定了二叉树的3个结点。同时,左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列,如此递归下去,当取尽先序序列中的结点时,便可以恢复一棵二叉树。

1.由前序和中序恢复二叉树

由前序和中序恢复二叉树的具体步骤如下。

（1）根据前序序列确定树的根结点（第一个结点）,根据中序序列确定左子树和右子树。

（2）分别找出左子树和右子树的根结点,并把左、右子树的根结点连到父（father）结点上去。

（3）再对左子树和右子树按此法找根结点和左、右子树,直到子树只剩下1个结点或2个结点,或者为空为止。

【例6－3】　由下列前序序列和中序序列恢复二叉树。

前序序列:A C B R S E D F M L K

中序序列:R B S C E A F D L K M

首先,由先序序列可知,结点A是二叉树的根结点；其次,根据中序序列,在A之前的所有结点都是根结点左子树的结点,在A之后的所有结点都是根结点右子树的结点。

然后,再对左子树进行分解,得知C是左子树的根结点；又从中序序列知道,C的右子树只有一个结点E,B的左子树有B、R、S三个结点。接着对A的右子树进行分解,由前序得知A的右子树的根结点为D；再根据右子树的中序序列可知,结点D把其余结点分成两部分,即左子树仅一个结点E,右子树为L、K、M3个结点。

再按同样的方法继续分解下去,最后得到如图6－15所示的整棵二叉树。

上述过程是一个递归过程,其递归算法的思想是:首先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素,确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树,由右子树的先序序列与中序序列建立右子树。

2.由中序和后序恢复二叉树

由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树,其具体方法如下。

图6－15　例6－3对应的二叉树

（1）根据后序序列找出根结点（最后一个结点）,根据中序序列确定左、右子树。

（2）分别找出左子树和右子树的根结点,并把左、右子树的根结点连到父（father）结点上去。

（3）再对左子树和右子树按此法找根结点和左、右子树,直到子树只剩下一个结点或两个结点,或者为空为止。

【例6－4】　由下列中序序列和后序序列恢复二叉树。

中序序列:C B E D A G H F J I

后序序列:C E D B H G J I F A

首先,由后序序列可知,结点A是二叉树的根结点；其次,根据中序序列,在A之前的所有结点都是根结点左子树的结点,在A之后的所有结点都是根结点右子树的结点。

然后,再对左子树进行分解,由后序序列可知,B是左子树的根结点；又从中序序列知道,B的左子树只有一个结点C,B的右子树有E、D两个结点。接着对右子树进行分解,由后序序列可知,F为右子树的根结点；再根据右子树的中序可知,结点F把其余结点分成两部分,即左子树有G、H两个结点,右子树仅有J、I两个结点。

图6－16　整棵二叉树

再按同样的方法继续分解下去,最后得到如图6－16所示的整棵恢复的二叉树。

思考:

根据二叉树的前序序列和后序序列能否唯一恢复一棵二叉树？

6.3.3　线索二叉树

1.什么是线索二叉树

遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列,这实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列,除第一个结点和最后一个结点以外,其余每个结点都有且仅有一个直接前驱结点和一个直接后继结点。

当以二叉链表作为存储结构时,只能找到结点的左、右孩子的信息,而不能直接得到结点任意一个序列中的直接前驱结点和直接后继结点是什么,这种信息只有在对二叉树遍历的动态过程中才能得到。若增加前驱指针和后继指针将使存储密度进一步降低。

在用二叉链表存储的二叉树中,单个结点的二叉树有两个空指针域,如图6－17（a）所示；两个结点的二叉树有三个空指针域,如图6－17（b）所示。

图6－17　用二叉链表存储的二叉树

不难证明:n个结点的二叉树有n＋1个空指针域。也就是说,一个具有n个结点的二叉树,若采用二叉链表存储结构,在其总共2n个指针域中只有n－1个指针域是用于存储结点子树的地址,而另外n＋1个指针域存放的都是∧（空指针域）。因此,可以充分利用二叉链表存储结构中的那些空指针域,来保存结点在某种遍历序列中的直接前驱结点和直接后继结点的地址信息。

指向直接前驱结点或指向直接后继结点的指针称为线索（thread）,带有线索的二叉树称为线索二叉树。对于二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

2.线索二叉树的方法

由于二叉树结点的序列可由不同的遍历方法得到,因此,线索二叉树也分为先序线索二叉树、中序线索二叉树和后序线索二叉树三种。在三种线索二叉树中一般以中序线索化用得最多,所以下面以图6－10所示的二叉树为例,说明中序线索二叉树的方法。中序线索二叉树的具体步骤如下。

（1）先写出原二叉树的中序遍历序列:D G B A E C H F。

图6－18　中序线索二叉树

（2）若结点的左子树为空,则此线索指针将指向前一个遍历次序的结点。

（3）若结点的右子树为空,则此线索指针将指向下一个遍历次序的结点。

图6－18所示即为图6－10的二叉树的中序线索二叉树的结果。其中,实线表示指针,虚线表示线索。

线索二叉树的结点结构定义如下。

二叉树进行中序线索化的递归函数代码如下。

由于整棵二叉树中序序列的直接前驱结点和直接后继结点均可为空,因此对二叉树T进行中序线索化可采用语句InThreadBiTree（T,NULL,NULL）。

另外,为了便于操作,在存储线索二叉树时需要增设一个结点,其结构与其他线索二叉树的结点结构一样。但是头结点的数据域不存放信息,它的左指针域指向二叉树的根结点,右指针域指向自己。而原二叉树在某种序列遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向头结点。

3.线索二叉树的优点

（1）利用线索二叉树进行中序遍历时,不必采用堆栈处理,速度比一般二叉树的遍历速度快,并且节约存储空间。

（2）任意一个结点都能直接找到它相应遍历顺序的直接前驱结点和直接后继结点。

4.线索二叉树的缺点

（1）结点的插入和删除较麻烦,并且速度也比较慢。

（2）线索子树不能共用。