實驗三全線索鏈表應(yīng)用

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

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

3、struct BiTNode/二叉樹構(gòu)造體聲明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* ne*t;BiTNode,*BiTree;3.2負(fù)責(zé)模塊的偽碼算法1int visit(Type e,BiTree T)/找到一樣元素并返回它的前驅(qū)和后繼 if(T-data =e) return 1; else return 0;2const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& ne*t)

4、/中序遍歷二叉排序線索樹，并返回符合visit函數(shù)的元素的前驅(qū)和后繼 B=T-ne*t; while(B非空且不等于T) if(visit(e,B)/找到等于e的B結(jié)點值 if(B前驅(qū)等于T) ne*t=B-ne*t-data;/B只有后繼 return 2; else if(B后繼等于T) prior=B-prior-data;/B只有前驅(qū) return 3; else/B前驅(qū)和后繼都不等于T (prior,ne*t)=(B-prior-data,B-ne*t-data); return 1;/前驅(qū)和后繼都存在 B=B-ne*t; return 0;3const int SearchPN(B

5、iTree Thrt,BiTree T)/利用全線索查找所需元素的前驅(qū)和后繼 cine;/輸入要查找的元素m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,ne*t);/全線索中序查找*個元素的前驅(qū)和后繼 if(m=1)輸出前驅(qū)和后繼 else if(m=2)前驅(qū)不存在，輸出后繼 else if(m=3)后繼不存在，輸出前驅(qū) else查找失敗，樹中無該元素 return 1;調(diào)試分析4.1問題分析與解決方法對于給定輸入數(shù)，查找它的前驅(qū)和后繼，需要考慮該數(shù)是否存在前驅(qū)和后繼，如果沒有前驅(qū)和后繼，則需要輸出不存在標(biāo)志。利用線索指針很容易進(jìn)展判斷，如果需要查找的

6、元素的前驅(qū)是線索的頭線索的頭是個空結(jié)點，則該元素就不存在前驅(qū)，只存在后繼；而如果需要查找的元素的后繼是線索的頭，則它就不存在后繼，只有前驅(qū)。因此通過if進(jìn)展判斷，就可以成功輸出需要查詢的元素的前驅(qū)和后繼。4.2算法的時空分析在樹中查找*個元素并輸出該元素的前驅(qū)和后繼的整個時間復(fù)雜度最多為，空間復(fù)雜度為。4.3算法的改良設(shè)想全線索的應(yīng)用主要是為了方便樹的遍歷，能夠快速的*個節(jié)點的前驅(qū)和后繼，因此可以考慮將線索應(yīng)用于平衡二叉樹上，從而進(jìn)一步提高平衡二叉樹獲取數(shù)據(jù)的速度。4.4經(jīng)歷和體會在整個程序的編寫過程中，出現(xiàn)一個問題，如果是首次線索化，便可以通過線索成功輸出該樹，但當(dāng)刪除*個節(jié)點后，再次進(jìn)展線

7、索化，然后利用線索輸出該樹就無法得到完整的樹。后來經(jīng)過調(diào)試發(fā)現(xiàn)，由于第一次的線索化，該樹的各個線索指針已被賦值，所以第二次線索化實際上是失敗的，因此需要先對樹進(jìn)展去線索化操作把線索指針指空后，再對其進(jìn)展線索化，這樣才能輸出正確的數(shù)據(jù)?？梢?，程序各個模塊之間的影響不容小覷，必須對程序各個模塊的功能和影響有個整體的把握才不至于出現(xiàn)不合設(shè)想的錯誤。使用說明按照操作提示，通過鍵盤輸入數(shù)據(jù)即可。輸入的節(jié)點數(shù)據(jù)可以為小數(shù)，但是數(shù)量數(shù)據(jù)必須為正整數(shù)。測試結(jié)果截屏1前驅(qū)和后繼都存在的數(shù)：2只存在前驅(qū)的數(shù)：3只存在后繼的數(shù)：附錄7.1個人負(fù)責(zé)模塊的程序代碼int visit(Type e,BiTree T)/找

8、到一樣元素并返回它的前驅(qū)和后繼 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& ne*t)/中序遍歷二叉排序線索樹，并返回符合visit函數(shù)的元素的前驅(qū)和后繼 BiTree B=T-ne*t; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T)/該點的前驅(qū)為T，說明它無前驅(qū) ne*t.num=B-ne*t-data.num;

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

