1 /* 遍歷二叉樹就是以一定的規則將二叉樹中的節點排列成一個線性 2 * 序列，從而得到二叉樹節點的各種遍歷序列，其實質是：對一個 3 * 非線性的結構進行線性化。使得在這個訪問序列中每一個節點都 4 * 有一個直接前驅和直接後繼。 5 * 傳統的鏈式結構只能體現一種父子關係，￥不能直接得到節點在
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 }
