1 /* 遍歷二叉樹就是以一定的規則將二叉樹中的節點排列成一個線性 2 * 序列,從而得到二叉樹節點的各種遍歷序列,其實質是:對一個 3 * 非線性的結構進行線性化。使得在這個訪問序列中每一個節點都 4 * 有一個直接前驅和直接後繼。 5 * 傳統的鏈式結構只能體現一種父子關系,¥不能直接得到節點在 6 * 遍歷中的前驅和後繼¥,而我們知道二叉鏈表表示的二叉樹中有 7 * 大量的空指針,當使用這些空的指針存放指向節點的前驅和後繼 8 * 的指針時,則可以更加方便的運用二叉樹的某些操作。 9 * 引入線索二叉樹的目的是: 為了加快查找節點的前驅和後繼。 10 * 11 * 對二叉樹的線索化就是對二叉樹進行一次遍歷,在遍歷的過程中 12 * 檢測節點的左右指針是否為空,如果是空,則將他們改為指向前 13 * 驅和後繼節點的線索。 14 * */ 15 #include<stdio.h> 16 #include<stdlib.h> 17 18 #define OK 1 19 #define ERROR 0 20 21 typedef char ElemType; 22 typedef int Status; 23 24 /* 定義枚舉類型,其值只能是Link和Thread 25 * Link表示的該指針指示的是孩子 26 * Thread表示的是還指針指示的是前驅或者是後綴 27 * */ 28 typedef enum { 29 Link,Thread 30 }PointerTag; 31 32 typedef struct ThrBiTrNode{ 33 ElemType data; 34 struct ThrBiTrNode *lchild, *rchild; 35 PointerTag rTag, lTag; 36 }ThrBiTrNode, *ThrBiTree; 37 38 ThrBiTree Pre; 39 40 Status InitThreadBinaryTree(ThrBiTree* T){ 41 *T = NULL; 42 return OK; 43 } 44 //先序建立二叉樹,lchild和rchild都是指示做孩子和右孩子,所以lTag和rTag為Link 45 Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){ 46 ElemType c; 47 scanf("%c", &c); 48 if( ' ' == c ){ 49 *T = NULL; 50 } 51 else{ 52 *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode)); 53 if( !*T ){ 54 return ERROR; 55 } 56 (*T)->data = c; 57 (*T)->lTag = Link; 58 (*T)->rTag = Link; 59 ThreadBinaryTree_PreOrderInput(&(*T)->lchild); 60 ThreadBinaryTree_PreOrderInput(&(*T)->rchild); 61 } 62 return OK; 63 } 64 //<<中序遍歷>>對二叉樹進行<<線索化>>,但是沒有提供Pre的初始值,只是給出了 65 //中間的過程,遞歸的思想和思考方式。 66 //1 線索化左子樹 67 //2 對雙親節點處理//遞歸中的base 68 //3 線索化右子樹 69 Status InOrderThread(ThrBiTree T){ 70 if( T != NULL ){ 71 InOrderThread(T->lchild); //線索化左子樹 72 73 //對雙親節點進行線索化處理 74 if( T->lchild == NULL ){ //如果左孩子為空,則將lchild作為索引 75 //Pre指向剛剛訪問的節點 76 T->lTag = Thread; 77 T->lchild = Pre; 78 } 79 if( Pre->rchild == NULL ){ //直到現在才知道Pre的後綴是T,所以 80 //要對Pre進行設置,如果Pre的rchild為空 81 //則將Pre的rchild設置為後綴,指向T 82 Pre->rTag = Thread; 83 Pre->rchild = T; 84 } 85 86 Pre = T; //標記當前的節點稱為剛剛訪問過的節點 87 //Pre最後會指向樹的中序遍歷的最後的 88 //一個節點 89 90 InOrderThread(T->rchild); //線索化右子樹 91 } 92 return OK; 93 } 94 //創建中序線索二叉樹,為上個函數提供Pre 95 Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){ 96 *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode)); 97 if( !headOfTree ) 98 return ERROR; 99 (*headOfTree)->lTag = Link; //將要指向T 100 (*headOfTree)->rTag = Thread; //將頭節點的rchild用於索引 101 (*headOfTree)->rchild = *headOfTree; //指向自身 102 if( T == NULL ){ 103 (*headOfTree)->lchild = *headOfTree; //若T為空樹,則頭節點的lchild 104 //指向自身 105 } 106 else{ 107 (*headOfTree)->lchild = T; 108 Pre = *headOfTree; //賦值了全局變量Pre 109 InOrderThread(T); //中序線索化 110 //printf("\n%c\n",Pre->data); 111 //執行完InOrderThread之後Pre指向最後 112 //一個節點 113 Pre->rTag = Thread; 114 Pre->rchild = *headOfTree; 115 //(*headOfTree)->rchild = Pre; 116 } 117 return OK; 118 } 119 //對中序線索化後的線索二叉樹使用<<非遞歸>>的代碼進行中序遍歷 120 //並且原來的遞歸形式的代碼在這裡是不再可以進行遍歷。 121 // 如果二叉樹沒有被線索化,也是使用<<非遞歸>>的代碼進行遍 122 // 歷的,但是那就需要借助於<<棧>>,但是在線索化之後,對線索 123 // 化的二叉樹進行<<非遞歸>>的遍歷就不再需要棧的輔助。 124 Status visit(ElemType c){ 125 printf("%c ", c); 126 return OK; 127 } 128 Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ 129 //headOfTree是T的頭節點的指針,headOfTree->lchild = T; 130 while( T != headOfTree ){ 131 while( T->lTag == Link ){ //找到樹(子樹)的最左節點 132 //用while接替if// 133 //用if理解while// 134 T = T->lchild; 135 } 136 visit(T->data); 137 138 while( T->rTag == Thread && T->rchild != headOfTree){ 139 //這個while和下面的T=T->rchild 140 //可用ifelse語句理解。 141 //if(rchild是線索 && 不是最後一個節點) 142 //else(rchild不是線索)-->走到右孩子 143 //也就是代碼T=T->rchild 144 T = T->rchild; 145 visit(T->data); 146 } 147 T = T->rchild; 148 } 149 return OK; 150 } 151 //求中序線索二叉樹中中序序列下的第一個節點 152 ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){ 153 if( T != NULL ){ 154 while( T->lTag == Link ){ 155 T = T->lchild; 156 } 157 return T; 158 } 159 return ERROR; 160 } 161 //求中序線索二叉樹中節點P在中序序列下的下一個節點 162 ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){ 163 if( CurrentP->rTag == Link ){ //有右孩子的時候,那麼下一個就是以 164 //右孩子為root的樹的最左下角元素。 165 //即seekFirstNode的返回值。 166 return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild); 167 } 168 else{ //沒有右孩子,則rchild指向後綴 169 return CurrentP->rchild; 170 } 171 } 172 //使用上面兩個函數,SeekFirstNode_InOrderThrBiTree和GetNextNode來實現對 173 //中序先做二叉樹的遍歷 174 Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){ 175 for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) ) 176 visit(T->data); 177 return OK; 178 } 179 180 //test 181 /* ShowThread函數的目的是想在將T中序線索化之後,使用函數InOrderTraverse 182 * 函數中序遍歷,輸出一下節點中的信息以檢驗線索化,但是失敗。原因是:在 183 * 線索化之後,空指針域都被應用,所有InOrderTraverse函數中的if( T )是滿 184 * 足不了的,故失敗。 185 Status ShowThread(ThrBiTree C){ 186 printf("%d %d %d %d\n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag); 187 printf("%d %d\n",C->lTag,C->rTag); 188 return OK; 189 * */ 190 191 //中序遍歷二叉樹 192 Status InOrderTraverse(ThrBiTree T){ 193 if( T ){ 194 InOrderTraverse(T->lchild); 195 visit(T->data); 196 InOrderTraverse(T->rchild); 197 } 198 return OK; 199 } 200 int main(){ 201 ThrBiTree T,R,Head = NULL; 202 InitThreadBinaryTree(&T); 203 204 printf("Please Input Binary Tree By PreOrder\n "); 205 ThreadBinaryTree_PreOrderInput(&T); 206 207 printf(" InOrder Traverse before Thread with Recursion\n"); 208 InOrderTraverse(T); 209 printf("\n"); 210 211 CreateInOrderThreadBinaryTree(T,&Head); 212 printf(" InOrder Traverse after Thread with no-Recursion\n"); 213 InOrderTeaverse_NoRecursion(T,Head); 214 printf("\n"); 215 216 printf("The root is %c \n", T->data); //不能夠通過指針形參的值改變指針實參的值 217 //或者說,對指針形參的改變不會作用到指針 218 //實參上。 219 220 ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL; 221 if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){ 222 firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T); 223 printf("the value of First Node of InOrderThreadBinaryTree is %c\n", firstOfInOrder->data); 224 } 225 secondOfInOrder = GetNextNode(firstOfInOrder); 226 printf("the value of Node after D is: %c \n", secondOfInOrder->data); 227 secondOfInOrder = GetNextNode(secondOfInOrder); 228 printf("the value of Node after B is: %c \n", secondOfInOrder->data); 229 secondOfInOrder = GetNextNode(secondOfInOrder); 230 printf("the value of Node after E is: %c \n", secondOfInOrder->data); 231 secondOfInOrder = GetNextNode(secondOfInOrder); 232 printf("the value of Node after A is: %c \n", secondOfInOrder->data); 233 secondOfInOrder = GetNextNode(secondOfInOrder); 234 printf("the value of Node after C is: %c \n", secondOfInOrder->data); 235 secondOfInOrder = GetNextNode(secondOfInOrder); 236 printf("the value of Node after G is: %c \n", secondOfInOrder->data); 237 secondOfInOrder = GetNextNode(secondOfInOrder); 238 printf("the value of Node after root is: %c \n", secondOfInOrder->data); 239 240 printf(" InOrder Traverse after Thread with no-Recursion Method_2\n"); 241 InOrderTraverse_NoRecursion_Method(T,Head); 242 243 return 0; 244 }