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

1、 課課 程程 設(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)的平衡二叉樹的帶父親節(jié)點(diǎn)的平衡二叉樹的建立建立院（系）：計(jì)算機(jī)學(xué)院專 業(yè)：網(wǎng)絡(luò)工程班 級(jí)：學(xué) 號(hào)：姓 名： 指導(dǎo)教師： 目目 錄錄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)試與分析調(diào)試與分析.104.1 調(diào)試過程.104.1 程序執(zhí)

2、行過程.11參考文獻(xiàn)參考文獻(xiàn).12附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.13 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容設(shè)計(jì)程序，建立帶有父親結(jié)點(diǎn)的平衡二叉樹，系統(tǒng)主要功能是：從鍵盤上輸入一整數(shù)序列，建立一顆平衡二叉樹。1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求(1) 要能夠形象方便的觀察樹的結(jié)構(gòu)；(2) 要能夠形象的演示樹的平衡過程；(3) 課程設(shè)計(jì)報(bào)告必須符合課程設(shè)計(jì)報(bào)告規(guī)范；(4) 提交合格的報(bào)告后，經(jīng)指導(dǎo)老師測(cè)試程序后，課設(shè)完成。2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，我將整體程序分為四大模塊

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

4、(4)輸出模塊：對(duì)建立完成的平衡二叉樹輸出，輸出格式為二叉樹的括號(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)鍵字在已建樹中已經(jīng)存在，則返回主函數(shù)接著對(duì)下一個(gè)關(guān)鍵字進(jìn)行判斷。若該關(guān)鍵字在已建樹中不存在，則插入該數(shù)，若插入左子樹中則調(diào)用函數(shù) leftprocess（）進(jìn)行插入操作，若插入右子樹中則調(diào)用函數(shù)dispbstree（）進(jìn)行插入操作。當(dāng)所有的關(guān)鍵字都插入完事之后，進(jìn)行輸出，調(diào)用函數(shù)，dispbstr

5、ee（） 。.1 功能模塊圖功能模塊圖1.判斷模塊 若在平衡二叉排序樹 b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)，并返回 1，否則返回 0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量 taller 反映 b 長(zhǎng)高與否。2.左子樹插入模塊對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p 指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹等高，現(xiàn)因左子樹增高而使樹增；原本右子樹比左子樹高，現(xiàn)左右子樹等高；原本左子樹比右子樹高，須作左子樹的平衡處理。若新關(guān)鍵字插入在*p 的左孩子的左子樹上，要做 ll 調(diào)整，若新關(guān)鍵

6、字插入在*p 的左孩子的右子樹上，要做 lr 調(diào)整。3.右子樹子樹插入模塊對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p 指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹等高，現(xiàn)因右子樹增高而使樹增；原本左子樹比右子樹高，現(xiàn)左右子樹等高；原本右子樹比左子樹高，須作右子樹的平衡處理。若新關(guān)鍵字插入在*p 的右孩子的右子樹上，要做 rr 調(diào)整，若新關(guān)鍵字插入在*p 的右孩子的左子樹上，要做 rl 調(diào)整。.2 流程圖分析流程圖分析1主函數(shù)流程圖主函數(shù)主要實(shí)現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對(duì)輸入的關(guān)鍵字進(jìn)行判斷，若該關(guān)鍵字在已建樹中已經(jīng)存在，則返回主函數(shù)接著對(duì)下一個(gè)

7、關(guān)鍵字進(jìn)行判斷。若該關(guān)鍵字在已建樹中不存在，則插入該數(shù)，當(dāng)所有的關(guān)鍵字都插入完事之后，進(jìn)行輸出。流程圖如圖 2.1 所示。 開始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 leftprocess(b,taller)n結(jié)束rightprocess(b,taller)圖 2.2 判斷模塊流程圖3左子樹插入模塊流程圖 斷完的新關(guān)鍵字插在左子樹上，則對(duì)該以指針 p 所指結(jié)

8、點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)針。流程圖如圖 2.3 所示。開始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-rchild=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

9、-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 左子樹插入模塊流程圖4右子樹插入模塊流程圖斷完的新關(guān)鍵字插在右子樹上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)針。流程圖如圖 2.4 所示。開始bstnode *p1,*p2bstnode *&p,int &taller;ynynyp-bf=-1p-bf=1; taller=1p-bf=1p-bf=0;

