在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
概念
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题
产生背景
通过观察上面的二叉链表，存在着若干个没有指向的空指针域。对于一个有n个节点的二叉链表，每个节点有指向左右节点的2个指针域，整个二叉链表存在2n个指针域。而n个节点的二叉链表有n-1条分支线，那么空指针域的个数=2n-(n-1) = n+1个空指针域，从存储空间的角度来看，这n+1个空指针域浪费了内存资源。
从另外一个角度来分析，如果我们想知道按中序方式遍历二叉链表时B节点的前驱节点或者后继节点时，必须要按中序方式遍历二叉链表才能够知道结果，每次需要结果时都需要进行一次遍历，是否可以考虑提前存储这种前驱和后继的关系来提高时间效率呢？
综合以上两方面的分析，可以通过充分利用二叉链表中的空指针域，存放节点在某种遍历方式下的前驱和后继节点的指针。我们把这种指向前驱和后继的指针成为线索，加上线索的二叉链表成为线索链表，对应的二叉树就成为“线索二叉树(Threaded Binary Tree)” 。
我们对二叉树进行中序遍历（不了解二叉树遍历请参考二叉树介绍），
将所有的节点右子节点为空的指针域指向它的后继节点
所有节点左指针域为空的指针域指向它的前驱节点
通过观察上图，可以看出，线索二叉树，等于是把一棵二叉树转变成了一个“特殊的双向链表“，这样对于我们的新增、删除、查找节点带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。
中序遍历: HDIBJEAFCG
线索化带来的问题
思考: 我们如何区分⼀一个结点的左孩⼦子指针指向的是左孩⼦子还是前驱结点了了
线索化带来标识位
lchild,rchild:表示左右孩子
LTag,RTag:表示是否标记
Link==0表示指向左右孩子指针,
Thread==1表示指向前驱或后继的线索
typedef enum {Link,Thread} PointerTag;
所以通过线索可以生成新的二叉树
线索二叉树存储结点结构
/* 线索二叉树存储结点结构*/
typedef struct BiThrNode{
//数据
CElemType data;
//左右孩子指针
struct BiThrNode *lchild,*rchild;
//左右标记
PointerTag LTag;
PointerTag RTag;
}BiThrNode,*BiThrTree;
中序遍历线索二叉树T, 将其中序线索化,Thrt指向头结点
/*
8.3 中序遍历二叉树T, 将其中序线索化,Thrt指向头结点
*/
BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化*/
void InThreading(BiThrTree p){
/*
InThreading(p->lchild);
.....
InThreading(p->rchild);
*/
if (p) {
//递归左子树线索化
InThreading(p->lchild);
//无左孩子
if (!p->lchild) {
//前驱线索
p->LTag = Thread;
//左孩子指针指向前驱
p->lchild = pre;
}else
{
p->LTag = Link;
}
//前驱没有右孩子
if (!pre->rchild) {
//后继线索
pre->RTag = Thread;
//前驱右孩子指针指向后继(当前结点p)
pre->rchild = p;
}else
{
pre->RTag = Link;
}
//保持pre指向p的前驱
pre = p;
//递归右子树线索化
InThreading(p->rchild);
}
}
线索二叉树-双向链表（中序）
/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if (! *Thrt) {
exit(OVERFLOW);
}
//建立头结点;
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread;
//右指针回指向
(*Thrt)->rchild = (*Thrt);
/* 若二叉树空,则左指针回指 */
if (!T) {
(*Thrt)->lchild=*Thrt;
}else{
(*Thrt)->lchild=T;
pre=(*Thrt);
//中序遍历进行中序线索化
InThreading(T);
//最后一个结点rchil 孩子
pre->rchild = *Thrt;
//最后一个结点线索化
pre->RTag = Thread;
(*Thrt)->rchild = pre;
}
return OK;
}
中序遍历二叉线索树T（双向链表）
##/*中序遍历二叉线索树T*/
Status InOrderTraverse_Thr(BiThrTree T){
BiThrTree p;
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=p->rchild;
}
return OK;
}
本质
二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。
优势与不足
优势
(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
(2)任意一个结点都能直接找到它的前驱和后继结点。
不足
(1)结点的插入和删除麻烦，且速度也较慢。
(2)线索子树不能共用。
网友评论