#include
　　#include
　　#include
　　typedef char DataType;/*定义DataType类型*/
　　typedef enum {Link,Thread}PointerTag;
　　typedef struct node{
　　DataType data;
　　struct node *lchild, *rchild;/*左右孩子子树*/
　　PointerTag LTag,RTag;
　　}BiThrNode; /*结点类型*/
　　typedef BiThrNode *BiThrTree ;/*二叉树类型*/
　　void CreatBinTree(BiThrTree *T)
　　{ /*构造二叉链表,注意:输入序列是先序序列*/
　　char ch;
　　if ((ch=getchar())==' ')
　　*T=NULL;
　　else{ /*读入非空格*/
　　*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/
　　(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
　　CreatBinTree(&(*T)->lchild); /*构造左子树 */
　　CreatBinTree(&(*T)->rchild); /*构造右子树*/
　　}
　　}
　　BiThrTree pre;/*全局变量*/
　　void InThreading(BiThrTree p)
　　{
　　if(p)
　　{InThreading(p->lchild);/*左子树线索化*/
　　if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驱线索*/
　　if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后继线索*/
　　pre=p;/*保持pre指向p*/
　　InThreading(p->rchild);/*右子树线索化*/
　　}
　　}
　　int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
　　/*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/
　　{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
　　(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/
　　(*Thrt)->rchild=*Thrt;/*右指针回指*/
　　if(!T) (*Thrt)->lchild=*Thrt;
　　else
　　{ (*Thrt)->lchild=T;pre=*Thrt;
　　InThreading(T);/*中序遍历进行中序线索化*/
　　pre->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/
　　(*Thrt)->rchild=pre;
　　}
　　return 1;
　　}
　　int print(BiThrTree e)
　　{printf("%d %c %d\n",e->LTag,e->data,e->RTag);return 1;}

　　int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
　　/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树*/
　　{BiThrTree p;
　　p=T->lchild;/*p指向根结点*/
　　while(p!=T)/*空树或遍厉结束时，p==T*/
　　{while(p->LTag==Link) p=p->lchild;
　　if(!visit(p)) return 0;/*打印*/
　　while(p->RTag==Thread&&p->rchild!=T)
　　{p=p->rchild;visit(p);}/*访问后继结点*/
　　p=p->rchild;
　　}
　　return 1;
　　}
　　void main()
　　{ /*测试程序*/
　　BiThrTree T,Thrt;
　　CreatBinTree(&T);
　　InOrderThreading(&Thrt,T);
　　InOrderTraverse(Thrt,print);
　　}
　　/*可输入"-+a *b -c d /e f "来测试(注意空格)*/

　　相关链接：