一、线索二叉树的基本概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列；使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。

引入线索二叉树正是为了加快查找结点前驱和后继的速度。

== 我们规定 ==： 对data结点增加两个标志域标识指针 lchild(rchild)、ltag(rtag) ，其中若无左子树，则 lchild 指向其前驱结点；同理，若无右子树，令 rchild 指向其后继结点。

那如何判断 lchild(rchild) 是代表 前驱/后继 结点，还是代表 左/右孩子 呢?

那就要用到 ltag(rtag) 标志域了：

线索二叉树的结点结构如下： 这种结点结构构成的二叉链表叫做 线索链表 ，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二又树。

---

二、线索二叉树的诞生由来

对于中序遍历序列：D G B E A F C的二叉树，能否从一个指定结点开始中序遍历? 例如从G开始遍历，这是不可能的！因为我们不知道根节点是哪一个。

要求： 根据上图的二叉树

• ① 如何找到指定结点p在中序遍历序列中的前驱 ?
• ② 如何找到p的中序后继 ?

【分析】： 首先我们从根节点出发，重新进行一次中序遍历，遍历过程中，用指针q记录当前访问的结点，指针pre则记录结点q的上一个访问结点，由于中序满足(左根右)–> q->lchild = pre, pre->rchild = q;
当 q == p 时，pre是p的前驱；一问答毕!
当 pre == p 时，那么q是p的后继；二问答毕!

缺点: 找前驱、后继很不方便，遍历操作必须从根结点开始。

因此才会衍生出线索二叉树，在原有基础上增加两个标志域。

---

三、线索二叉树的构造

我们要找到某结点的前驱与后继，是有先要条件的！！

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

我们要事先知道，这个二叉树是由什么形式遍历而成的。是中序、先序还是后序遍历构成的。

例如上图的二叉树（中序遍历） ：

• 中序遍历（左根右）：DGBEAFC；
• 先序遍历（根左右）：ABDGECF；
• 后序遍历（左右根）：GDEBFCA；

线索化：

• 中序线索二叉树：以中序遍历序列为依据进行”线索化"；
• 先序线索二叉树：以先序遍历序列为依据进行”线索化”；
• 后序线索二叉树：以后序遍历序列为依据进行"线索化”。

进行线索化后，变成这样子，如下图：

我们很容易从线索二叉树看到，G结点的前驱是D，后继是B；E的前驱是B，后继是A。跟中序遍历结果显示的一样。

中序遍历（左根右）：DGBEAFC。
这就是线索二叉树的便利之处：加快查找结点前驱和后继的速度。

---

3.1 线索二叉树的存储结构

//线索二叉树存储结构
typedef struct ThreadNode{
	char data;
	struct ThreadNode *lchild, *rchild;	// 左右孩子指针
	int ltag, rtag;	// 左右线索标志
}ThreadNode, *ThreadTree;

---

3.2 中、先、后序遍历结构图

中序遍历（左根右）：DGBEAFC 线索二叉树的存储结构图。

先序遍历（根左右）：ABDGECF的线索二叉树的存储结构图。
后序遍历（左右根）：GDEBFCA 的线索二叉树的存储结构图。

3.3 画出线索二叉树

手算画出线索二叉树：

1. 确定线索二叉树类型——中序、先序、后序?
2. 按照对应遍历规则，确定各个结点的访问顺序，并写上编号；
3. 将n+1个空链域连上前驱、后继。

---

四、线索二叉树的代码逻辑

【分析】：

1. 定义线索二叉树类型；
2. 创建全局变量 pre指针记录结点p的上一个访问位置；pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索；
3. 先序建立二叉树、中序递归显示二叉树；
4. 线索化二叉树，①结点p非空，左子树递归线索化；②如果左孩子为空，加上左线索，p的左孩子指针指向pre(前驱)；③如果pre的右孩子为空，加上右线索，pre的右孩子指针指向p(后继)；④将pre指向刚访问过的结点p， pre=p；⑤右子树递归线索化；
5. 主函数调用。

// 算法：以结点P为根的子树中序线索化
#include<iostream>
using namespace std;

// 定义线索二叉树存储类型
typedef struct BiThrNode{
	char data;						// 结点数据域
	struct BiThrNode *lchild,*rchild;	// 左右孩子指针
	int LTag,RTag;
}BiThrNode,*BiThrTree;

// 全局变量pre
BiThrNode *pre=new BiThrNode;

// 建立二叉链表
void CreateBiTree(BiThrTree &T){
	// 按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;	// 递归结束，建空树
	else{
		T=new BiThrNode;
		T->data=ch;				// 生成根结点
		CreateBiTree(T->lchild);	// 递归创建左子树
		CreateBiTree(T->rchild);	// 递归创建右子树
	}
}

void InThreading(BiThrTree p){
	// pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
	if(p){
		InThreading(p->lchild);    // 左子树递归线索化
		if(!p->lchild){           // p的左孩子为空
			p->LTag=1;           // 给p加上左线索
			p->lchild=pre; 		// p的左孩子指针指向pre（前驱）
		}
		else
			p->LTag=0;
		if(!pre->rchild){		// pre的右孩子为空
			pre->RTag=1;       // 给pre加上右线索
			pre->rchild=p;    // pre的右孩子指针指向p（后继）
		}
		else
			pre->RTag=0;
		pre=p;                		// 保持pre指向p的前驱
		InThreading(p->rchild);    // 右子树递归线索化
    }
}

void InOrderTraverse(BiThrTree T){ // 中序输出
    if(T){
        InOrderTraverse(T->lchild);
        cout<< T->data;
        InOrderTraverse(T->rchild);
    }
}

int main(){
	pre->RTag=1;
	pre->rchild=NULL;	// 默认右孩子为空
	BiThrTree tree;
	cout<<"二叉链表的序列(中序输入) 例如：ABD##E##CF###：\n";
	CreateBiTree(tree);

	cout<<"中序遍历的结果为：\n";
	InOrderTraverse(tree);
	cout<<endl;

	InThreading(tree);
	cout<<"线索化完毕！\n";
}

这章有点难以理解代码，可以扫描二维码查看视频解析。