对于一个普通的二叉树
我们可以很明显的看到，在一个二叉树中，会有许多的空结点，而这些空结点必然会造成空间的浪费，为了解决这个问题，我们可以引入线索二叉树，把这些空结点利用起来，利用 ‘^’ 记录给定结点的前驱后继，那么问题就来了，该如何建立呢？
前面我们说过四种的遍厉方法，我应该用哪种方法来建立线索二叉树呢？
经过逐一的分析，我们发现利用中序遍历方法能够有效地建立起线索二叉树
我们先看一看在上述二叉树中中序遍历的结果
H D I B E A F C G
红色的结点为有空结点
在空结点中储存前驱与后继
单面对这样的一种二叉树时又怎么办呢？
中序遍历为
F D G B A C E
我们可以看到在b结点与结点 c出只有一个空结点
那机器该如何判断放的是线索还是指针呢？
为了解决这种问题，我们可以吧树的每个结点进行扩容
ltag : 为0时，表示lchild指向改结点的左孩子； 为1时，表示lchild指向该结点的前驱
rtag：为0时，表示rchild指向该结点的右孩子；为1时，表示rchild指向该结点的后继
线索二叉树的代码实现：
#include<iostream>
using namespace std; typedef char ElemType; //线索存储标志位
//Link 为0时，表示指向左右孩子的指针
//Thread 为1时，表示指向前驱后继的线索
typedef enum{Link, Thread} PointerTag; typedef struct BitThrNode
{
char data;
struct BitThrNode *lchild, *rchild;
PointerTag ltag;
PointerTag rtag;
}BitThrNode, *BitThrTree; //全局变量，指向刚刚访问过的节点
BitThrTree pre; //利用前序遍历创建二叉树
void createBitThrTree(BitThrTree *T) //根节点的地址
{
char c;
cin >> c;
if(c =='-')
{
*T=NULL;
}
else
{
*T=new BitThrNode;
(*T)->data=c;
(*T)->ltag=Link;
(*T)->rtag=Link;
createBitThrTree(&(*T)->lchild);
createBitThrTree(&(*T)->rchild);
}
} //中序遍历线索化
void InThreading(BitThrTree T)
{
if(T)
{
InThreading(T->lchild);//递归左孩子线索化
//结点处理
if(!T->lchild)
{
T->ltag=Thread;
T->lchild=pre;
} if(!pre->rchild)
{
pre->rtag=Thread;
pre->rchild=T;
} pre=T; InThreading(T->rchild);//递归右孩子线索化
}
} void InorderThreading(BitThrTree *p, BitThrTree T)
{
*p=new BitThrNode();
(*p)->ltag=Link;
(*p)->rtag=Thread;
(*p)->rchild=*p;
if(!T)
{
(*p)->lchild=*p;
}
else
{
(*p)->lchild=T;
pre=*p;
InThreading(T);
pre->rchild=*p;
pre->rtag=Thread;
(*p)->rchild=pre;
}
} void visit(char c)
{
cout<<c<<endl;
} //中序遍历二叉树非递归
void InorderTravel(BitThrTree T)
{
BitThrTree p;
p=T->lchild;
while(p!=T)
{
while(p->ltag==Link)
{
p=p->lchild;
}
visit(p->data); while(p->rtag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data);
}
p=p->rchild;
}
} int main()
{
BitThrTree T=NULL;
BitThrTree p;
createBitThrTree(&T);
InorderThreading(&p,T)； cout<<"中序遍历输出结果为"<<endl;
InorderTravel(p); return 0;
}