//* * * * * * * * * * * * * * * * * * * * * * * * * *
//*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      //定義線索二叉樹節(jié)點(diǎn)結(jié)構(gòu)
{char  data;                     //數(shù)據(jù)域
 struct BiThrNode *lchild,*rchild; //左右孩子指針
 PointerTag LTag,RTag;            //左右標(biāo)志，指明是指針還是線索
}BiThrNode,*BiThrTree;
void CreateBiThrTree(BiThrTree &);    //生成一個(gè)二叉樹
void InOrder_Thr(BiThrTree);          //對(duì)中序線索二叉樹進(jìn)行遍歷
void InOrderThreading(BiThrTree &,BiThrTree );  //對(duì)二叉樹進(jìn)行中序線索化  
void InThreading(BiThrTree);
BiThrTree pre;    //全局變量，在遍歷時(shí)用來指示前驅(qū)結(jié)點(diǎn)
void main()
{BiThrTree T,Thrt;
 textbackground(3);  //設(shè)定屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序?qū)崿F(xiàn)二叉樹的操作。\n");
 printf("可以進(jìn)行建立二叉樹，遞歸先序、中序、后序遍歷等操作。\n");
 //----------------------------------------------------
 printf("請(qǐng)將先序遍歷二叉樹的結(jié)果輸入以建立二叉樹。\n");
 printf("對(duì)于葉子結(jié)點(diǎn)以空格表示。\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); //對(duì)二叉樹進(jìn)行中序線索化
 if(Thrt->lchild==Thrt) printf("二叉樹為空!\n"); //該二叉樹為空
 else {printf("遍歷二叉樹為:");  //否則對(duì)該二叉樹進(jìn)行遍歷
       InOrder_Thr(Thrt);
       printf("\n");getchar();
      }
 printf("程序運(yùn)行結(jié)束，按任意鍵退出!\n");
 getchar();
}

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

void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//對(duì)二叉樹T進(jìn)行中序線索化，生成以Thrt為頭結(jié)點(diǎn)的線索二叉樹
 Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); //生成頭結(jié)點(diǎn)
 Thrt->LTag=Link; Thrt->RTag=Thread;        //建頭指針
 Thrt->rchild=Thrt;                         //右指針回指
 if(!T) Thrt->lchild=Thrt;                  //若二叉樹空，左指針回指
 else {Thrt->lchild=T; pre=Thrt;            //根結(jié)點(diǎn)作為頭結(jié)點(diǎn)的左孩子
       InThreading(T);                      //中序遍歷進(jìn)行中序線索化
       pre->rchild=Thrt; pre->RTag=Thread;  //最后一個(gè)結(jié)點(diǎn)線索化
       Thrt->rchild=pre;    //頭結(jié)點(diǎn)的右指針指向遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)
      }
}
void InThreading(BiThrTree p)
{if(p)
   {InThreading(p->lchild);  //線索化左子樹
    if(!p->lchild)           //若左孩子為空，進(jìn)行前驅(qū)線索化
       {p->LTag=Thread; p->lchild=pre;}
    else p->LTag=Link;       //否則，LTag標(biāo)志為Link
    if(!pre->rchild)        //若前驅(qū)的右孩子為空，進(jìn)行后繼線索化
       {pre->RTag=Thread; pre->rchild=p;}
    else pre->RTag=Link;    //否則，RTag標(biāo)志為Link
    pre=p;                  //修改前驅(qū)指針
    InThreading(p->rchild); //線索化右子樹
   }
}
void InOrder_Thr(BiThrTree Thrt)
{BiThrTree p;
 p=Thrt->lchild;      //p指向根結(jié)點(diǎn)
 while(p!=Thrt)       //空樹或遍歷結(jié)束時(shí)，p==Thrt 
   {while(p->LTag==Link) p=p->lchild; //尋找最左下的左子樹為空的結(jié)點(diǎn)
    printf("%c",p->data);             //訪問該結(jié)點(diǎn)
    while(p->RTag==Thread&&p->rchild!=Thrt)
       {p=p->rchild;                  //訪問后繼結(jié)點(diǎn)
	printf("%c",p->data);
       }
    p=p->rchild;
   }
}