线索二叉树，或者说，对二叉树线索化，实质上就是遍历一棵二叉树，在遍历的过程中，检查当前结点的左、右指针域是否为空。如果为空，将它们改为指向前驱结点或后继结点的线索。

当以二叉链表作为存储结构时，只能找到左右孩子信息，而不能直接得到结点在任意序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。 解决此问题最简单的办法是在每个节点上增加两个指针域fwd和bkwd，分别指示结点依任意次序遍历时得到前驱和后继信息。显然这样做使得结构的存储密度 大大降低，另一方面，在有n个结点的二叉链表中必定存在n+1个空链域。由此设想能否利用这些空链域来存放前驱和后继信息。

试做如下规定：若结点有左子树，则其lchild域指向其左孩子，否则域指示其前驱，若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域。

lchild LTag data RTag rchild

其中：

LTag=0  lchild域指示结点的左孩子LTag=1  lchild域指示结点的前驱RTag=0  rchild域指示结点的右孩子RTag=1  rchild域指示结点的后继

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树。对二叉树进行某种次序遍历使其变为线索二叉树的过程叫做线索化。

头文件：

/*****************************************************************************************************  *Copyright: Yue Workstation  *  *FileName: IndexTree.h  *  *Function: 线索二叉树数据结构定义  *  *Author: Abel Lee  *  *CreateOn: 2012-2-19  *  *Log: 2012-2-19 由Abel Lee创建  *****************************************************************************************************/ #ifndef INDEX_TREE_H #define INDEX_TREE_H #include "global.h" typedef enum{Link,Thread} PointerTag;     //指针标志 typedef int DataType; typedef struct BiThreTree {               //定义结点元素     PointerTag LTag,RTag;     DataType data;     struct BiThreTree *lchild,*rchild; }BiThreTree; BiThreTree *pre;                     //全局变量，用于二叉树的线索化 BiThreTree *CreateTree(void); void InThread(BiThreTree *T); BiThreTree *InOrderThrTree(BiThreTree *T); void InThrTravel(BiThreTree *Thre); #endif

源文件：

/*****************************************************************************************************  *Copyright:Yue Workstation  *  *FileName: IndexTree.c  *  *Function: 线索二叉树操作  *  *Author:Abel Lee  *  *CreateOn:2012-2-19  *  *Log:2011-5-3 由Abel Lee创建  *****************************************************************************************************/ #include "../inc/IndexTree.h" /****************************************************************************************************  *Function Name: CreateTree  *  *Function: 按先序输入建立二叉树  *  *Parameter:   无  *  *Return Value:成功返回树的指针，失败返回NULL  *  *Author:Abel Lee  *  *Log:2012-2-19  ***************************************************************************************************/ BiThreTree *CreateTree(void) {     BiThreTree *T;     DataType e;     scanf("%d",&e);     if(e==0)     {         T=NULL;     }     else     {         T=(BiThreTree *)malloc(sizeof(BiThreTree));         T->data=e;         T->LTag=Link;          //初始化时指针标志均为Link         T->RTag=Link;         T->lchild=CreateTree();         T->rchild=CreateTree();     }     return T; } /****************************************************************************************************  *Function Name: InThread  *  *Function:  *  *Parameter:   无  *  *Return Value:成功返回树的指针，失败返回NULL  *  *Author:Abel Lee  *  *Log:2012-2-19  ***************************************************************************************************/ void InThread(BiThreTree *T) {     BiThreTree *p;     p=T;     if(p)     {         InThread(p->lchild);         if(!p->lchild)         {             p->LTag=Thread;             p->lchild=pre;         }         if(!pre->rchild)         {             pre->RTag=Thread;             pre->rchild=p;         }         pre=p;         InThread(p->rchild);     } } /****************************************************************************************************  *Function Name: InOrderThrTree  *  *Function: 中序线索化二叉树  *  *Parameter:   T:二叉树指针  *  *Return Value:成功返回树的指针，失败返回NULL  *  *Author:Abel Lee  *  *Log:2012-2-19  ***************************************************************************************************/ BiThreTree *InOrderThrTree(BiThreTree *T) {     BiThreTree *Thre;                  //Thre为头结点的指针     Thre=(BiThreTree *)malloc(sizeof(BiThreTree));     if(Thre == NULL)     {         perror("Thre == NULL,malloc error!\n");         return NULL;     }     Thre->lchild=T;     Thre->rchild=Thre;     pre=Thre;     InThread(T);     pre->RTag=Thread;     pre->rchild=Thre;     Thre->rchild=pre;     return Thre; } /****************************************************************************************************  *Function Name: InThrTravel  *  *Function: 中序遍历二叉树  *  *Parameter:   Thre:二叉树指针  *  *Return Value:成功返回树的指针，失败返回NULL  *  *Author:Abel Lee  *  *Log:2012-2-19  ***************************************************************************************************/ void InThrTravel(BiThreTree *Thre) {     BiThreTree *p;     p=Thre->lchild;     while(p!=Thre)                  //指针回指向头结点时结束     {         while(p->LTag==Link)           p=p->lchild;         printf("%4d",p->data);         while(p->RTag==Thread&&p->rchild!=Thre)         {             p=p->rchild;             printf("%4d",p->data);         }         p=p->rchild;     } }