考研专业课之统考计算机蓝宝书(21)

来源：跨考网 2009-01-04 23:28

3.2.4 线索二叉树

1. 线索二叉树的定义

按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。

订阅收藏考研专业课之统考计算机蓝宝书

2. 线索二叉树基本操作的实现

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

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。
另外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
下面是建立中序线索二叉树的递归算法，其中pre为全局变量。

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

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

1. 如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱
结点；
2. 如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，
它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。
在中序线索二叉树上寻找结点p的中序前驱结点的算法如下：

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

对于中序线索二叉树上的任一结点，寻找其中序的后继结点，有以下两种情况：
1. 如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继
结点；
2. 如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，
它的前驱结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。
在中序线索二叉树上寻找结点p的中序后继结点的算法如下：

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

专业课精选

专业课复习规划专业课知识库专业课真题专业课大纲

教育学统考

心理学统考

西医综合