1.前言
在n个结点的⼆叉链表中，必定有n+1个空链域。⽽遍历运算是最重要的，也是最常⽤的运算⽅ 法，之前的⽆论是递归与非递归的算法实现遍历效率其实都不算⾼。
现有⼀棵结点数⽬为n的⼆叉树，采⽤⼆叉链表的形式存储。对于每个结点均有指向左右孩⼦的 两个指针域，⽽结点为n的⼆叉树⼀共有n-1条有效分⽀路径。那么，则⼆叉链表中存在2n-(n-1)=n+1个 空指针域。那么，这些空指针造成了空间浪费。
若将遍历后对应的有关前驱和后继预存起来 ，则从第一个结点开始就能很快“顺藤摸瓜 ”而遍历整个树。
例如如图：
如图所示⼆叉树的中序遍历结果 为DBEAC，可以得知A的前驱结点为E，后继结点为C。但是，这种关系的获得是建⽴在完成遍历后得到的，那么可不可以在建⽴⼆叉树时就记录下前驱后继的关系呢，那么在后续寻找前驱结点和后继结点时将大大提升效率。
2.相关术语
线索： 指向结点前驱或后继的指针
线索链表： 以五域线索结点构成的二叉链表
线索二叉树： 加上线索的二叉树
线索化： 对二叉树以某种次序遍历使其变为线索二叉树的过程
3.规则
现将某结点的空指针域指向该结点的前驱后继，定义规则如下：
若结点的左⼦树为空，则该结点的左孩⼦指针指向其前驱结点。
若结点的右⼦树为空，则该结点的右孩⼦指针指向其后继结点。
这种指向前驱和后继的指针称为线索。将⼀棵普通⼆叉树以某种次序遍历，并添加线索的过程称为线索化。
可以将⼀棵⼆叉树线索化为⼀棵线索⼆叉树，那么新的问题产⽣了。我们如何区分⼀个结点的 lchild指针是指向左孩⼦还是前驱结点呢？
结点结构：
为了解决这⼀问题，现需要添加标志位ltag，rtag。
并定义规则如下：
ltag为0时，指向左孩⼦，为1时指向前驱
rtag为0时，指向右孩⼦，为1时指向后继
4.代码呈现
以中序遍历为例
1.结点结构
/*假设一个二叉树含有n个结点，采用链式存储，一共会有2n个指针域，有n+1的指针域为NULL，有n-1个指针有数值
会造成极大的空间浪费
以中序为例 如何快速的找到某个结点的前驱和后继
规则如下：如果一个结点的左孩子为空，左孩子指针指向其前驱
如果一个结点的右孩子为空，右孩子指针指向其后继
根据遍历序列不同，线索也分为三类：中序线索化，先序线索化，后序线索化
线索化：内存的优化
*/
//二叉链表的结点结构
typedef struct BTNode
{
char data;
struct BTNode* left;
struct BTNode* right;
int lflag, rflag;
}BTNode, *Btree;
BTNode * pre = NULL;
int flag; //0是插入左孩子 1是插入右孩子2.初始化结点插入
Btree initTree(char x)
{
BTNode *r = new BTNode;
if (r == NULL)
{
cout << "defate!" << endl;
return NULL;
}
else
{
r->data = x;
r->left = r->right = NULL;
r->rflag = r->lflag = 0;
return r;
}
}
BTNode *find(Btree r, char fx)
{
if (r == NULL || r->data == fx)
{
return r;
}
if (r->left != NULL && r->lflag == 0)
{
BTNode * f = find(r->left, fx);
if (f != NULL && f->data == fx)
{
return f;
}
}
if (r->right != NULL && r->rflag == 0)
{
BTNode * f = find(r->right, fx);
if (f != NULL && f->data == fx)
{
return f;
}
}
return NULL;
}
void insert(BTNode * r, char x, char fx, int flag)
{
BTNode * f = find(r, fx);//寻找父亲指针
if (f != NULL)
{
BTNode *s = new BTNode;
s->data = x;
s->left = s->right = NULL;
s->rflag = s->lflag = 0;
if (flag == 0)
{
f->left = s;
}
else
{
f->right = s;
}
}
}
3.遍历后添加线索
void inOrder(Btree r)//遍历
{
if (r == NULL && r->lflag == 0)
{
return;
}
if (r->left != NULL && r->rflag == 0)
{
inOrder(r->left);
}
//变成加线索
visit(r);
if (r->right != NULL)
{
inOrder(r->right);
}
}
void visit(Btree r)
{
//该函数的作用是(遍历后)添加线索，线索化结束后再具体找某个点的前驱和后继
//x->lflag=1 前驱就是x->left
//x->lflag=0 x->left是x的左孩子，x左子树中的最右边的结点才是x的前驱（为1则为前驱，为0则判断是不是后继）
//x->rflag=1 后继就是x->right
//x->rflag=0 x->right是x的右孩子，x右子树中的最左边的结点才是x的后继（为1则为后继，为0则判断是不是前驱）
//原来visit可以想象成cout输出遍历完的树
//现在将树想象成一条直线(pre是箭头)，r为第一个遍历出来的元素
//前驱可以通过r找，但是后继只能通过前一个即pre来找后继
if (r->left == NULL)
{
r->left = pre;
r->lflag = 1;//线索
}
if (pre != NULL && pre->right == NULL)
{
pre->right = r;//r是目前的r，pre是上一个r，没有下一个r
pre->rflag = 1;//线索《===》r->rflag = 1
}
pre = r;//当访问完r时，r变成了上一个访问的结点（pre）
}