全線索鏈表應用

1、實驗三 全線索鏈表應用問題定義及需求分析1.1課題目的和任務問題描述：對二叉樹的二叉鏈表結點增加兩個指針域，前驅指針prior和后繼指針next。通過該結點構造全線索二叉鏈表。實驗要求：設計一個全線索二叉鏈表的應用程序。1)創(chuàng)建全線索二叉樹。2)完成全線索二叉樹的主要基本操作。3)給出簡單應用實例1.2數據形式輸入數據形式：通過鍵盤輸入數據輸入值的范圍：輸入值的范圍均為float型，范圍為1.2e-38至3.4e+38。 輸出數據形式：輸出到顯示器。1.3程序功能將全線索作用于二叉排序樹中，通過對其進行中序遍歷線索化，實現通過線索搜索某個節(jié)點的前驅和后繼，并且利用線索，實現對整個樹中數據的中序

2、線索輸出，并且能夠在刪除樹中某個節(jié)點后，實現對該樹的重新線索化。1.4測試數據7 /樹中元素的個數5 2 7 1 3 6 8 /依次輸入的樹中元素值3 /需要輸出前驅和后繼的元素值7 /刪除的元素值8 /重新線索化后，需要輸出前驅和后繼的元素值1. 概要設計2.1抽象數據類型需要定義一個全線索二叉樹，該樹中含有數據，左右孩子，以及分別指向前驅和后繼的指針。通過前驅和后繼指針，將建立的二叉樹中序線索化，從而實現對數據更方便和快速的獲取。2.2主程序流程及各模塊之間的調用關系2. 詳細設計3.1存儲結構實現typedef struct Type/數據類型結構體聲明 float num;Type;t

3、ypedef struct BiTNode/二叉樹結構體聲明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next;BiTNode,*BiTree;3.2負責模塊的偽碼算法（1）int visit(Type e,BiTree T)/找到相同元素并返回它的前驅和后繼 if(T-data =e) return 1; else return 0;（2）const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,

4、Type& next)/中序遍歷二叉排序線索樹，并返回符合visit函數的元素的前驅和后繼 B=T-next; while(B非空且不等于T) if(visit(e,B)/找到等于e的B結點值 if(B前驅等于T) next=B-next-data;/B只有后繼 return 2; else if(B后繼等于T) prior=B-prior-data;/B只有前驅 return 3; else/B前驅和后繼都不等于T (prior,next)=(B-prior-data,B-next-data); return 1;/前驅和后繼都存在 B=B-next; return 0;（3）const i

5、nt SearchPN(BiTree Thrt,BiTree T)/利用全線索查找所需元素的前驅和后繼 cine;/輸入要查找的元素m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全線索中序查找某個元素的前驅和后繼 if(m=1)輸出前驅和后繼 else if(m=2)前驅不存在，輸出后繼 else if(m=3)后繼不存在，輸出前驅 else查找失敗，樹中無該元素 return 1;3. 調試分析4.1問題分析與解決方法對于給定輸入數，查找它的前驅和后繼，需要考慮該數是否存在前驅和后繼，如果沒有前驅和后繼，則需要輸出不存在標志。利用線索指

6、針很容易進行判斷，如果需要查找的元素的前驅是線索的頭（線索的頭是個空結點），那么該元素就不存在前驅，只存在后繼；而如果需要查找的元素的后繼是線索的頭，那么它就不存在后繼，只有前驅。因此通過if進行判斷，就可以成功輸出需要查詢的元素的前驅和后繼。4.2算法的時空分析在樹中查找某個元素并輸出該元素的前驅和后繼的整個時間復雜度最多為，空間復雜度為。4.3算法的改進設想 全線索的應用主要是為了方便樹的遍歷，能夠快速的訪問某個節(jié)點的前驅和后繼，因此可以考慮將線索應用于平衡二叉樹上，從而進一步提高平衡二叉樹獲取數據的速度。4.4經驗和體會 在整個程序的編寫過程中，出現一個問題，如果是首次線索化，便可以通過

7、線索成功輸出該樹，但當刪除某個節(jié)點后，再次進行線索化，然后利用線索輸出該樹就無法得到完整的樹。后來經過調試發(fā)現，由于第一次的線索化，該樹內的各個線索指針已被賦值，所以第二次線索化實際上是失敗的，因此需要先對樹進行去線索化操作（把線索指針指空）后，再對其進行線索化，這樣才能輸出正確的數據。 可見，程序各個模塊之間的影響不容小覷，必須對程序各個模塊的功能和影響有個整體的把握才不至于出現不合設想的錯誤。4. 使用說明按照操作提示，通過鍵盤輸入數據即可。輸入的節(jié)點數據可以為小數，但是數量數據必須為正整數。5. 測試結果（截屏）（1）前驅和后繼都存在的數：（2）只存在前驅的數：（3）只存在后繼的數：6.

8、 附錄7.1個人負責模塊的程序代碼int visit(Type e,BiTree T)/找到相同元素并返回它的前驅和后繼 if(T-data.num=e.num) return 1; else return 0;const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& next)/中序遍歷二叉排序線索樹，并返回符合visit函數的元素的前驅和后繼 BiTree B=T-next; while(B!=NULL&B!=T) if(visit(e,B) if(B-prio

9、r=T)/該點的前驅為T，說明它無前驅 next.num=B-next-data.num; return 2; else if(B-next=T)/該點的后繼為T，說明它無后繼 prior.num=B-prior-data.num; return 3; else/該點既有前驅也有后繼 prior.num=B-prior-data.num; next.num=B-next-data.num; return 1; B=B-next; return 0;const int SearchPN(BiTree Thrt,BiTree T)/利用全線索查找所需元素的前驅和后繼 Type e,prior,ne

10、xt; int m; coutPlease input a number to be searched and print its prior and next:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全線索中序查找某個元素的前驅和后繼 if(m=1)/前驅和后繼均有的情形 coutThe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2)/只有后繼的情形 coutThe prior of number

