數(shù)據(jù)結(jié)構(gòu)課程設(shè)計帶父親節(jié)點的平衡二叉樹的建立

1、沈陽航空沈陽航空航天大學航天大學 課課 程程 設(shè)設(shè) 計計 報報 告告 課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課程設(shè)計題目：帶父親節(jié)點的平衡二叉樹的帶父親節(jié)點的平衡二叉樹的 建立建立 院（系）：計算機學院 專 業(yè)：網(wǎng)絡(luò)工程 班 級： 學 號： 姓 名：夏媛 指導教師：鄭志勇 沈陽航空航天大學課程設(shè)計報告 i 目目 錄錄 1 1 課程設(shè)計介紹課程設(shè)計介紹.1 1.1 課程設(shè)計內(nèi)容.1 1.2 課程設(shè)計要求.1 2 2 課程設(shè)計原理課程設(shè)計原理.2 2.1 課設(shè)題目粗略分析.2 2.2 原理圖介紹.2 2.2.1 功能模塊圖.2 2.2.2 流程圖分析.3 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.8

2、 3.1 存儲結(jié)構(gòu).8 3.2 算法描述.8 4 4 調(diào)試與分析調(diào)試與分析.10 4.1 調(diào)試過程.10 4.1 程序執(zhí)行過程.11 參考文獻參考文獻.12 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.13 沈陽航空航天大學課程設(shè)計報告 1 1 1 課程設(shè)計介紹課程設(shè)計介紹 1.11.1 課程設(shè)計內(nèi)容課程設(shè)計內(nèi)容 設(shè)計程序，建立帶有父親結(jié)點的平衡二叉樹，系統(tǒng)主要功能是：從鍵盤 上輸入一整數(shù)序列，建立一顆平衡二叉樹。 1.21.2 課程設(shè)計要求課程設(shè)計要求 (1) 要能夠形象方便的觀察樹的結(jié)構(gòu)； (2) 要能夠形象的演示樹的平衡過程； (3) 課程設(shè)計報告必須符合課程設(shè)計報告規(guī)范； (4

3、) 提交合格的報告后，經(jīng)指導老師測試程序后，課設(shè)完成。 沈陽航空工業(yè)學院課程設(shè)計報告 2 2 2 課程設(shè)計原理課程設(shè)計原理 2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析 根據(jù)課設(shè)題目要求，我將整體程序分為四大模塊，這四個模塊相互獨立，沒 有任何嵌套調(diào)用的情況，以下是四個模塊的大體分析： (1)判斷模塊：在插入一個關(guān)鍵字時，首先先對該關(guān)鍵字進行判斷，如果該關(guān) 鍵字已經(jīng)存在則不插入，否則插入該關(guān)鍵字，調(diào)用函數(shù) insertavl（） 。 (2)左子樹插入模塊：如果判斷完的新關(guān)鍵字插在左子樹上，則對該以指針 p 所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時，指針 p 指向新的根 結(jié)點，調(diào)用函

4、數(shù) leftprocess（） 。 (3)右子樹插入模塊：如果判斷完的新關(guān)鍵字插在右子樹上，則對該以指針 p 所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時，指針 p 指向新的根 結(jié)點，調(diào)用函數(shù) rightprocess（） 。 (4)輸出模塊：對建立完成的平衡二叉樹輸出，輸出格式為二叉樹的括號表 示，且每一步插入操作對應(yīng)一次輸出，最后做一次總體輸出，調(diào)用函數(shù)， dispbstree（） 。 2.22.2 原理圖介紹原理圖介紹 主函數(shù)主要實現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對輸入的關(guān)鍵字進行判斷， 調(diào)用函數(shù) insertavl（） ，若該關(guān)鍵字在已建樹中已經(jīng)存在，則返回主函數(shù)接著對 下一個關(guān)鍵

5、字進行判斷。若該關(guān)鍵字在已建樹中不存在，則插入該數(shù)，若插入左 子樹中則調(diào)用函數(shù) leftprocess（）進行插入操作，若插入右子樹中則調(diào)用函數(shù) dispbstree（）進行插入操作。當所有的關(guān)鍵字都插入完事之后，進行輸出，調(diào) 用函數(shù)，dispbstree（） 。 .1 功能模塊圖功能模塊圖 1.判斷模塊 沈陽航空工業(yè)學院課程設(shè)計報告 3 若在平衡二叉排序樹 b 中不存在和 e 有相同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù) 元素為 e 的新結(jié)點，并返回 1，否則返回 0。若因插入而使二叉排序樹失去平衡， 則作平衡旋轉(zhuǎn)處理，布爾變量 taller 反映 b 長高與否。 2.左子樹插入模塊

