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

1、xxx 航空航空航天大學(xué)航天大學(xué)課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：帶父親節(jié)點(diǎn)的平衡二叉樹(shù)的帶父親節(jié)點(diǎn)的平衡二叉樹(shù)的建立建立院（系）：計(jì)算機(jī)學(xué)院專 業(yè)：網(wǎng)絡(luò)工程班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師：沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 i 目目 錄錄1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹.11.1 課程設(shè)計(jì)內(nèi)容.11.2 課程設(shè)計(jì)要求.12 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理.22.1 課設(shè)題目粗略分析.22.2 原理圖介紹.22.2.1 功能模塊圖.22.2.2 流程圖分析.33 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.83.1 存儲(chǔ)結(jié)構(gòu).83.2 算法描述.84 4 調(diào)

2、試與分析調(diào)試與分析.104.1 調(diào)試過(guò)程.101.2程序執(zhí)行過(guò)程.11參考文獻(xiàn)參考文獻(xiàn).12附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.13沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 1 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容設(shè)計(jì)程序，建立帶有父親結(jié)點(diǎn)的平衡二叉樹(shù)，系統(tǒng)主要功能是：從鍵盤上輸入一整數(shù)序列，建立一顆平衡二叉樹(shù)。1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求(1) 要能夠形象方便的觀察樹(shù)的結(jié)構(gòu)；(2) 要能夠形象的演示樹(shù)的平衡過(guò)程；(3) 課程設(shè)計(jì)報(bào)告必須符合課程設(shè)計(jì)報(bào)告規(guī)范；(4) 提交合格的報(bào)告后，經(jīng)指導(dǎo)老師測(cè)試程序后，課設(shè)完成。沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告

3、2 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，我將整體程序分為四大模塊，這四個(gè)模塊相互獨(dú)立，沒(méi)有任何嵌套調(diào)用的情況，以下是四個(gè)模塊的大體分析：(1)判斷模塊：在插入一個(gè)關(guān)鍵字時(shí)，首先先對(duì)該關(guān)鍵字進(jìn)行判斷，如果該關(guān)鍵字已經(jīng)存在則不插入，否則插入該關(guān)鍵字，調(diào)用函數(shù) insertavl（） 。(2)左子樹(shù)插入模塊：如果判斷完的新關(guān)鍵字插在左子樹(shù)上，則對(duì)該以指針p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)點(diǎn)，調(diào)用函數(shù) leftprocess（） 。(3)右子樹(shù)插入模塊：如果判斷完的新關(guān)鍵字插在右子樹(shù)上，則對(duì)該以指針

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

5、入右子樹(shù)中則調(diào)用函數(shù)dispbstree（）進(jìn)行插入操作。當(dāng)所有的關(guān)鍵字都插入完事之后，進(jìn)行輸出，調(diào)用函數(shù)，dispbstree（） 。.1 功能模塊圖功能模塊圖1.判斷模塊 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 3 若在平衡二叉排序樹(shù) b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)，并返回 1，否則返回 0。若因插入而使二叉排序樹(shù)失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量 taller 反映 b 長(zhǎng)高與否。2.左子樹(shù)插入模塊對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p 指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而

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

7、2 流程圖分析流程圖分析1主函數(shù)流程圖主函數(shù)主要實(shí)現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對(duì)輸入的關(guān)鍵字進(jìn)行判斷，若該關(guān)鍵字在已建樹(shù)中已經(jīng)存在，則返回主函數(shù)接著對(duì)下一個(gè)關(guān)鍵字進(jìn)行判斷。若該關(guān)鍵字在已建樹(shù)中不存在，則插入該數(shù)，當(dāng)所有的關(guān)鍵字都插入完事之后，進(jìn)行輸出。流程圖如圖 2.1 所示。沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 4 開(kāi)始bstnode *b=null; int i,j;keytype a=6,1,2,3,4,5,0,7,8,9,n=10;ykey存在yinsertavl(b,ai,j); dispbstree(b);nfor(i=0;ikeyytaller=0; return 0;ekeyy le

8、ftprocess(b,taller)n結(jié)束rightprocess(b,taller)圖 2.2 判斷模塊流程圖3左子樹(shù)插入模塊流程圖 斷完的新關(guān)鍵字插在左子樹(shù)上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)針。流程圖如圖 2.3 所示。沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 6 開(kāi)始bstnode *p1,*p2bstnode *&p,int &taller;ynynyp-bf=0p-bf=1; taller=1p-bf=-1p-bf=0; taller=0p1-bf=1np1=p-lchild;p-lchild=p1-rchild; p1-rchil

9、d=p; p-bf=p1-bf=0; p=p1; p-bf=p1-bf=0p2-bf=0ynp2-bf=1nyp1-bf=0; p-bf=-1np1-bf=1; p-bf=0;p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p;p1-bf=-1ytaller=0p=p2; p-bf=0; ;taller=0結(jié)束圖 2.3 左子樹(shù)插入模塊流程圖4右子樹(shù)插入模塊流程圖斷完的新關(guān)鍵字插在右子樹(shù)上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)針。

10、流程圖如圖 2.4 所示。沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 7 開(kāi)始bstnode *p1,*p2bstnode *&p,int &taller;ynynyp-bf=-1p-bf=1; taller=1p-bf=1p-bf=0; taller=01-bf=-1np1=p-rchildp-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1;p-bf=p1-bf=0;p2-bf=0ynp2-bf=-1nyp1-bf=0; p-bf=1np1-bf=-1; p-bf=0p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild

