线索二叉树的原理：
如图所示，我们会发现许多指针域并没有充分利用起来，而是有很多空指针域。
如何利用这些空指针域呢？
我们可以把这颗二叉树做中序遍历后，将所有空指针域的rchild，改为指向它的后继节点
改进如图：
同理：我们可以把空指针域的lchild指向它的前驱节点。
其实一颗线索二叉树，等于是把一颗二叉树变成一个双向链表，这样对我们插入删除查找节点带来了方便，我们对二叉树以某种次序遍历使其变成线索二叉树的过程称为线索化
但是我们如何知道一个节点的lchild是指向左子节点还是前驱呢，同理rchild也是如此。我们需要给lchild和rchild设置两个标志来决定指向前驱后继或子节点。因此，我们设置了两个标志ltag、rtag。ltag和rtag是只能存0或1的布尔类型变量。
节点的结构：
其中：
ltag：为0时，lchild指向左子节点，为1时，lchild指向前驱。
rtag：为0时，rchild指向右子节点，为1时，rchild指向后继驱。
线索二叉树的实现：
二叉树的线索存储结构：
typedef enum {Link,Thread} PointerTag; /*Link==0表示指向左右孩子指针*/
/*Thread==1表示指向前驱或后继的线索*/
typedef struct BiThrNode
{
TElemType data;
structBiThrNode * lchild,* rchild;
PointerTag lTag;
PointerTag rTag;
}BiThrNode,*BiThrTree;
线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索，由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。
中序遍历线索化的递归函数：
BiThrea pre //全局变量，始终指向刚刚访问过的节点
//中序遍历进行中序线索化
void InThreading(BiThrTree p) //递归左子树线索化
{
if(p)
{
if(!p->lchild) //没有左孩子
{
p->lTag=Thread; //前驱线索
p->lchild=pre; //左孩子指针指向前驱
}
if(!pre->rchild) //前驱没有左孩子
{
pre->rTag=Thread; //后继线索
pre->rchild=p; //前驱右孩子指针指向后继（当前节点p）
}
pre=p; //保持pre指向p的前驱
InThreading(p->rchild); //递归右子树线索化
}
}
实现代码：
#include<iostream>
usingnamespace std;
typedefenum{Link=1,Thread}PointerTag;
template<classT>
structBiThrNode
{
T data;
BiThrNode<T> * lchild, * rchild;
PointerTag lTag,rTag;
BiThrNode():data(T()),lchild(NULL),rchild(NULL),lTag((PointerTag)NULL),rTag((PointerTag)NULL){}
};
template<classT>
classThrBree
{
public:
ThrBree():root(NULL),pre(NULL){}
void InitThrBree()
{
InitBree(root);
InitThrBree(root);
}
void display()
{
display(root);
}
private:
void InitBree(BiThrNode<T> *&t);
void InitThrBree(BiThrNode<T> *&t);
void display(BiThrNode<T> *&t);
BiThrNode<T> * root;
BiThrNode<T> * pre;
};
template<classT>
voidThrBree<T>::InitBree(BiThrNode<T> * &t)
{
BiThrNode<T> *p=newBiThrNode<T>;
t=p;
cout<<"请输入数据："<<endl;
cin>>p->data;
cout<<"选择节点是否有左子节点-- 1：有，0没有"<<endl;
int i;
cin>>i;
switch(i)
{
case 1:
p->lTag=Link;
InitBree(p->lchild);
break;
case 0:
break;
}
cout<<"选择节点是否有右子节点-- 1：有，0没有"<<endl;
cin>>i;
switch(i)
{
case 1:
p->rTag=Link;
InitBree(p->rchild);
break;
case 0:
break;
}
pre=t->lchild;
}
template<classT>
voidThrBree<T>::InitThrBree(BiThrNode<T> * &t)
{
if(t)
{
InitThrBree(t->lchild);
if(!t->lchild)
{
t->lTag=Thread;
t->lchild=pre;
}
if(!pre->rchild)
{
pre->rTag=Thread;
pre->rchild=t;
}
pre=t;
InitThrBree(t->rchild);
}
}
template<classT>
voidThrBree<T>::display(BiThrNode<T> * &t)
{
BiThrNode<T> * p=t;
while(p)
{
while(p->lTag==Link)
{
p=p->lchild;
}
cout<<p->data<<",";
while(p->rTag==Thread&&p->rchild!=NULL)
{
p=p->rchild;
cout<<p->data<<",";
}
p=p->rchild;
}
}
intmain()
{
ThrBree<int> t;
t.InitThrBree();
t.display();
return 0;
}
参考：《大话数据结构》