6、對以指針 p 所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時，指針 p 指向新的根結(jié)點，插入分三種情況：原本左右子樹等高，現(xiàn)因左子樹增高而使 樹增；原本右子樹比左子樹高，現(xiàn)左右子樹等高；原本左子樹比右子樹高，須作 左子樹的平衡處理。若新關(guān)鍵字插入在*p 的左孩子的左子樹上，要做 ll 調(diào)整， 若新關(guān)鍵字插入在*p 的左孩子的右子樹上，要做 lr 調(diào)整。 3.右子樹子樹插入模塊 對以指針 p 所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時，指針 p 指向新的根結(jié)點，插入分三種情況：原本左右子樹等高，現(xiàn)因右子樹增高而使 樹增；原本左子樹比右子樹高，現(xiàn)左右子樹等高；原本右子樹比左子樹高，須作

7、 右子樹的平衡處理。若新關(guān)鍵字插入在*p 的右孩子的右子樹上，要做 rr 調(diào)整， 若新關(guān)鍵字插入在*p 的右孩子的左子樹上，要做 rl 調(diào)整。 .2 流程圖分析流程圖分析 1主函數(shù)流程圖 主函數(shù)主要實現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對輸入的關(guān)鍵字進行判斷， 若該關(guān)鍵字在已建樹中已經(jīng)存在，則返回主函數(shù)接著對下一個關(guān)鍵字進行判斷。 若該關(guān)鍵字在已建樹中不存在，則插入該數(shù)，當所有的關(guān)鍵字都插入完事之后， 進行輸出。流程圖如圖 2.1 所示。 沈陽航空工業(yè)學院課程設(shè)計報告 4 開始 bstnode *b=null; int i,j; keytype a=6,1,2,3,4,5,0,7,8

