22、线索二叉树

（1）以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表；指向结点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树（Threaded Binary Tree）；对二叉树以某种次序（前序、中序、后序）遍历使其变为线索树的过程叫做线索化。

（2）[为什么要有线索二叉树]二叉树是一种非线性结构，对二叉树的遍历实际上是将二叉树这种非线性结构按某种需要转化为线性序列，以便以后在对二叉树进行某种处理时直接使用。因此如何保存遍历二叉树后得到的线性序列，以避免对二叉树的重复遍历，是一个需要解决的问题。

一种最简单的方法是将得到的遍历序列存放在另外的存储空间内，但这需要付出额外的存储花销。我们能不能在不增加存储空间的前提下，在原来二叉链表的存储空间内反映出某种遍历后结点的逻辑关系，即遍历后某个结点的直接前驱和直接后继呢？

另一种方法就是：当我们用标准形式存储一棵二叉树时，树中有一半以上的指针是空的。对于一棵具有n个结点的二叉树，如果按标准形式来存储，那么总共有2n个指针（用来存放左孩子、右孩子的指针）其中只有（n-1）个用来指向子结点，另外（n+1）个指针时空的。这显然是浪费，我们应该设法利用这些空的指针来实现保存遍历二叉树后得到的线性序列。

由此，我们产生了线索二叉树的概念。

线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题。它只增加了两个标志性域，就可以充分利用没有左或右孩子的结点的左右孩子的存储空间来存放该结点的线性前驱结点与线性后继结点。两个标志性域所占用的空间是极少的，所有充分利用了二叉链表中空闲存的储空间。

对一棵给定的二叉树，按不同的遍历规则进行线索化所得到的线索树是不同的，分别用前序、中序、后序遍历规则，对给定二叉树进行线索化得到的二叉树，分别称之为前序线索树、中序线索树、后序线索树。

要实现线索二叉树，就必须定义二叉链表结点数据结构如下（定义请看代码）：

LnodeLtagDataRtagRnode

说明：

1. Ltag=0时，表示Lnode指向该结点的左孩子；

2. Ltag=1时，表示Lnode指向该结点的线性前驱结点；

3. Rtag=0时，表示Rnode指向该结点的右孩子；

4. Rtag=1时，表示Rnode指向该结点的线性后继结点。

中序次序线索化二叉树算法：

中序次序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索；（具体看代码）

检索中序二叉树某结点的线性前驱结点的算法：

1. 如果该结点的Ltag=1,那么Lnode就是它的线性前驱；

2. 如果该结点的Ltag=0,那么该结点左子树最右边的尾结点就是它的线性前驱点。

（具体请看代码）

检索中序二叉树某结点的线性后继结点和算法：

1. 如果该结点的Rtag=1,那么Rnode就是它的线性后继结点；

2. 如果该结眯的Rtag=0,那么该结点右子树最左边的尾结点就是它的线性后继结点。

（具体请看代码）

解决方案中所有到二叉树的中序线索二叉树和中序线索链表的图。

//二叉树线索化

//输入二叉树先序，建树，然后中序线索化，遍历输出

#include

usingnamespace std;

enumPointerTag

{

Link,Thread //枚举值Link和Thread分别为0,1

};

structBiThrNode //线索二叉树的结点类型

{

char data;

PointerTag LTag; //左标志

PointerTag RTag; //右标志

BiThrNode *lchild; //左孩子指针

BiThrNode *rchild; //右孩子指针

};

typedefBiThrNode* BiThrTree;

BiThrNode*pre=NULL; //全局量

voidInOrderThreading（BiThrTree & Thrt,BiThrTree T）；//线索化

voidInThreading（BiThrTree p）；//中序遍历线索化

boolPreOrderCreatBiTree（BiThrTree &T）；//先序建立树

voidInOrderTraverse_Thr（BiThrTree T）；//中序遍历线索树

intmain（）

{

BiThrTree T,Thrt;

printf（“输入先序序列（‘#’表示空节点）建立二叉树：\n”）；

PreOrderCreatBiTree（T）；//先序建立树

InOrderThreading（Thrt,T）；//中序线索化

printf（“中序线索化，中序遍历得中缀式：\n”）；

InOrderTraverse_Thr（Thrt）；//中序遍历线索树

printf（“\n”）；

return 0;

}

返回目录：2013年软考程序员常考知识点锦集

编辑推荐：

2013年软件设计师考前冲刺专题

2013年网络工程师考前复习专题