本篇文章主要介绍线索二叉树

什么是线索二叉树

首先我们要知道遍历二叉树的结果是什么？我们得到的是一个线性序列

而指向该线性序列中的“前驱”和“后继”的指针，称为线索。

我们把包含线索的存储结构称作“线索链表”

于是，对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：

• 若该结点下的左子树不空，则lChild域的指针指向其左子树，且左标志域的值为“指针 Link”；否则其lChild域的指针域指向其“前驱”，且左标志域的值为“线索 Thread”

• 若该结点下的右子树不空，则rChild域的指针指向其右子树，且有标志域的值为“指针 Link”；否则其rChild域的指针域指向其“前驱”，且右标志域的值为“线索 Thread”

我们把如此定义的二叉树的存储结构称作“线索链表”

线索链表的类型描述

1
2
3
4
5
6
7
8
9
10
11

typedef enum {
	//Link == 1:指针; Thread == 0:线索
	Link,
	Thread
}pointerThr;
	
typedef struct BiThrNod {
	TElemType e;
	BiThrNod struct *lChild, *rChild;	//左右指针
	PointerThr lTag, rTag;	//左右标志
}BiThrNod, *BiThrTree;

线索链表的遍历算法

由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。

主要思想:

for (p = firstNode(T); p; p = Succ(p)) 
    visit(p);

我们以中序遍历为例:

中序遍历的第一个结点：左子树上处于“最左下”（没有左子树）的结点

在中序线索化链表中找结点的后继

对于结点p，想要找其后继结点，当p -> rTag = 1时，p -> rChild 即为p的后继结点；当 p -> rTag = 0 时，说明p有右子树，此时p的中序后继结点即为其右子树的“最左下段”结点。

在二叉树的线索链表上添加一个头结点，令其lChild域的指针指向二叉树的根节点，其rChild域的指针指向中序遍历时访问的最后一个结点；同时令二叉树的中序序列中的第一个结点的lChild域的指针和最后一个结点的rChild域的指针都指向头结点。即为二叉树建立双向线索链表。

中序遍历二叉线索树的过程分析:

1）如果用指针p从头结点（T指向其头结点）开始访问，则遍历过程结束时，p＝＝T

2）从根结点A开始，找到其左孩子，左孩子的左孩子…直到某个结点的lTag＝＝1

3）访问该结点，如果该结点的rTag＝＝1（说明该结点有直接后继），且该结点的rChild不指向头结点T（即该结点不是中序遍历的最后一个结点），则沿着该结点rChild找到后继结点，后继结点的后继结点…并访问之

4）如果某个结点的rTag＝＝0，说明该结点有右子树，此时应该访问右子树

5）如果某个结点的rChild指向T，即该结点是中序遍历的最后一个结点，此时说明遍历过程应该结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Status inOrderTraverse_Thr(BiThrTree T, Status(* Visit)(TElemType)) {
	//T指向头结点，头结点的lChild左链指向根节点
	//中序遍历二叉线索树的非递归算法
	p = T -> lChild;	//p指向根节点
	while (p != T) {
		//空树或者遍历结束时，p==T
		while (p -> lTag == Link)
			p = p -> lChild;
		if (!Visit(p -> data))
			//访问左子树为空的结点
			return ERROR;
		while (p -> rTag == Thread && p -> rChild != T) {
			//访问后继结点
			p = p -> rChild;
			Visit(p -> data);
		}
		//如果p -> rTag == Link，则从右子树开始
		p = p -> rChild;
	}
	return OK;
}//inOrderTraverse_Thr

在中序线索二叉树中找到前驱结点

根据线索二叉树的基本概念和存储结构可知，对于结点p，当p -> lTag == 1 时，p -> lChild 指向其前驱；当p -> lTag == 0 时，p -> lChild 指向其左孩子。

由中序遍历的规律可知，作为跟p的前驱结点，他是中序遍历p的左子树时访问的最后一个结点，即左子树的“最右下端”结点。

在先序线索二叉树中找前驱结点

在先序线索树中找结点的前驱比较困难

