程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 線索二叉樹及若干操作,線索二叉樹操作

線索二叉樹及若干操作,線索二叉樹操作

編輯:關於C語言

線索二叉樹及若干操作,線索二叉樹操作


  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 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved