#include<stdio.h> 
#include<stdlib.h> 
 
#define OK 1 
#define ERROR 0 
 
typedef char ElemType; 
typedef int Status; 
 
/* 定義枚舉類(lèi)型，其值只能是Link和Thread 
 * Link表示的該指針指示的是孩子 
 * Thread表示的是還指針指示的是前驅(qū)或者是后綴 
 * */ 
typedef enum { 
  Link,Thread 
}PointerTag; 
 
typedef struct ThrBiTrNode{ 
  ElemType data; 
  struct ThrBiTrNode *lchild, *rchild; 
  PointerTag rTag, lTag; 
}ThrBiTrNode, *ThrBiTree; 
 
ThrBiTree Pre; 
 
Status InitThreadBinaryTree(ThrBiTree* T){ 
  *T = NULL; 
  return OK; 
} 
//先序建立二叉樹(shù),lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag為L(zhǎng)ink 
Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){ 
  ElemType c; 
  scanf("%c", &c); 
  if( ' ' == c ){ 
    *T = NULL; 
  } 
  else{ 
    *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode)); 
    if( !*T ){ 
      return ERROR; 
    } 
    (*T)->data = c; 
    (*T)->lTag = Link; 
    (*T)->rTag = Link; 
    ThreadBinaryTree_PreOrderInput(&(*T)->lchild); 
    ThreadBinaryTree_PreOrderInput(&(*T)->rchild); 
  } 
  return OK; 
} 
//<<中序遍歷>>對(duì)二叉樹(shù)進(jìn)行<<線索化>>，但是沒(méi)有提供Pre的初始值，只是給出了 
//中間的過(guò)程，遞歸的思想和思考方式。 
//1 線索化左子樹(shù) 
//2 對(duì)雙親節(jié)點(diǎn)處理//遞歸中的base 
//3 線索化右子樹(shù) 
Status InOrderThread(ThrBiTree T){ 
  if( T != NULL ){ 
    InOrderThread(T->lchild);    //線索化左子樹(shù) 
     
    //對(duì)雙親節(jié)點(diǎn)進(jìn)行線索化處理 
    if( T->lchild == NULL ){ //如果左孩子為空，則將lchild作為索引 
            //Pre指向剛剛訪問(wèn)的節(jié)點(diǎn) 
      T->lTag = Thread; 
      T->lchild = Pre; 
    } 
    if( Pre->rchild == NULL ){  //直到現(xiàn)在才知道Pre的后綴是T，所以 
            //要對(duì)Pre進(jìn)行設(shè)置,如果Pre的rchild為空 
            //則將Pre的rchild設(shè)置為后綴，指向T 
      Pre->rTag = Thread; 
      Pre->rchild = T; 
    } 
 
    Pre = T;      //標(biāo)記當(dāng)前的節(jié)點(diǎn)稱(chēng)為剛剛訪問(wèn)過(guò)的節(jié)點(diǎn) 
            //Pre最后會(huì)指向樹(shù)的中序遍歷的最后的 
            //一個(gè)節(jié)點(diǎn) 
 
    InOrderThread(T->rchild);  //線索化右子樹(shù) 
  } 
  return OK; 
} 
//創(chuàng)建中序線索二叉樹(shù),為上個(gè)函數(shù)提供Pre 
Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){ 
  *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode)); 
  if( !headOfTree ) 
    return ERROR; 
  (*headOfTree)->lTag = Link;   //將要指向T 
  (*headOfTree)->rTag = Thread;    //將頭節(jié)點(diǎn)的rchild用于索引 
  (*headOfTree)->rchild = *headOfTree;   //指向自身 
  if( T == NULL ){ 
    (*headOfTree)->lchild = *headOfTree; //若T為空樹(shù)，則頭節(jié)點(diǎn)的lchild 
              //指向自身 
  } 
  else{ 
    (*headOfTree)->lchild = T; 
    Pre = *headOfTree;     //賦值了全局變量Pre 
    InOrderThread(T);        //中序線索化 
    //printf("\n%c\n",Pre->data); 
            //執(zhí)行完InOrderThread之后Pre指向最后 
            //一個(gè)節(jié)點(diǎn) 
    Pre->rTag = Thread;    
    Pre->rchild = *headOfTree; 
    //(*headOfTree)->rchild = Pre; 
  } 
  return OK; 
} 
//對(duì)中序線索化后的線索二叉樹(shù)使用<<非遞歸>>的代碼進(jìn)行中序遍歷 
//并且原來(lái)的遞歸形式的代碼在這里是不再可以進(jìn)行遍歷。 
//  如果二叉樹(shù)沒(méi)有被線索化，也可以使用<<非遞歸>>的代碼進(jìn)行遍 
//  歷的，但是那就需要借助于<<棧>>,但是在線索化之后，對(duì)線索 
//  化的二叉樹(shù)進(jìn)行<<非遞歸>>的遍歷就不再需要棧的輔助。 
Status visit(ElemType c){ 
  printf("%c ", c); 
  return OK; 
} 
Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ 
//headOfTree是T的頭節(jié)點(diǎn)的指針，headOfTree->lchild = T; 
  while( T != headOfTree ){ 
    while( T->lTag == Link ){  //找到樹(shù)(子樹(shù))的最左節(jié)點(diǎn) 
            //用while接替if// 
            //用if理解while// 
      T = T->lchild; 
    }         
    visit(T->data); 
 
    while( T->rTag == Thread && T->rchild != headOfTree){ 
            //這個(gè)while和下面的T=T->rchild 
            //可用ifelse語(yǔ)句理解。 
            //if(rchild是線索 && 不是最后一個(gè)節(jié)點(diǎn))  
            //else(rchild不是線索)-->走到右孩子 
            //也就是代碼T=T->rchild 
      T = T->rchild; 
      visit(T->data); 
    } 
    T = T->rchild; 
  } 
  return OK; 
} 
//求中序線索二叉樹(shù)中中序序列下的第一個(gè)節(jié)點(diǎn) 
ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){ 
  if( T != NULL ){ 
    while( T->lTag == Link ){ 
      T = T->lchild; 
    } 
    return T; 
  } 
  return ERROR; 
} 
//求中序線索二叉樹(shù)中節(jié)點(diǎn)P在中序序列下的下一個(gè)節(jié)點(diǎn) 
ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){ 
  if( CurrentP->rTag == Link ){  //有右孩子的時(shí)候，那么下一個(gè)就是以 
          //右孩子為root的樹(shù)的最左下角元素。 
          //即seekFirstNode的返回值。 
    return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild); 
  } 
  else{        //沒(méi)有右孩子，則rchild指向后綴 
    return CurrentP->rchild; 
  } 
} 
//使用上面兩個(gè)函數(shù)，SeekFirstNode_InOrderThrBiTree和GetNextNode來(lái)實(shí)現(xiàn)對(duì) 
//中序先做二叉樹(shù)的遍歷 
Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){ 
  for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) ) 
    visit(T->data); 
  return OK; 
} 
 
