#include<stdio.h> #include<stdlib.h>  #define OK 1 #define ERROR 0  typedef char ElemType; typedef int Status;  /* 定義枚舉類型，其值只能是Link和Thread  * Link表示的該指針指示的是孩子  * Thread表示的是還指針指示的是前驅或者是后綴  * */ 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; } //先序建立二叉樹,lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag為Link 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; } //<<中序遍歷>>對二叉樹進行<<線索化>>，但是沒有提供Pre的初始值，只是給出了 //中間的過程，遞歸的思想和思考方式。 //1 線索化左子樹 //2 對雙親節點處理//遞歸中的base //3 線索化右子樹 Status InOrderThread(ThrBiTree T){   if( T != NULL ){     InOrderThread(T->lchild);    //線索化左子樹          //對雙親節點進行線索化處理     if( T->lchild == NULL ){ //如果左孩子為空，則將lchild作為索引             //Pre指向剛剛訪問的節點       T->lTag = Thread;       T->lchild = Pre;     }     if( Pre->rchild == NULL ){  //直到現在才知道Pre的后綴是T，所以             //要對Pre進行設置,如果Pre的rchild為空             //則將Pre的rchild設置為后綴，指向T       Pre->rTag = Thread;       Pre->rchild = T;     }      Pre = T;      //標記當前的節點稱為剛剛訪問過的節點             //Pre最后會指向樹的中序遍歷的最后的             //一個節點      InOrderThread(T->rchild);  //線索化右子樹   }   return OK; } //創建中序線索二叉樹,為上個函數提供Pre Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){   *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode));   if( !headOfTree )     return ERROR;   (*headOfTree)->lTag = Link;   //將要指向T   (*headOfTree)->rTag = Thread;    //將頭節點的rchild用于索引   (*headOfTree)->rchild = *headOfTree;   //指向自身   if( T == NULL ){     (*headOfTree)->lchild = *headOfTree; //若T為空樹，則頭節點的lchild               //指向自身   }   else{     (*headOfTree)->lchild = T;     Pre = *headOfTree;     //賦值了全局變量Pre     InOrderThread(T);        //中序線索化     //printf("/n%c/n",Pre->data);             //執行完InOrderThread之后Pre指向最后             //一個節點     Pre->rTag = Thread;        Pre->rchild = *headOfTree;     //(*headOfTree)->rchild = Pre;   }   return OK; } //對中序線索化后的線索二叉樹使用<<非遞歸>>的代碼進行中序遍歷 //并且原來的遞歸形式的代碼在這里是不再可以進行遍歷。 //  如果二叉樹沒有被線索化，也可以使用<<非遞歸>>的代碼進行遍 //  歷的，但是那就需要借助于<<棧>>,但是在線索化之后，對線索 //  化的二叉樹進行<<非遞歸>>的遍歷就不再需要棧的輔助。 Status visit(ElemType c){   printf("%c ", c);   return OK; } Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ //headOfTree是T的頭節點的指針，headOfTree->lchild = T;   while( T != headOfTree ){     while( T->lTag == Link ){  //找到樹(子樹)的最左節點             //用while接替if//             //用if理解while//       T = T->lchild;     }             visit(T->data);      while( T->rTag == Thread && T->rchild != headOfTree){             //這個while和下面的T=T->rchild             //可用ifelse語句理解。             //if(rchild是線索 && 不是最后一個節點)              //else(rchild不是線索)-->走到右孩子             //也就是代碼T=T->rchild       T = T->rchild;       visit(T->data);     }     T = T->rchild;   }   return OK; } //求中序線索二叉樹中中序序列下的第一個節點 ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){   if( T != NULL ){     while( T->lTag == Link ){       T = T->lchild;     }     return T;   }   return ERROR; } //求中序線索二叉樹中節點P在中序序列下的下一個節點 ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){   if( CurrentP->rTag == Link ){  //有右孩子的時候，那么下一個就是以           //右孩子為root的樹的最左下角元素。           //即seekFirstNode的返回值。     return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild);   }   else{        //沒有右孩子，則rchild指向后綴     return CurrentP->rchild;   } } //使用上面兩個函數，SeekFirstNode_InOrderThrBiTree和GetNextNode來實現對 //中序先做二叉樹的遍歷 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函數的目的是想在將T中序線索化之后，使用函數InOrderTraverse  * 函數中序遍歷，輸出一下節點中的信息以檢驗線索化，但是失敗。原因是：在  * 線索化之后，空指針域都被應用，所有InOrderTraverse函數中的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;  * */  //中序遍歷二叉樹 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);  //不能夠通過指針形參的值改變指針實參的值             //或者說，對指針形參的改變不會作用到指針             //實參上。    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; }