10、arched and print its prior and ne*t:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,ne*t);/全線索中序查找*個元素的前驅(qū)和后繼 if(m=1)/前驅(qū)和后繼均有的情形 coutThe prior of number e.num is prior.num,; coutand its ne*t is ne*t.num.endl; else if(m=2)/只有后繼的情形 coutThe prior of number e.num is not e*isted,; coutand its ne*t is n

11、e*t.num.endl; else if(m=3)/只有前驅(qū)的情形 coutThe prior of number e.num is prior.num,; coutand its ne*t is not e*isted.endl; else/未找到該數(shù)的情形 coutThe number searched is not e*istedendl; return 1;7.2程序全部代碼#include#includeusing namespace std;typedef struct Type/數(shù)據(jù)類型構(gòu)造體聲明 float num;Type;typedef struct BiTNode/二叉

12、排序樹構(gòu)造體聲明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* ne*t;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-ne*t=NULL; return 1;int DestroyTree(BiTree& T)/遞歸銷毀二叉排序樹 if(T=NULL) r

13、eturn 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 InsertTree(BiTree& T, Type e)/二叉排序樹中元素插入 BiT

14、ree 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-ne*t=NULL; if(!p)T=s; else if(e.numdata.num) p-lchild=s; else p-rchild=s; return 1; coutThe number has been e*isted!data.num) Delete(T); return 1; else if(e.numdata.num) Delet

15、eTree(T-lchild,e); elseDeleteTree(T-rchild,e); return 1;int Delete(BiTree& p)/結(jié)點刪除算法 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-rchild) q=s; s=s-rchild; p-data.num=s-data.num; i

16、f(q!=p) q-rchild=s-lchild; elseq-lchild=s-lchild; free(s); return 1;int visit(Type e,BiTree T)/找到一樣元素并返回它的前驅(qū)和后繼 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& ne*t)/中序遍歷二叉排序線索樹，并返回符合visit函數(shù)的元素的前驅(qū)和后繼 BiTree B=

17、T-ne*t; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T) ne*t.num=B-ne*t-data.num; return 2; else if(B-ne*t=T) prior.num=B-prior-data.num; return 3; else prior.num=B-prior-data.num; ne*t.num=B-ne*t-data.num; return 1; B=B-ne*t; return 0;int InOrderThreading(BiTree& Thrt,BiTree& T)/中序遍歷二叉排序樹T，并將其線索化,頭

18、結(jié)點為Thrt void InThreading(BiTree& ,BiTree& ); if(!T)return 0; else Thrt=(BiTree)malloc(sizeof(BiTNode); Thrt-ne*t=Thrt-prior=NULL; BiTree pre; pre=Thrt; InThreading(T,pre); pre-ne*t=Thrt; Thrt-prior=pre; return 1;void InThreading(BiTree& T,BiTree& pre)/將結(jié)點線索化 if(T) InThreading(T-lchild,pre); if(T-pri

19、or=NULL)T-prior=pre; if(pre-ne*t=NULL)pre-ne*t=T; pre=T; InThreading(T-rchild,pre); const int InOrderThrPrint(BiTree Thrt)/中序線索遍歷輸出樹 if(!Thrt) return 0; BiTree B=Thrt-ne*t; while(B!=Thrt) coutdata.numne*t; coutendl; return 1;const int SearchPN(BiTree Thrt,BiTree T)/利用全線索查找所需元素的前驅(qū)和后繼 Type e,prior,ne*

20、t; int m; coutPlease input a number to be searched and print its prior and ne*t:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,ne*t);/全線索中序查找*個元素的前驅(qū)和后繼 if(m=1) coutThe prior of number e.num is prior.num,; coutand its ne*t is ne*t.num.endl; else if(m=2) coutThe prior of number e.num is not e*isted,; coutand its ne*t is ne*t.num.endl; else if(m=3) coutThe prior of number e.num is prior.num,; coutand its ne*t is not e*isted.endl; else coutThe number searched is not e*istedne*t=T-prior=NULL; RemoveThr(T-lchild); RemoveThr(T-rchild); ret