408数据结构-线索二叉树自学知识点整理

前置知识：二叉树的概念、性质与存储结构

线索二叉树的基本概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列（如中序遍历序列），从而得到几种遍历序列，使得该序列中的每个结点（除了首尾两个结点外）都有一个直接前驱和直接后继。
（注：此处的前驱后继指的是遍历序列中的，并不是树的逻辑结构中的前驱后继。）

typedef struct ElemType {
	int value;
}ElemType;

typedef struct BiTNode {//二叉树的结点（链式存储）
	ElemType data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

在传统的二叉链表中，仅能体现出结点之间的一种父子关系，并不能直接得到结点在遍历中的前驱或后继。在之前的内容里提到过：

由二叉链表的性质， $n$ 个结点的二叉链表共有 $n + 1$ 个空指针域，这一部分可用于构造线索二叉树。
（计算方法：度为 $2$ 的结点有 $0$ 个空指针域，度为 $1$ 的结点有 $1$ 个空指针域，度为 $0$ 的结点有 $2$ 个空指针域。由此前的性质可知，当 $n_1=1$ 时， $n_0=n/2$ ，空指针域数量为 $1 + 2 * n /2 = n + 1$ ；当 $n_1=0$ 时， $n_0=(n+1)/2$ ，空指针域数量为 $0 + 2 * (n + 1) /2 = n + 1$ 。故无论 $n$ 的值为奇数还是偶数， $n$ 个结点的二叉链表的空指针域都为 $n + 1$ 个）

因此，可规定：对一个结点，若其无左子树，则令 $l c hi l d$ 指针指向其前驱节点；若无右子树，则令 $rc hi l d$ 指针指向其后继结点。为此，还需增加两个标志域，以标识指针域指向其左（右）孩子或前驱（后继）。

typedef struct ThreadNode {//线索二叉树结点
	ElemType data;
	struct ThreadNode* lchild, * rchild;
	bool ltag = false, rtag = false;//左、右线索标志
	//当tag值为0的时候，表示指针指向孩子
	//而tag值为1的时候，表示指针指向线索
}ThreadNode, * ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点的前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。它的作用是方便从一个指定结点出发，找到其前驱、后继；方便遍历。
无论根据先序序列、中序序列还是后序序列，定义线索二叉树结点的方法都是一样的，区别在于三种序列中的前驱和后继不同，因此仅在二叉树线索化时算法设计有所不同。
对这一部分内容，408考研初试要求掌握能够手算画出线索二叉树——首先确定线索二叉树的类型（先序/中序/后序），再按照对应规则，确定各个结点的访问顺序并写上编号，最后将 $n + 1$ 空链域连上前驱和后继即可。

二叉树的线索化（前置知识：二叉树的遍历）

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
预处理如下：

ThreadNode* pre = NULL;//全局变量pre，指向当前访问节点的前驱

以中序线索二叉树的建立为例，增加一个全局 $T h re a d N o d e *$ 类型的变量 $p re$ ，用于指向当前访问结点 $p$ 的上一个访问的结点，即 $p re$ 指向 $p$ 的前驱。在中序遍历的过程中，检查 $p$ 的左孩子指针是否为空，若为空，则将其指向 $p re$ ，同时修改 $lt a g$ 的值为 $1$ ；同时检查检查 $p re$ 的右孩子指针是否为空，若为空，则将其指向 $p$ ，同时修改 $r t a g$ 的值为 $1$ 。
具体代码实现如下，使用递归算法：

void visit(ThreadNode* q) {
	if (q->lchild == NULL) {//左子树为空，建立前驱线索
		q->lchild = pre;
		q->ltag = true;
	}
	if (pre != NULL && pre->rchild == NULL) {
		pre->rchild = q;//建立前驱节点的后继线索
		pre->rtag = true;
	}
	pre = q;
	return;
}

void InThread(ThreadTree T) {//中序遍历二叉树，并线索化
	if (T != NULL) {
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	}
	return;
}

void CreateInThread(ThreadTree T) {//中序线索化二叉树T
	pre = NULL;//pre初始为NULL
	if (T != NULL) {//若二叉树非空
		InThread(T);//中序遍历并线索化处理
		if (pre->rchild == NULL)
			pre->rtag = true;//对最后一个结点特殊处理
	}
	return;
}

先序线索二叉树和后序线索二叉树的实现与中序基本相同，唯一不同的是遍历时访问结点的顺序。
此外需特别注意，在先序遍历时，一定要在访问左子树前加上一个判断条件，若 $lt a g == 0$ 才继续访问并处理左子树。否则，因为当前结点的左孩子指针指向其前驱结点，会出现递归中的死循环。而后序遍历则无需担心这个问题，因为在对一棵子树的处理中，它的根结点是最后才处理的。

void PreThread(ThreadTree T) {//先序遍历二叉树并线索化
	if (T != NULL) {
		visit(T);//先处理根节点
		if (!T->ltag)PreThread(T->lchild);//若左孩子不是线索才处理
		PreThread(T->rchild);
	}
	return;
}

void PostThread(ThreadTree T) {//后序遍历二叉树并线索化
	if (T != NULL) {
		PostThread(T->lchild);
		PostThread(T->rchild);
		visit(T);//最后处理根结点
		//因此无需担心左右子树被线索化后可能产生“死循环”
	}
	return;
}

线索二叉树的遍历

中序线索二叉树的遍历

中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只需要先找到序列中的第一个结点，然后依次找结点的后继，直到其后继为空。

求中序线索二叉树的中序序列下的第一个结点

//找到以p为根的子树中第一个被中序遍历到的结点
ThreadNode* FirstNode(ThreadNode* p) {
	while (!p->ltag)p = p->lchild;//循环找到最左下角的结点（不一定是叶结点）
	return p;
}

求中序线索二叉树中结点 $p$ 在中序序列下的后继

//在中序线索二叉树中找到结点p的后继结点
ThreadNode* NextNode(ThreadNode* p) {
	if (p->rtag == 0)return FirstNode(p->rchild);
	//若右子树不为空，则返回右子树中第一个被中序遍历到的结点
	else return p->rchild;//否则直接返回右孩子（后继线索）
}

利用线索非递归地实现中序线索二叉树的中序遍历

void _Visit(ThreadNode* p) {
	cout << p->data.value << " ";
	return;
}
//利用线索实现对中序线索二叉树的中序遍历（非递归算法）
void InOrder(ThreadNode* T) {
	for (ThreadNode* p = FirstNode(T); p != NULL; p = NextNode(p))
		_Visit(p);
	return;
}

同理，对上续操作稍加修改，就能得到中序线索二叉树的逆中序遍历序列。

找到中序线索二叉树的中序遍历序列的最后一个结点

//找到以p为根的子树中最后一个被中序遍历到的结点
ThreadNode* LastNode(ThreadNode* p) {
	while (!p->rtag)p = p->rchild;//循环找到最右下角的结点（不一定是叶结点）
	return p;
}

找到中序线索二叉树中结点 $p$ 在中序序列中的前驱

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode* PreNode(ThreadNode* p) {
	if (p->ltag == 0)return LastNode(p->lchild);
	//若左子树不为空，则返回左子树中最后一个被中序遍历到的结点
	else return p->lchild;//否则直接返回左孩子（前驱线索）
}

利用线索非递归地实现中序线索二叉树的逆中序遍历

//利用线索实现对中序线索二叉树的逆向中序遍历（非递归算法）
void RevInOrder(ThreadNode* T) {
	for (ThreadNode* p = LastNode(T); p != NULL; p = PreNode(p))
		_Visit(p);
	return;
}

完整代码可以看我的Github：传送门

先序线索二叉树（根左右）

$1)$ 找先序后继 $n e x t$

