1. #include<stdio.h>
    2. #include<stdlib.h>
    3. typedef enum{link,thread}PionerTag;
    4. typedef struct BiThrNode{
    5.     char data;//数据域
    6.     struct BiThrNode*L,*R;//左右孩子指针域
    7.     PionerTag Ltag,Rtag;
    8. }BiThrNode,*BiThrTree;
    9. BiThrTree pre = NULL;//定义一个指向线索树所指位置前一个位子的指针域
    10. void PreCreatBiTree(BiThrTree *t);//前序创建二叉树
    11. void MidThreading(BiThrTree p);//中序二叉树线索化
    12. void MidThrShow(BiThrTree t);//中序遍历线索二叉树
    13. int main(){
    14.     BiThrTree t;
    15.     printf("输入任意字符，输入#为空\n");
    16.     PreCreatBiTree(&t);
    17.     printf("\n");
    18.     MidThreading(t);
    19.     printf("中序遍历线索二叉树:\n");
    20.     MidThrShow(t);
    21.     printf("\n");
    22. }
    23. void PreCreatBiTree(BiThrTree *t){
    24.     char ch;
    25.     scanf("%c",&ch);
    26.     if(ch!='#')
    27.     {
    28.         if(!((*t) = (BiThrTree)malloc(sizeof(BiThrNode))))
    29.         {
    30.             printf("申请空间失败，程序运行失败：\n");
    31.             return;
    32.         }
    33.         else
    34.         {
    35.             (*t)->data = ch;
    36.             PreCreatBiTree(&(*t)->L);
    37.             PreCreatBiTree(&(*t)->R);
    38.         }
    39.     }
    40.     else
    41.     {
    42.         *t = NULL;
    43.     }
    44. }
    45. void MidThreading(BiThrTree p){
    46.     if(p)//如果结点p存在
    47.     {
    48.         MidThreading(p->L);//递归遍历左孩子，直到左孩子不存在
    49.         if(!p->L)
    50.         {
    51.             p ->Ltag = thread;//将当前结点标志域设为thread即1
    52.             p ->L = pre;//将当前左孩子指针域指向上逻辑上访问的前一个结点
    53.         }
    54.         else p->Ltag = link;
    55.         if(pre&&!pre->R)//逻辑上访问的前一个结点存在，并且逻辑上访问前一个结点不存在右孩子
    56.         {
    57.             pre ->Rtag = thread;//逻辑上访问的前一个结点的标志域设为thread即1
    58.             pre ->R = p;//逻辑上访问的前一个结点的右孩子指向逻辑上下一个访问的结点
    59.         }
    60.         else p->Rtag = link;
    61.         pre = p;//逻辑上访问的前一个结点指向逻辑上访问的下一个结点
    62.         MidThreading(p ->R);//依次递归遍历当前结点的右孩子
    63.     }
    64. }
    65. void MidThrShow(BiThrTree t){
    66.     while(t)
    67.     {
    68.         while(t->Ltag==link)
    69.         {
    70.             t = t->L;
    71.         }
    72.         printf("%c",t->data);
    73.         while(t->Rtag==thread&&t->R!=NULL )
    74.         {
    75.             t = t->R;
    76.             printf("%c",t->data);
    77.         }
    78.         t = t->R;
    79.     }
    80. }