11、=p1; p-rchild=p2-lchild; p2-lchild=p;p1-bf=1yp=p2; p-bf=0;taller=0結(jié)束圖 2.4 右子樹(shù)插入模塊流程圖沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 8 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析3.13.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)定義一個(gè)關(guān)鍵字類型的字符數(shù)組，其空間足夠大，用來(lái)存放關(guān)鍵字。3.23.2 算法描述算法描述1判斷關(guān)鍵字算法如下：/若在平衡二叉排序樹(shù) b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)，if(b=null) /原樹(shù)為空，插入新結(jié)點(diǎn)，樹(shù)長(zhǎng)高，置 taller 為 1b=(bstnode*)malloc(sizeof(

12、bstnode); b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1;elseif(e=b-key) /樹(shù)中已存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)則不插入taller=0; return 0;if(ekey) /繼續(xù)在*b 的左子樹(shù)中進(jìn)行搜索if(insertavl(b-lchild,e,taller)=0) /未插入 return 0;if(taller=1) /已插入到*b 的左子樹(shù)中且左子樹(shù)長(zhǎng)高 leftprocess(b,taller);else /繼續(xù)在*b 的右子樹(shù)中進(jìn)行搜索if(insertavl(b-rchild,e,taller)=

13、0) /未插入 return 0; if(taller=1) /已插入到*b 的右子樹(shù)中且右子樹(shù)長(zhǎng)高 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 9 rightprocess(b,taller);return 1;2.左平衡處理算法如下： /對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)， /指針 p 指向新的根結(jié)點(diǎn) bstnode *p1,*p2; if(p-bf=0) /原本左右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高 p-bf=1; taller=1; else if(p-bf=-1) /原本右子樹(shù)比左子樹(shù)高，現(xiàn)左右子樹(shù)等高 p-bf=0; taller=0; else /原本左子樹(shù)比右子

14、樹(shù)高，須作左子樹(shù)的平衡處理 p1=p-lchild; /p 指向*p 的左子樹(shù)根節(jié)點(diǎn) if(p1-bf=1) /新結(jié)點(diǎn)插入在*p 的左孩子的左子樹(shù)上，要做 ll 調(diào)整 p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=-1) /新結(jié)點(diǎn)插入在*p 的左孩子的右子樹(shù)上，要做 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é)點(diǎn)插入在*p2 處作為葉子結(jié)點(diǎn)的情況

15、p-bf=p1-bf=0; else if(p2-bf=1) /新結(jié)點(diǎn)插在*p2 的左子樹(shù)上的情況沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 10 p1-bf=0; p-bf=-1; else /新結(jié)點(diǎn)插在*p2 的右子樹(shù)上的情況 p1-bf=1; p-bf=0; p=p2; p-bf=0; /仍將 p 指向新的根結(jié)點(diǎn)，并置其 bf 值為 0 taller=0; 4 4 調(diào)試與分析調(diào)試與分析4.14.1 調(diào)試過(guò)程調(diào)試過(guò)程在調(diào)試程序是主要遇到一下幾類問(wèn)題：1. 本程序用到指針的地方特別多，由于指針那部分知識(shí)我掌握的不是很好，故而在這方面有困難。后來(lái)我通過(guò)在圖書館查資料、看書解決了這方面問(wèn)題。2. 對(duì)二叉樹(shù)的左

16、右子樹(shù)進(jìn)行插入調(diào)整的操作時(shí)，由于考慮問(wèn)題不夠全面而導(dǎo)致輸出結(jié)果出現(xiàn)錯(cuò)誤，在查質(zhì)料重新學(xué)習(xí)二叉樹(shù)后，解決了此問(wèn)題。沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 11 4.1 程序執(zhí)行過(guò)程程序執(zhí)行過(guò)程圖 4.1 第一組輸入執(zhí)行結(jié)果圖 4.2 第二組輸入執(zhí)行結(jié)果沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 12 參考文獻(xiàn)參考文獻(xiàn)1 嚴(yán)蔚敏.吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社，2007.2 張長(zhǎng)海.陳娟. .c 程序設(shè)計(jì)m.北京：高等教育出版社，2004. 3 譚浩強(qiáng). .c 程序設(shè)計(jì)m.北京：清華大學(xué)出版社，2005.4 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程.m.北京：清華大學(xué)出版社，2006.5 張秉權(quán). .數(shù)據(jù)結(jié)構(gòu)（c 語(yǔ)言描述

17、）.m.北京：中國(guó)輕工業(yè)出版社，2004.沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 13 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）程序代碼程序代碼#include#includetypedef int keytypetypedef struct nodekeytype key; int bf; struct node *lchild,*rchild;bstnode;void leftprocess(bstnode *&p,int &taller) /*對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針 p 指向新結(jié)點(diǎn)*/ bstnode *p1,*p2; if(p-bf=0)

18、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-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=1)沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 14 p1-bf

19、=0; p-bf=-1; else p1-bf=1; p-bf=0; p=p2; p-bf=0; taller=0; void rightprocess(bstnode *&p,int &taller) /*對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)點(diǎn)*/ bstnode *p1,*p2; 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=p1-lchild; p1-lchild=p; p-b

20、f=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áng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 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,keytype e,int &taller) /*若在平衡二叉排序樹(shù)

21、 b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)，并返回 1，否則返回 0。若因插入而使二叉排序樹(shù)失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變 taller反映 b 長(zhǎng)高與否*/ if(b=null)b=(bstnode*)malloc(sizeof(bstnode); b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1;elseif(e=b-key)taller=0; return 0;if(ekey)if(insertavl(b-lchild,e,taller)=0) return 0;if(taller=1) leftpr

22、ocess(b,taller);else if(insertavl(b-rchild,e,taller)=0) return 0; if(taller=1) rightprocess(b,taller);沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 16 return 1;void dispbstree(bstnode *b) /*以括號(hào)表示法輸出 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