//* * * * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :4  (4_3)                       *
//*PROGRAM          :線索二叉樹                     *
//*CONTENT          :初始化，中序線索化，遍歷線索樹 *
//* * * * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
enum PointerTag{Link,Thread};
	//Link==0:指針,Thread==1:線索
typedef struct  BiThrNode      //定義線索二叉樹節點結構
{char  data;                     //數據域
 struct BiThrNode *lchild,*rchild; //左右孩子指針
 PointerTag LTag,RTag;            //左右標志，指明是指針還是線索
}BiThrNode,*BiThrTree;
void CreateBiThrTree(BiThrTree &);    //生成一個二叉樹
void InOrder_Thr(BiThrTree);          //對中序線索二叉樹進行遍歷
void InOrderThreading(BiThrTree &,BiThrTree );  //對二叉樹進行中序線索化  
void InThreading(BiThrTree);
BiThrTree pre;    //全局變量，在遍歷時用來指示前驅結點
void main()
{BiThrTree T,Thrt;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序實現二叉樹的操作。\n");
 printf("可以進行建立二叉樹，遞歸先序、中序、后序遍歷等操作。\n");
 //----------------------------------------------------
 printf("請將先序遍歷二叉樹的結果輸入以建立二叉樹。\n");
 printf("對于葉子結點以空格表示。\n");
 printf("例如:abc  de g  f   (回車)，建立如下二叉樹：\n");
 printf("           a      \n");
 printf("          /       \n");
 printf("         b        \n");
 printf("        / \\       \n");
 printf("       c   d      \n");
 printf("          / \\     \n");
 printf("         e   f    \n");
 printf("          \\       \n");
 printf("           g      \n");
 CreateBiThrTree(T);       //生成二叉樹  
 InOrderThreading(Thrt,T); //對二叉樹進行中序線索化
 if(Thrt->lchild==Thrt) printf("二叉樹為空!\n"); //該二叉樹為空
 else {printf("遍歷二叉樹為:");  //否則對該二叉樹進行遍歷
       InOrder_Thr(Thrt);
       printf("\n");getchar();
      }
 printf("程序運行結束，按任意鍵退出!\n");
 getchar();
}

void CreateBiThrTree(BiThrTree &T)
{//生成一棵二叉樹，該二叉樹以T為根結點
 char ch;
 scanf("%c",&ch);    //讀入一個字符
 if(ch==' ') T=NULL;
 else {T=(BiThrNode *)malloc(sizeof(BiThrNode)); //生成一個新結點
       T->data=ch;
       CreateBiThrTree(T->lchild);  //生成左子樹
       CreateBiThrTree(T->rchild);  //生成右子樹
      }
}

void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//對二叉樹T進行中序線索化，生成以Thrt為頭結點的線索二叉樹
 Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); //生成頭結點
 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;    //頭結點的右指針指向遍歷時的最后一個結點
      }
}
void InThreading(BiThrTree p)
{if(p)
   {InThreading(p->lchild);  //線索化左子樹
    if(!p->lchild)           //若左孩子為空，進行前驅線索化
       {p->LTag=Thread; p->lchild=pre;}
    else p->LTag=Link;       //否則，LTag標志為Link
    if(!pre->rchild)        //若前驅的右孩子為空，進行后繼線索化
       {pre->RTag=Thread; pre->rchild=p;}
    else pre->RTag=Link;    //否則，RTag標志為Link
    pre=p;                  //修改前驅指針
    InThreading(p->rchild); //線索化右子樹
   }
}
void InOrder_Thr(BiThrTree Thrt)
{BiThrTree p;
 p=Thrt->lchild;      //p指向根結點
 while(p!=Thrt)       //空樹或遍歷結束時，p==Thrt 
   {while(p->LTag==Link) p=p->lchild; //尋找最左下的左子樹為空的結點
    printf("%c",p->data);             //訪問該結點
    while(p->RTag==Thread&&p->rchild!=Thrt)
       {p=p->rchild;                  //訪問后繼結點
	printf("%c",p->data);
       }
    p=p->rchild;
   }
}