8、,9,n=10; y key存在 y insertavl(b,ai,j); dispbstree(b); n for(i=0;ikey y taller=0; return 0; ekey y leftprocess(b,taller) n 結(jié)束 rightprocess(b,taller) 圖 2.2 判斷模塊流程圖 3左子樹插入模塊流程圖 斷完的新關(guān)鍵字插在左子樹上，則對該以指針 p 所指結(jié)點為根的二叉樹作左 平衡旋轉(zhuǎn)處理，本算法結(jié)束時，指針 p 指向新的根結(jié)針。流程圖如圖 2.3 所示。 沈陽航空工業(yè)學院課程設(shè)計報告 6 開始 bstnode *p1,*p2 bstnode * y n

9、y n y p-bf=0 p-bf=1; taller=1 p-bf=-1 p-bf=0; taller=0 p1-bf=1 n p1=p-lchild; p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; p-bf=p1-bf=0 p2-bf=0 y n p2-bf=1 n y p1-bf=0; p-bf=-1 n p1-bf=1; p-bf=0; p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; p1-bf=-1 y tal

10、ler=0p=p2; p-bf=0; ; taller=0 結(jié)束 圖 2.3 左子樹插入模塊流程圖 4右子樹插入模塊流程圖 斷完的新關(guān)鍵字插在右子樹上，則對該以指針 p 所指結(jié)點為根的二叉樹作右 平衡旋轉(zhuǎn)處理，本算法結(jié)束時，指針 p 指向新的根結(jié)針。流程圖如圖 2.4 所示。 沈陽航空工業(yè)學院課程設(shè)計報告 7 開始 bstnode *p1,*p2 bstnode * y n y n y p-bf=-1 p-bf=1; taller=1 p-bf=1 p-bf=0; taller=0 1-bf=-1 n p1=p-rchild p-rchild=p1-lchild; p1-lchild=p; p

11、-bf=p1-bf=0; p=p1; p-bf=p1-bf=0; p2-bf=0 y n p2-bf=-1 n y p1-bf=0; p-bf=1 n p1-bf=-1; p-bf=0 p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; p1-bf=1 y p=p2; p-bf=0; taller=0 結(jié)束 圖 2.4 右子樹插入模塊流程圖 沈陽航空工業(yè)學院課程設(shè)計報告 8 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析 3.13.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 定義一個關(guān)鍵字類型的字符數(shù)組，其空間足夠大，用來

12、存放關(guān)鍵字。 3.23.2 算法描述算法描述 1判斷關(guān)鍵字算法如下： /若在平衡二叉排序樹 b 中不存在和 e 有相同關(guān)鍵字的結(jié)點，則插入一個 數(shù)據(jù)元素為 e 的新結(jié)點， if(b=null) /原樹為空，插入新結(jié)點，樹長高，置 taller 為 1 b=(bstnode*)malloc(sizeof(bstnode); b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1; else if(e=b-key) /樹中已存在和 e 有相同關(guān)鍵字的結(jié)點則不插入 taller=0; return 0; if(ekey) /繼續(xù)在*b 的左子樹中進行搜索

13、if(insertavl(b-lchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的左子樹中且左子樹長高 leftprocess(b,taller); else /繼續(xù)在*b 的右子樹中進行搜索 if(insertavl(b-rchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的右子樹中且右子樹長高 沈陽航空工業(yè)學院課程設(shè)計報告 9 rightprocess(b,taller); return 1; 2.左平衡處理算法如下： /對以指針 p 所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處

14、理，本算法結(jié)束時， /指針 p 指向新的根結(jié)點 bstnode *p1,*p2; if(p-bf=0) /原本左右子樹等高，現(xiàn)因左子樹增高而使樹增高 p-bf=1; taller=1; else if(p-bf=-1) /原本右子樹比左子樹高，現(xiàn)左右子樹等高 p-bf=0; taller=0; else /原本左子樹比右子樹高，須作左子樹的平衡處理 p1=p-lchild; /p 指向*p 的左子樹根節(jié)點 if(p1-bf=1) /新結(jié)點插入在*p 的左孩子的左子樹上，要做 ll 調(diào)整 p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; e

15、lse if(p1-bf=-1) /新結(jié)點插入在*p 的左孩子的右子樹上，要做 lr 調(diào)整 p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) /新結(jié)點插入在*p2 處作為葉子結(jié)點的情況 p-bf=p1-bf=0; else if(p2-bf=1) /新結(jié)點插在*p2 的左子樹上的情況 沈陽航空工業(yè)學院課程設(shè)計報告 10 p1-bf=0; p-bf=-1; else /新結(jié)點插在*p2 的右子樹上的情況 p1-bf=1; p-bf=0; p=p2; p-bf=

16、0; /仍將 p 指向新的根結(jié)點，并置其 bf 值為 0 taller=0; 4 4 調(diào)試與分析調(diào)試與分析 4.14.1 調(diào)試過程調(diào)試過程 在調(diào)試程序是主要遇到一下幾類問題： 1. 本程序用到指針的地方特別多，由于指針那部分知識我掌握的不是很好， 故而在這方面有困難。后來我通過在圖書館查資料、看書解決了這方面問題。 2. 對二叉樹的左右子樹進行插入調(diào)整的操作時，由于考慮問題不夠全面而 導致輸出結(jié)果出現(xiàn)錯誤，在查質(zhì)料重新學習二叉樹后，解決了此問題。 沈陽航空工業(yè)學院課程設(shè)計報告 11 4.1 程序執(zhí)行過程程序執(zhí)行過程 圖 4.1 第一組輸入執(zhí)行結(jié)果 圖 4.2 第二組輸入執(zhí)行結(jié)果 沈陽航空工業(yè)學

17、院課程設(shè)計報告 12 參考文獻參考文獻 1 嚴蔚敏.吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學出版社，2007. 2 張長海.陳娟. .c 程序設(shè)計m.北京：高等教育出版社，2004. 3 譚浩強. .c 程序設(shè)計m.北京：清華大學出版社，2005. 4 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實用教程.m.北京：清華大學出版社，2006. 5 張秉權(quán). .數(shù)據(jù)結(jié)構(gòu)（c 語言描述）.m.北京：中國輕工業(yè)出版社，2004. 沈陽航空工業(yè)學院課程設(shè)計報告 13 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單） 程序代碼程序代碼 #include #include typedef int keytype typedef st

18、ruct node keytype key; int bf; struct node *lchild,*rchild; bstnode; void leftprocess(bstnode * if(p-bf=0) p-bf=1; taller=1; else if(p-bf=-1) p-bf=0; taller=0; else p1=p-lchild if(p1-bf=1) p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=-1) p2=p1-rchild; p1-rchild=p2-lchild; p2-lc

19、hild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=1) 沈陽航空工業(yè)學院課程設(shè)計報告 14 p1-bf=0; p-bf=-1; else p1-bf=1; p-bf=0; p=p2; p-bf=0; taller=0; void rightprocess(bstnode * if(p-bf=0) p-bf=-1; taller=1; else if(p-bf=1) p-bf=0; taller=0; else p1=p-rchild; if(p1-bf=-1) p-rchild=p

20、1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=1) p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=-1) 沈陽航空工業(yè)學院課程設(shè)計報告 15 p1-bf=0; p-bf=1; else p1-bf=-1; p-bf=0; p=p2; p-bf=0; taller=0; int insertavl(bstnode* b-key=e;

21、b-lchild=b-rchild=null; b-bf=0; taller=1; else if(e=b-key) taller=0; return 0; if(ekey) if(insertavl(b-lchild,e,taller)=0) return 0; if(taller=1) leftprocess(b,taller); else if(insertavl(b-rchild,e,taller)=0) return 0; if(taller=1) rightprocess(b,taller); 沈陽航空工業(yè)學院課程設(shè)計報告 16 return 1; void dispbstree(bstnode *b) /*以括號表示法輸出 avl*/ if(b!=null) printf(%d,b-key); if(b-lchild!=null|b-rchild!=null) printf(); dispbstree(b-lchild); if(b-rchild!=null)printf(,); dispbstree(b-rchild); printf(); int main() bstnode *b=null; int i,j; keytype a=6,1,2,3,4,5,0,7,8,9,n=10; printf(創(chuàng)建一棵 avl 樹:n);