一、原理
利用二叉树中闲置的 n+1 个空间记录每个节点的前驱和后继。
线索：利用二叉树空链域存放在某种遍历次序下结点的前驱和后继，这些指针称为线索，加上线索的二叉树称为线索二叉树。根据线索性质的不同，线索二叉树可分为前序、中序、后序三种。
线索化的过程就是在遍历的过程中修改空指针的过程。
记 ptr 指向二叉链表中的一个结点，以下是建立中序线索的规则：
- ptr->lchild 为空，则存放该结点的前驱结点，这个结点称为 ptr 的中序前驱；
- ptr->rchild 为空，则存放该结点的后继结点，这个结点称为 ptr 的中序后继；
显然，在决定 lchild 是指向左孩子还是前驱，rchild 是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域 ltag 和 rtag，注意 ltag 和 rtag 只是区分0或1数字的布尔型变量，其占用内存空间要小于像 lchild 和 rchild 的指针变量。
结点结构重新定义如下：
| lchild | ltag | data | rtag | rchild |
|---|
- ltag 为 0 时指向该结点的左孩子，为 1 时指向该结点的前驱；
- rtag 为 0 时指向该结点的右孩子，为 1 时指向该结点的后继；
普通二叉树
线索二叉树 节点结构
二、源代码
/**
* 线索化即在遍历过程中修改空指针
* n 个结点的二叉树一共有 2n 个指针，n-1 已经用于 link，剩下 n+1 个用于 thread
* 剩下的：n-1 个用于按照遍历的顺序联系结点，多出的 2 个用于指向给出的头结点
*/
#include <iostream>
using namespace std;
typedef enum {
link, thread // 线索存储标志位：link(0)，表示指向左右指针，thread(1)，表示指向前趋后继的线索
} tag;
typedef struct Bnode {
char data;
struct Bnode *Lchild, *Rchild;
tag Ltag, Rtag; // 多了2个标志位
} Bnode, *Bintree;
Bnode *pre; // 全局变量,始终指向刚刚访问过的结点
/**
* 先序建立二叉树 TLR
* @param T 引用 main 函数中定义的树根结点的地址
*/
void createBintree(Bintree &T) {
char ch;
cin >> ch;
getchar(); // 接收 space 或 enter
if (ch == '#') { // # 结束符
T = NULL;
} else {
T = (Bintree) malloc(sizeof(Bnode)); // 新建结点
T->data = ch;
cout << ch << " 左结点(#结束): ";
createBintree(T->Lchild);
cout << ch << " 右结点(#结束): ";
createBintree(T->Rchild);
}
}
/**
* 在中序遍历基础上，线索化联系结点，n-1
*/
void inThread(Bintree T) {
if (T) {
inThread(T->Lchild); // 左子树线索化
// 原本中序遍历输出数据的地方 变为修改空指针
// 线索化结点的两种方式：前趋，后继
if (!T->Lchild) {
T->Ltag = thread; // 前趋线索
T->Lchild = pre; // 当前结点T 找前趋pre
}
if (!pre->Rchild) {
pre->Rtag = thread; // 后继线索
pre->Rchild = T; // pre结点找后继T (T在递归遍历过程中可以是树上任意一个结点)
}
pre = T; // 始终指向刚刚访问过的结点 即下一轮当前结点的上一个结点
inThread(T->Rchild); //递归右孩子线索化
}
}
/**
* 完整化线索二叉树 添加头结点 设置结束结点指向
* @param head 线索二叉树的头结点
* @param T 原本的二叉树
*/
void inThreadTree(Bnode *head, Bintree T) {
if (!T) {
// 若二叉树为空，则将Lchild和Rchild指向自己(双向链表head前趋和后继指向自己，链表为空)
head->Lchild = head;
head->Ltag = link;
head->Rchild = head;
head->Rtag = link;
} else {
// 起始工作
head->Lchild = T; // head左指针记录下树根，这样在inThreadTraverse方法中只需要传入head就够了
head->Ltag = link;
head->Rchild = head; // head右指针一定会线索化，先赋初值指向自己(head)
head->Rtag = thread;
pre = head; // pre 赋初值，指向head，然后中序线索化
// 中序线索化
inThread(T);
// 收尾工作
pre->Rtag = thread; // 线索化之后，pre是遍历的最后一个结点
pre->Rchild = head;
head->Rchild = pre; // 在起始工作中，先给了head->Rchild一个初值，这里赋给了真正的值
}
}
/**
* 中序遍历线索二叉树
* @param head 线索二叉树的头结点
*/
void inThreadTraverse(Bintree head) {
Bnode *p = head->Lchild; // 起始工作中设置了head->Lchild为树根
// 1.满足树为空的情况，树空时设置了head左右孩子都指向自己
// 2.满足循环终结条件，收尾工作中设置了最后一个节点的Rchild为head
while (p != head) {
// 寻找线索开头 从根寻找到最左结点
while (p->Ltag == link) {
p = p->Lchild;
}
cout << p->data << " ";
// 根据线索，用链表的方式遍历
while (p->Rtag == thread && p->Rchild != head) {
p = p->Rchild;
cout << p->data << " ";
} // 该循环一般在 p->Rtag == link 时跳出，说明右边是一棵树，需要重新寻找右子树的最左节点
p = p->Rchild;
}
}
/**
* 普通中序遍历
*/
void inOrder(Bintree T) {
if (T) {
inOrder(T->Lchild);
cout << T->data << " ";
inOrder(T->Rchild);
}
}
int main() {
// 创建树
Bintree bintree;
cout << "输入树的根结点: ";
createBintree(bintree);
cout << endl;
// 普通中序遍历
cout << "普通中序遍历" << endl;
inOrder(bintree);
cout << endl << endl;
// 线索二叉树并遍历
Bnode *head = (Bnode *) malloc(sizeof(Bnode)); // 头结点
inThreadTree(head, bintree);
cout << "线索化后中序遍历" << endl;
inThreadTraverse(head);
cout << endl << endl;
return 0;
}
输入树的根结点: 1
1 左结点(#结束): 2
2 左结点(#结束): #
2 右结点(#结束): #
1 右结点(#结束): 3
3 左结点(#结束): 4
4 左结点(#结束): #
4 右结点(#结束): #
3 右结点(#结束): 5
5 左结点(#结束): #
5 右结点(#结束): #
普通中序遍历
2 1 4 3 5
线索化后中序遍历
2 1 4 3 5
误区
本来想用做个尝试，在线索化二叉树后，随便取一个结点，输出其前趋和后继。
原本采用先序遍历的方式寻找：
void preOrderSearch(Bintree T, char target) {
if (T) {
if (T->data == target) {
if (T->Ltag == thread) cout << "前趋结点：" << T->Lchild->data << endl;
if (T->Rtag == thread) cout << "后继结点：" << T->Rchild->data << endl;
return;
}
preOrderSearch(T->Lchild, target);
preOrderSearch(T->Rchild, target);
}
}
错误点：if (T) 的条件控制已经不对了，线索化之后，不存在空结点了。