10、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=p1; p-rchild=p2-lchild; p2-lchild=p;p1-bf=1yp=p2; p-bf=0;taller=0結(jié)束圖 2.4 右子樹插入模塊流程圖3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析3.13.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)

11、定義一個(gè)關(guān)鍵字類型的字符數(shù)組，其空間足夠大，用來存放關(guān)鍵字。3.23.2 算法描述算法描述1判斷關(guān)鍵字算法如下：/若在平衡二叉排序樹 b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)，if(b=null) /原樹為空，插入新結(jié)點(diǎn)，樹長(zhǎng)高，置 taller 為 1b=(bstnode*)malloc(sizeof(bstnode); b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1;elseif(e=b-key) /樹中已存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)則不插入taller=0; return 0;if(ekey) /繼續(xù)

12、在*b 的左子樹中進(jìn)行搜索if(insertavl(b-lchild,e,taller)=0) /未插入 return 0;if(taller=1) /已插入到*b 的左子樹中且左子樹長(zhǎng)高 leftprocess(b,taller);else /繼續(xù)在*b 的右子樹中進(jìn)行搜索if(insertavl(b-rchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的右子樹中且右子樹長(zhǎng)高 rightprocess(b,taller);return 1;2.左平衡處理算法如下： /對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，

13、 /指針 p 指向新的根結(jié)點(diǎn) 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é)點(diǎn) if(p1-bf=1) /新結(jié)點(diǎn)插入在*p 的左孩子的左子樹上，要做 ll 調(diào)整 p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; else if(p1

14、-bf=-1) /新結(jié)點(diǎn)插入在*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é)點(diǎn)插入在*p2 處作為葉子結(jié)點(diǎn)的情況 p-bf=p1-bf=0; else if(p2-bf=1) /新結(jié)點(diǎn)插在*p2 的左子樹上的情況 p1-bf=0; p-bf=-1; else /新結(jié)點(diǎn)插在*p2 的右子樹上的情況 p1-bf=1; p-bf=0; p=p2; p-bf=0; /仍將 p 指向新的根結(jié)點(diǎn)，并置其 bf 值為

15、0 taller=0; 4 4 調(diào)試與分析調(diào)試與分析4.14.1 調(diào)試過程調(diào)試過程在調(diào)試程序是主要遇到一下幾類問題：1. 本程序用到指針的地方特別多，由于指針那部分知識(shí)我掌握的不是很好，故而在這方面有困難。后來我通過在圖書館查資料、看書解決了這方面問題。2. 對(duì)二叉樹的左右子樹進(jìn)行插入調(diào)整的操作時(shí)，由于考慮問題不夠全面而導(dǎo)致輸出結(jié)果出現(xiàn)錯(cuò)誤，在查質(zhì)料重新學(xué)習(xí)二叉樹后，解決了此問題。4.1 程序執(zhí)行過程程序執(zhí)行過程圖 4.1 第一組輸入執(zhí)行結(jié)果圖 4.2 第二組輸入執(zhí)行結(jié)果參考文獻(xiàn)參考文獻(xiàn)1 嚴(yán)蔚敏.吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社，2007.2 張長(zhǎng)海.陳娟. .c 程序設(shè)計(jì)m.北

16、京：高等教育出版社，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 語言描述）.m.北京：中國(guó)輕工業(yè)出版社，2004.附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）程序代碼程序代碼#include#includetypedef int keytypetypedef struct nodekeytype key; int bf; struct node *lchild,*rchild;bstnode;void leftprocess(bstnode *&p,in

17、t &taller) /*對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(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-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

18、=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=1) p1-bf=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)為根的二叉樹作右平衡旋轉(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

19、=0; taller=0; else p1=p-rchild; if(p1-bf=-1) p-rchild=p1-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) p1-bf=0; p-bf=1; else p1-bf=-1; p-bf=0; p=p2; p-bf=0; talle

20、r=0; int insertavl(bstnode*&b,keytype e,int &taller) /*若在平衡二叉排序樹 b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)，并返回 1，否則返回 0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉(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

21、;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);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,7,8,9,n=