//test 
/* ShowThread函數(shù)的目的是想在將T中序線索化之后，使用函數(shù)InOrderTraverse 
 * 函數(shù)中序遍歷，輸出一下節(jié)點(diǎn)中的信息以檢驗(yàn)線索化，但是失敗。原因是：在 
 * 線索化之后，空指針域都被應(yīng)用，所有InOrderTraverse函數(shù)中的if( T )是滿 
 * 足不了的，故失敗。 
Status ShowThread(ThrBiTree C){ 
  printf("%d %d %d %d\n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag); 
  printf("%d %d\n",C->lTag,C->rTag); 
  return OK; 
 * */ 
 
//中序遍歷二叉樹(shù) 
Status InOrderTraverse(ThrBiTree T){ 
  if( T ){ 
    InOrderTraverse(T->lchild); 
    visit(T->data); 
    InOrderTraverse(T->rchild); 
  } 
  return OK; 
} 
int main(){ 
  ThrBiTree T,R,Head = NULL; 
  InitThreadBinaryTree(&T); 
 
  printf("Please Input Binary Tree By PreOrder\n  "); 
  ThreadBinaryTree_PreOrderInput(&T); 
 
  printf("  InOrder Traverse before Thread with Recursion\n"); 
  InOrderTraverse(T); 
  printf("\n"); 
 
  CreateInOrderThreadBinaryTree(T,&Head); 
  printf("  InOrder Traverse after Thread with no-Recursion\n"); 
  InOrderTeaverse_NoRecursion(T,Head); 
  printf("\n"); 
 
  printf("The root is %c \n", T->data);  //不能夠通過(guò)指針形參的值改變指針實(shí)參的值 
            //或者說(shuō)，對(duì)指針形參的改變不會(huì)作用到指針 
            //實(shí)參上。 
 
  ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL; 
  if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){ 
    firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T); 
    printf("the value of First Node of InOrderThreadBinaryTree is %c\n", firstOfInOrder->data); 
  } 
  secondOfInOrder = GetNextNode(firstOfInOrder); 
  printf("the value of Node after D is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after B is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after E is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after A is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after C is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after G is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after root is: %c \n", secondOfInOrder->data); 
 
  printf("  InOrder Traverse after Thread with no-Recursion Method_2\n"); 
  InOrderTraverse_NoRecursion_Method(T,Head); 
 
  return 0; 
}