/*中序线索二叉树   2014/11/14 */#include<stdio.h>#include<stdlib.h>typedef struct BiTrNoDe{     char data;     struct BiTrNoDe *lchild;     struct BiTrNoDe *rchild;     unsigned ltag : 1;     //LINK是1      此处也可以用枚举类型或者宏定义去写      unsigned rtag : 1;    //threading是0 }BiTrNode,*BiThre;                //-----------------------------------------------------------BiThre pre;        //声明这个指向前驱的pre ,给予其全局变量。                   //比如 DBAECF这个中序表示法   B的前驱就是D，同理A便是B的后继                  //-----------------------------------------------------------void InitBiTree(BiThre *T);                   //创建一个二叉树 void InorderThread(BiThre *p,BiThre T);       //为了弄出一个头指针 void Inthreading(BiThre T);                  //中序线索后二叉树 void InorderTraverse(BiThre T);                //遍历二叉树 int main(void){ BiThre T = NULL,P = NULL;//创建2个结构体的指针，分别是T和P  InitBiTree(&T);   //取指针的指针是为了操作这个指针。  InorderThread( &P,T); //操作完毕后的指针可以直接拿来用  InorderTraverse(P); return 0;}//用前序递归创建一颗树 void InitBiTree(BiThre *T){     char c;     scanf("%c",&c);     if(‘ ‘ == c)     {      *T = NULL;     }     else{          *T = (BiTrNode*)malloc(sizeof(BiTrNode));          (*T)->data =http://www.mamicode.com/ c;          (*T)->ltag = 1;          (*T)->rtag = 1;          InitBiTree(&(*T)->lchild);          InitBiTree(&(*T)->rchild);    }}void InorderThread(BiThre *p,BiThre T){     *p = (BiTrNode*)malloc(sizeof(BiTrNode));     if(!*p)exit(-1);    //生成失败就退出     (*p)->ltag = 1;        //------------------------------------------     (*p)->rtag = 0;        //设置它的左tag为LINK，右为thread                         //------------------------------------------     (*p)->rchild = (*p);           if( T )         //这个T是创建的那棵树的根.如果它不是空树      {          (*p)->lchild = T;           pre = (*p );           //这个pre是指向的p，在下面执行的过程中使最左边的那个结点指向p            Inthreading(T);           pre->rchild=*p;        // -------------------------------------------------------------------           pre->rtag= 0;          //  这3步表示结束后把p指向最右边那个结点，然后把最后边的节点指给pre。         (*p)->rchild= pre;  //---------------------------------------------------------------------        }     else{          (*p)->rchild = (*p);     } }  //递归遍历并线索化。 void Inthreading(BiThre T){     if( T )           //如果不为空的就执行，当他空的的时候递归也就结束开始返回了。                  {          Inthreading(T->lchild);   //搜索到左边的最后一个节点            if(!T->lchild){     //指向前驱                T->ltag = 0;             T->lchild = pre;          }          if(!pre->rchild){       //指向后继             pre->rtag = 0;               pre->rchild = T;        }           pre = T;          Inthreading(T->rchild);   //和上面的同理      } } void InorderTraverse(BiThre T)  //这里形参写的不好应该写P ，这个函数里出现的T全是P的意思。。 {     BiThre p;     p = T->lchild;      while(p != T)     {          while(p->ltag == 1)          {               p = p->lchild;          }          printf("%c",p->data);          while(p->rtag == 0 && p->rchild!=T)//搜索他的后继，直到没有后继           {               p = p->rchild;               printf("%c",p->data);          }          p = p->rchild; //指到"根"的右子树      }}