11、 e.num is not existed,; coutand its next is next.num.endl; else if(m=3)/只有前驅的情形 coutThe prior of number e.num is prior.num,; coutand its next is not existed.endl; else/未找到該數的情形 coutThe number searched is not existedendl; return 1;7.2程序全部代碼#include#includeusing namespace std;typedef struct Type/數據類型結

12、構體聲明 float num;Type;typedef struct BiTNode/二叉排序樹結構體聲明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next;BiTNode,*BiTree;int InitTree(BiTree& T,Type e)/創(chuàng)建二叉排序樹 T=(BiTree)malloc(sizeof(BiTNode); if(!T)return 0; T-data.num=e.num; T-lchild=T-rchild=NULL; T-prior=T-next=NULL; return 1;int

13、DestroyTree(BiTree& T)/遞歸銷毀二叉排序樹 if(T=NULL) return 0; DestroyTree(T-lchild); DestroyTree(T-rchild); free(T); return 1;int SearchTree(BiTree T,Type key,BiTree& p)/非遞歸算法，搜索二叉排序樹中元素 while(T) if(key.num=T-data.num)p=T;return 1; else if(key.numdata.num) p=T; T=T-lchild; else p=T; T=T-rchild; return 0;int

14、 InsertTree(BiTree& T, Type e)/二叉排序樹中元素插入 BiTree p; if(!SearchTree(T,e,p) BiTree s; s=(BiTree)malloc(sizeof(BiTNode); s-data.num=e.num; s-lchild=s-rchild=NULL; s-prior=s-next=NULL; if(!p)T=s; else if(e.numdata.num) p-lchild=s; else p-rchild=s; return 1; coutThe number has been existed!data.num) Dele

15、te(T); return 1; else if(e.numdata.num) DeleteTree(T-lchild,e); elseDeleteTree(T-rchild,e); return 1;int Delete(BiTree& p)/結點刪除算法 if(!p-lchild)/沒有左孩子 BiTree q; q=p; p=p-rchild; free(q); else if(!p-rchild)/沒有右孩子 BiTree q; q=p; p=p-lchild; free(q); else/兩個孩子都有 BiTree q,s; q=p; s=p-lchild; while(s-rchi

16、ld) q=s; s=s-rchild; p-data.num=s-data.num; if(q!=p) q-rchild=s-lchild; elseq-lchild=s-lchild; free(s); return 1;int visit(Type e,BiTree T)/找到相同元素并返回它的前驅和后繼 if(T-data.num=e.num) return 1; else return 0;const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& next

17、)/中序遍歷二叉排序線索樹，并返回符合visit函數的元素的前驅和后繼 BiTree B=T-next; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T) next.num=B-next-data.num; return 2; else if(B-next=T) prior.num=B-prior-data.num; return 3; else prior.num=B-prior-data.num; next.num=B-next-data.num; return 1; B=B-next; return 0;int InOrderThreadin

18、g(BiTree& Thrt,BiTree& T)/中序遍歷二叉排序樹T，并將其線索化,頭結點為Thrt void InThreading(BiTree& ,BiTree& ); if(!T)return 0; else Thrt=(BiTree)malloc(sizeof(BiTNode); Thrt-next=Thrt-prior=NULL; BiTree pre; pre=Thrt; InThreading(T,pre); pre-next=Thrt; Thrt-prior=pre; return 1;void InThreading(BiTree& T,BiTree& pre)/將結點

19、線索化 if(T) InThreading(T-lchild,pre); if(T-prior=NULL)T-prior=pre; if(pre-next=NULL)pre-next=T; pre=T; InThreading(T-rchild,pre); const int InOrderThrPrint(BiTree Thrt)/中序線索遍歷輸出樹 if(!Thrt) return 0; BiTree B=Thrt-next; while(B!=Thrt) coutdata.numnext; coutendl; return 1;const int SearchPN(BiTree Thrt

20、,BiTree T)/利用全線索查找所需元素的前驅和后繼 Type e,prior,next; int m; coutPlease input a number to be searched and print its prior and next:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全線索中序查找某個元素的前驅和后繼 if(m=1) coutThe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2) coutThe prior of number e.num is not existed,; coutand its next is next.num.endl; else if(m=3) coutThe prior of number e.num is prior.num,; coutand its next is not existed.endl; else coutThe number searched is not existednext=T-prior=NULL; RemoveThr(T-lchild); RemoveThr(T-rchild); r