若右子树为空， $rc hi l d$ 指向后继线索，即 $p - > r t a g == 1$ ，则 $n e x t = p - > rc hi l d$ 。
若右子树非空，即 $p - > r t a g == 0$ ，此时需要分两种情况：
①若 $p$ 有左孩子，则 $p$ 的先序后继必为其左孩子；
②若 $p$ 没有左孩子，则 $p$ 的先序后继必为其右孩子。

$2)$ 找先序前驱 $p re$

若左子树为空， $l c hi l d$ 指向后继线索，即 $p - > lt a g == 1$ ，则 $p re = p - > l c hi l d$ 。
若左子树非空，即 $p - > lt a g == 0$ ，此时需要进一步讨论：
因为先序遍历的规则是“根左右”，因此其左右子树中所有结点一定都是它的先序后继，不可能在当前结点的左右子树中找到它的先序前驱。
解决方案有两种，一种是对整棵先序线索二叉树从头开始再进行一次完整的先序遍历，找到当前结点的先序前驱；另一种是在构建二叉树时使用三叉链表，即给各个结点设置一个指向其父结点的指针。
以三叉链表为基础再进一步探讨，共分为 $4$ 种情况：
①能找到结点 $p$ 的父结点，且 $p$ 是左孩子。此时 $p$ 的父结点一定是它的先序前驱；
②能找到结点 $p$ 的父结点， $p$ 是右孩子，且 $p$ 的左兄弟为空。此时 $p$ 的父结点也一定是它的先序前驱；
③能找到结点 $p$ 的父结点， $p$ 是右孩子，且 $p$ 的左兄弟非空。此时 $p$ 的先序前驱一定是其左兄弟子树中，按照先序遍历的规则最后一个被访问到的结点（向下查找，优先向右，无右向左，直至叶结点）；
④若不能找到结点 $p$ 的父结点，此时 $p$ 为根结点，没有先序前驱。

后序线索二叉树（左右根）

$1)$ 找后序前驱 $p re$

若左子树为空， $l c hi l d$ 指向前驱线索，即 $p - > lt a g == 1$ ，则 $p re = p - > l c hi l d$ 。
若左子树非空，即 $p - > lt a g == 0$ ，此时需要分两种情况：
①若 $p$ 有右孩子，则 $p$ 的后序前驱必为其右孩子；
②若 $p$ 没有右孩子，则 $p$ 的后序前驱必为其左孩子。

$2)$ 找后序后继 $n e x t$

若右子树为空， $rc hi l d$ 指向后继线索，即 $p - > r t a g == 1$ ，则 $n e x t = p - > rc hi l d$ 。
若右子树非空，即 $p - > r t a g == 0$ ，此时需要进一步讨论：
因为后序遍历的规则是“左右根”，因此其左右子树中所有结点一定都是它的后序前驱，不可能在当前结点的左右子树中找到它的后序后继。
解决方案有两种，一种是对整棵先序线索二叉树从头开始再进行一次完整的后序遍历，找到当前结点的后序后继；另一种是使用三叉链表构建二叉树。
以三叉链表为基础再进一步探讨，共分为 $4$ 种情况：
①能找到结点 $p$ 的父结点，且 $p$ 是右孩子。此时 $p$ 的父结点一定是它的后序后继；
②能找到结点 $p$ 的父结点， $p$ 是左孩子，且 $p$ 的右兄弟为空。此时 $p$ 的父结点也一定是它的后序后继；
③能找到结点 $p$ 的父结点， $p$ 是左孩子，且 $p$ 的右兄弟非空。此时 $p$ 的后序后继一定是其右兄弟子树中，按照后序遍历的规则第一个被访问到的结点（向下查找，优先向左，无左向右，直至叶结点）（和找先序前驱正好相反）；
④若不能找到结点 $p$ 的父结点，此时 $p$ 为根结点，没有后序后继。