全屏显示专题章节

在线索二叉树中，结点的结构可以定义为如下形式：

下面以中序线索二叉树为例，讨论线索二叉树的建立、线索二叉树的遍历以及在线索二叉树上查找前驱结点、查找后继结点、插入结点和删除结点等操作的实现算法。

1.建立一棵中序线索二叉树

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。

另外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

下面是建立中序线索二叉树的递归算法，其中pre为全局变量。

算法6.13 中序线索二叉树

算法6.14 中序线索化

2.在中序线索二叉树上查找任意结点的中序前驱结点

对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况：

（1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；

（2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。

在中序线索二叉树上寻找结点p的中序前驱结点的算法如下。

算法6.15 在中序线索二叉树上寻找结点p的中序前驱结点

3.在中序线索二叉树上查找任意结点的中序后继结点

对于中序线索二叉树上的任一结点，寻找其中序的后继结点，有以下两种情况：

（1）如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继结点；

（2）如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，它的前驱结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。

在中序线索二叉树上寻找结点p的中序后继结点的算法如下。

算法6.16 在中序线索二叉树上寻找结点p的中序后继结点

以上给出的仅是在中序线索二叉树中寻找某结点的前驱结点和后继结点的算法。在前序线索二叉树中寻找结点的后继结点以及在后序线索二叉树中寻找结点的前驱结点可以采用同样的方法分析和实现，在此就不再讨论了。

4.在中序线索二叉树上查找任意结点在先序下的后继

这一操作的实现依据是：若一个结点是某子树在中序下的最后一个结点，则它必是该子树在先序下的最后一个结点。该结论可以用反证法证明。

下面就依据这一结论，讨论在中序线索二叉树上查找某结点在先序下后继结点的情况。设开始时，指向此某结点的指针为p。

（1）若待确定先序后继的结点为分支结点，则又有两种情况：

①当p－ltag＝0时，p－lchild为p在先序下的后继；

②当p－ltag＝1时，p－rchild为p在先序下的后继。

（2）若待确定先序后继的结点为叶子结点，则也有两种情况：

①若p－rchild是头结点，则遍历结束；

②若p－rchild不是头结点，则p结点一定是以p－rchild结点为根的左子树中在中序遍历下的最后一个结点，因此p结点也是在该子树中按先序遍历的最后一个结点。此时，若prchild结点有右子树，则所找结点在先序下的后继结点的地址为p－rchild－rchild；若prchild为线索，则让p＝p－rchild，反复进行情况（2）的判定。

在中序线索二叉树上寻找结点p的先序后继结点的算法如下。

算法6.17 在中序线索二叉树上寻找结点p的先序后继结点

BiThrTree IPrePostNode（BiThrTree head，BiThrTree p）

｛／＊在中序线索二叉树上寻找结点p的先序后继结点，head为线索树的头结点＊／

5.在中序线索二叉树上查找任意结点在后序下的前驱

这一操作的实现依据是：若一个结点是某子树在中序下的第一个结点，则它必是该子树在后序下的第一个结点。该结论可以用反证法证明。

下面就依据这一结论，讨论在中序线索二叉树上查找某结点在后序下前驱结点的情况。设开始时，指向此某结点的指针为p。

（1）若待确定后序前驱的结点为分支结点，则又有两种情况：

①当p－ltag＝0时，p－lchild为p在后序下的前驱；

②当p－ltag＝1时，p－rchild为p在后序下的前驱。

（2）若待确定后序前驱的结点为叶子结点，则也有两种情况：

①若p－lchild是头结点，则遍历结束；

②若p－lchild不是头结点，则p结点一定是以p－lchild结点为根的右子树中在中序遍历下的第一个结点，因此p结点也是在该子树中按后序遍历的第一个结点。此时，若p－lchild结点有左子树，则所找结点在后序下的前驱结点的地址为p－lchild－lchild；若p－lchild为线索，则让p＝p－lchild，反复进行情况（2）的判定。

在中序线索二叉树上寻找结点p的后序前驱结点的算法如下。

算法6.18 在中序线索二叉树上寻找结点p的先序后继结点

6.在中序线索二叉树上查找值为x的结点

利用在中序线索二叉树上寻找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。比如，先找到按某序遍历的第一个结点，然后再依次查询其后继；或先找到按某序遍历的最后一个结点，然后再依次查询其前驱。这样，既不用栈也不用递归就可以访问到二叉树的所有结点。

在中序线索二叉树上查找值为x的结点，实质上就是在线索二叉树上进行遍历，将访问结点的操作具体写为该结点的值与x比较的语句。下面给出其算法。

算法6.19 在中序线索二叉树上查找值为x的结点

7.在中序线索二叉树上的更新

线索二叉树的更新是指，在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。一般来说，这个过程的代价几乎与重新进行线索化相同。这里仅讨论一种比较简单的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。

下面分两种情况来分析：

（1）若s的右子树为空，如图6－17（a）所示，则插入结点p之后成为图6－17（b）所示的情形。在这种情况中，s的后继将成为p的中序后继，s成为p的中序前驱，而p成为s的右孩子。二叉树中其他部分的指针和线索不发生变化。

（2）若s的右子树非空，如图6－18（a）所示，插入结点p之后如图6－18（b）所示。s原来的右子树变成p的右子树，由于p没有左子树，故s成为p的中序前驱，p成为s的右孩子；又由于s原来的后继成为p的后继，因此还要将s原来指向s的后继的左线索改为指向p。