1）若结点p是二叉树的根，则p的前驱为空

2）若p是其双亲的左孩子，或者p是其双亲的右孩子并且其双亲无左孩子，则p的前驱是其双亲结点

3）若p是双亲的右孩子，且双亲有左孩子，则p的前驱是其双亲的左子树按先序遍历时最后访问的那个结点

在先序线索二叉树中找后继结点

根据先序线索树的遍历过程可知:

1）若结点p存在左子树，则p的左孩子结点即为p的后继

2）若结点p没有左子树，但有右子树，则p的右孩子结点即为p的后继

3）若结点p既没有左子树，也没有右子树，则结点p的rChild的指针域所指的结点即为p的后继

在后序线索二叉树中找前驱结点

根据后序线索树的遍历过程可知:

1）若结点p存在右子树，则右子树的根即为p的前驱

2）若结点p存在左子树，但无右子树，则其前驱是左子树的根

3）若结点p既无左子树，又无右子树，则p -> lChild 即为他的前驱

在后序线索二叉树中找后继结点

可分为三种情况:

• 若结点p为二叉树的根，则其后继为空
• 若结点p是其双亲结点的右孩子或者是其双亲结点的左孩子且双亲没有右子树（注意条件判断，这句话有点复杂，各位不要理解错了）
• 若结点p是其双亲的左孩子，且其双亲有右子树，则其后继结点为其双亲的右子树上按后序遍历列出的第一个结点

如何建立线索链表

在中序遍历过程中，修改结点的左右指针域，以保存当前访问结点的的“前驱”和“后继”信息。遍历过程中，附设指针pre，并始终保持指针pre指向当前访问的、指针p所指结点的前驱。（即一直保持一对结点，p为正在访问的，pre为访问过的并指向p的前驱）

线索化的实质是指将二叉链表中的空指针改为指向前驱或者后继的线索

前驱或后继的信息只有在遍历时才能得到

因此，线索化的过程就是在遍历过程中修改空指针的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Status inOrderThreading(BiThrTree &Thrt, BiThrTree T) {
	//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
	if(!Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))
		return(OVERFLOW);
	//建立头结点
	Thrt -> lTag = Link;
	Thrt -> rTag = Thread;
	//右指针回指
	Thrt -> rChild = Thrt;
	if (!T)
		//若二叉树为空，左指针回指
		Thrt -> lChild = Thrt;
	else {
		Thrt -> lChild = T;
		pre = Thrt;
		//中序遍历进行中序线索化
		InThreading(T);
		//最后一个结点线索化
		pre -> rChild = Thrt;
		pre -> rTag = Thread;
		Thrt -> rChild = pre;
	}
	return OK;
}
Status InReading(BiThrTree &p) {
	//中序遍历进行中序线索化
	if (p) {
		//左子树线索化
		InReading(p -> lChild);
		if (!p -> lChild) {
			//前驱线索
			p -> lTag = Thread;
			p -> lChild = pre;
		}
		if (!p -> rChild) {
			//后继线索
			p -> rTag = Thread;
			p -> rChild = pre;
		}
		//保持pre指向p的前驱
		pre = p;
		//右子树线索化
		InThreading(p -> rChild);
	}
	return OK;
}

小结

线索二叉树：在二叉链表表示的二叉树中，引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，遍历过程会变得非常简单

二叉链表结构查找结点的左右孩子非常方便，但其前驱和后继是在遍历中形成的。在线索二叉树（尤其是中序线索二叉树中）上遍历便消除了递归，也不使用栈（其中后序线索二叉树中查找后继还是需要栈）

由于序列可由不同的遍历方法得到，因此，线索树中有先序线索二叉树、中序线索二叉树、后续线索二叉树三种。

在先序、中序、后序线索二叉树中实现方法均相同，即线索化之前的二叉树相同，所有结点的标志位取值也完全相同，只是标志位取1时，不同的线索二叉树将用不同的虚线表示，即不同的线索树中线索指向的前驱和后继结点不同。

因为中序线索二叉树使用的很普遍，以下表格以中序为例