線索二叉樹(shù)課程設(shè)計(jì)說(shuō)明書(shū)格式

1、 中 北 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū)學(xué) 院、系：軟件學(xué)院專 業(yè)：軟件工程班 級(jí)：15140X04學(xué) 生 姓 名：張航學(xué) 號(hào)：1514040423設(shè) 計(jì) 題 目：線索二叉樹(shù)的應(yīng)用 起 迄 日 期: 2016年12月16日2016年12月29日指 導(dǎo) 教 師:付東來(lái)日期: 2016年12月29日1 設(shè)計(jì)目的 數(shù)據(jù)結(jié)構(gòu)課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要達(dá)到以下目的：n 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；n 初步掌握軟件開(kāi)發(fā)過(guò)程

2、的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；n 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。2 任務(wù)概述設(shè)計(jì)內(nèi)容： （1）建立線索二叉樹(shù)，實(shí)現(xiàn)插入、刪除操作。 （2）線索二叉樹(shù)的遍歷（本程序中使用中序遍歷方法）設(shè)計(jì)要求： 實(shí)現(xiàn)線索樹(shù)建立、插入、刪除、恢復(fù)線索任務(wù)分析：該任務(wù)是關(guān)于線索二叉樹(shù)的運(yùn)算，其中的基本運(yùn)算應(yīng)基于二叉樹(shù)，但又有所不同，首先應(yīng)了解問(wèn)題有：（1）線索二叉樹(shù)如何建立：是通過(guò)二叉樹(shù)來(lái)實(shí)現(xiàn)線索化，還是直接進(jìn)行線索化的輸入。若由二叉樹(shù)建立而來(lái)，該二叉樹(shù)應(yīng)如何輸入，對(duì)具體

3、的二叉樹(shù)應(yīng)該使初次使用者明白使用的格式。（2）該程序重點(diǎn)內(nèi)容是有關(guān)二叉樹(shù)的插入、刪除和查找前驅(qū)后繼，在進(jìn)行具體操作時(shí)，該如何實(shí)現(xiàn)查找到相應(yīng)結(jié)點(diǎn)，線索應(yīng)該如何改變才能不破壞線索二叉樹(shù)的結(jié)構(gòu)。重點(diǎn)在于插入刪除是分清楚插入刪除位置的雙親結(jié)點(diǎn)與被插入刪除的結(jié)點(diǎn)的孩子關(guān)系。3 模塊劃分（1）定義數(shù)據(jù)結(jié)構(gòu)模塊：typedef struct BiThrNodeElemType data;struct BiThrNode *lchild,*rchild;int LTag,RTag; BiThrNode,*BiThrTree;（2）功能函數(shù)：二叉樹(shù)的建立函數(shù)：void CreateBiTree(BiThrTre

4、e &T)詢二叉樹(shù)深度函數(shù)：int Depth(BiThrTree T)帶頭結(jié)點(diǎn)的二叉樹(shù)中序線索化函數(shù)：void InOrderThreading(BiThrTree &Thrt,BiThrTree T)以結(jié)點(diǎn)T為根的子樹(shù)中序線索化：void InThreading(BiThrTree &T)中序遍歷函數(shù)：void InOrderTraverse_Thr(BiThrTree Thrt)查找某結(jié)點(diǎn)函數(shù)：BiThrTree Search(BiThrTree T,ElemType key)查找某結(jié)點(diǎn)函數(shù)：BiThrTree SearchPre(BiThrTree point,

5、BiThrTree child) 插入函數(shù)：Status InsertTree(BiThrTree T)刪除函數(shù)：Status DeleteTree(BiThrTree T)主函數(shù)：main()整體結(jié)構(gòu)圖： 開(kāi) 始 創(chuàng)建二叉樹(shù) 線索化二叉樹(shù) Main( )打印二叉樹(shù)插入結(jié)點(diǎn)刪除結(jié)點(diǎn)4 主要函數(shù)說(shuō)明及其N-S圖4.1詳細(xì)設(shè)計(jì)思想建立二叉樹(shù)（即指在內(nèi)存中建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)），建立一個(gè)二叉鏈表，需按某種順序一次輸入二叉樹(shù)中的結(jié)點(diǎn)，且輸入順序必須隱含結(jié)點(diǎn)間的邏輯結(jié)構(gòu)信息。對(duì)于一般的二叉樹(shù)，需添加虛結(jié)點(diǎn)，使其成為完全二叉樹(shù)。二叉樹(shù)的中序線索化算法與中序遍歷算法類似。只需要將遍歷算法中訪問(wèn)結(jié)點(diǎn)的操作具體

6、化為建立正在訪問(wèn)的結(jié)點(diǎn)與其非空中序前趨結(jié)點(diǎn)間線索。該算法應(yīng)附設(shè)一個(gè)指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)（pre的初值應(yīng)為NULL），而指針p指示當(dāng)前正在訪問(wèn)的結(jié)點(diǎn)。結(jié)點(diǎn)*pre是結(jié)點(diǎn)*p的前趨，而*p是*pre的后繼。結(jié)點(diǎn)插入算法：由線索二叉樹(shù)的定義易知插入的節(jié)點(diǎn)定是個(gè)葉子節(jié)點(diǎn)，需注意線索的修改，可分為兩種情況：（1）：插入的節(jié)點(diǎn)t是右兒子，t的中序后繼是其父親的中序后繼，中序前驅(qū)是其父親。（2）：插入的節(jié)點(diǎn)t是左兒子，t的中序前驅(qū)是其父親的中序前驅(qū)，中序后繼是其父親。結(jié)點(diǎn)刪除算法：刪除的情況與搜索二叉樹(shù)的刪除的類似（1）：刪除的節(jié)點(diǎn)p是葉子節(jié)點(diǎn)，直接刪除，修改其父親的線索。（2）：刪除的節(jié)點(diǎn)p

7、有一個(gè)兒子，p有一個(gè)左兒子，以p為根的左子樹(shù)中的具有最大值節(jié)點(diǎn)的t中序后繼是p的中序后繼，中序前驅(qū)不變；p有一個(gè)右兒子，以p為根的右子中的具有最小值節(jié)點(diǎn)t中序前驅(qū)是p的中序前驅(qū)，中序后繼不變。（3）：刪除的節(jié)點(diǎn)p有二個(gè)兒子，轉(zhuǎn)化為葉子節(jié)點(diǎn)或只有一個(gè)兒子節(jié)點(diǎn)的刪除。4.2各功能函數(shù)流程圖圖4.1 ：創(chuàng)建二叉樹(shù)圖4.2 ：查詢二叉樹(shù)深度圖4.3 ：中序線索化二叉樹(shù)圖4.4 ：中序遍歷輸出二叉樹(shù)圖4.5 ：查詢結(jié)點(diǎn)圖4.6 ：查詢結(jié)點(diǎn)的雙親結(jié)點(diǎn)圖4.7 ：插入結(jié)點(diǎn)圖4.8 ：刪除結(jié)點(diǎn)5 程序運(yùn)行數(shù)據(jù)及其結(jié)果1_按中序輸入一課二叉樹(shù)，建樹(shù)并實(shí)現(xiàn)線索化2_建樹(shù)完成后進(jìn)入主菜單，可執(zhí)行相應(yīng)插入、刪除、打印

8、操作3_選擇操作1，以中序遍歷輸出線索二叉樹(shù)4_選擇操作2，在線索二叉樹(shù)中插入新結(jié)點(diǎn)5_選擇操作3，刪除二叉樹(shù)中的結(jié)點(diǎn)6 課程設(shè)計(jì)心得通過(guò)這次做課程設(shè)計(jì)，發(fā)現(xiàn)了學(xué)習(xí)中的很多問(wèn)題，平時(shí)學(xué)習(xí)的東西在做起來(lái)時(shí)有很大的困難，獨(dú)立構(gòu)思一個(gè)程序很難，不僅僅是要實(shí)現(xiàn)某個(gè)功能，而且還要把這些功能結(jié)合起來(lái)，成為一個(gè)能良好運(yùn)行的程序，需要對(duì)錯(cuò)誤輸入提示，需要排除debug，需要設(shè)計(jì)每個(gè)使用界面等等。剛開(kāi)始的時(shí)候是先寫(xiě)了一部分代碼，后來(lái)就發(fā)覺(jué)應(yīng)該先把函數(shù)的功能需要弄清楚，整理出一個(gè)大框架。再此基礎(chǔ)上完善程序的功能。這次的線索二叉樹(shù)的插入和刪除課本上沒(méi)有相應(yīng)的內(nèi)容，為了完成課設(shè)，在網(wǎng)絡(luò)上一直翻看別人的博客，先看明白思

9、想，在盡量看懂人家的代碼。最后是借鑒了別人的思想，自己畫(huà)圖，才把代碼實(shí)現(xiàn)出來(lái)。其間廢了好大的力氣。而且雖說(shuō)是實(shí)現(xiàn)了，但函數(shù)的語(yǔ)句還是顯得有些亂，自己為了看懂還加了一大堆注釋。不便于和同學(xué)交流。一直以來(lái)，覺(jué)得自己數(shù)據(jù)結(jié)構(gòu)學(xué)的還行，起碼概念那些都能理解，知道說(shuō)了些什么，也大致知道怎么個(gè)原理，考完試也感覺(jué)良好，但是一到課程設(shè)計(jì)，看的題目挺簡(jiǎn)單，二叉樹(shù)，可是一去上手做了去無(wú)從下手，一點(diǎn)都不會(huì)，只會(huì)紙上談兵，我也知道變成這東西是需要多實(shí)踐的，但沒(méi)想到真的坐到那兒去編時(shí)，卻怎么也下不了手，于是很失落的回宿舍查閱書(shū)籍以及上網(wǎng)百度資料，仔細(xì)的參讀了很長(zhǎng)時(shí)間后，自己不停的磨合，終于完成個(gè)大概，不可避免調(diào)試中又出

10、些問(wèn)題，經(jīng)過(guò)好幾遍的查錯(cuò)，一點(diǎn)一點(diǎn)的改，最終終于完成現(xiàn)在的程序。 通過(guò)這段時(shí)間的課程設(shè)計(jì)，我認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是一門(mén)比較難的課程，但同時(shí)有時(shí)一門(mén)基礎(chǔ)切極為重要的課程。需要多花時(shí)間上機(jī)練習(xí)。這次的程序訓(xùn)練培養(yǎng)了我實(shí)際分析問(wèn)題、編程和動(dòng)手能力，使我掌握了程序設(shè)計(jì)的基本技能，提高了我適應(yīng)實(shí)際，實(shí)踐編程的能力。 總的來(lái)說(shuō)，這次課程設(shè)計(jì)讓我獲益匪淺，對(duì)數(shù)據(jù)結(jié)構(gòu)也有了進(jìn)一步的理解和認(rèn)識(shí)。附錄：#include<stdio.h> #include<stdlib.h>#include<math.h>#include<windows.h>/windows自帶函數(shù)庫(kù)：S

11、leep()函數(shù) #define ERROR 0#define OK 1typedef char ElemType;/二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)域可隨時(shí)修改數(shù)據(jù)類型 typedef int Status;typedef struct BiThrNode/二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) ElemType data;struct BiThrNode *lchild,*rchild;int LTag,RTag;BiThrNode,*BiThrTree;/BiThrTree用來(lái)聲明指針類型變量 static BiThrTree pre = (BiThrTree)malloc(sizeof(BiThrNode);void Cre

12、ateBiTree(BiThrTree &T)/前序創(chuàng)建 char ch;ch = getchar();if(ch = '#') T = NULL;elseT = (BiThrTree)malloc(sizeof(BiThrNode);T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);void InThreading(BiThrTree &T)/以T為根節(jié)點(diǎn)的二叉樹(shù)線索化 if(T)InThreading(T->lchild);if(!(T->lchild)T-

13、>LTag = 1;T->lchild = pre;else T->LTag = 0;if(!(pre->rchild)/pre被定義為全局變量 pre->RTag = 1;pre->rchild = T;else T->RTag = 0;pre = T;InThreading(T->rchild);void InOrderThreading(BiThrTree &Thrt,BiThrTree T)/帶頭結(jié)點(diǎn)的二叉樹(shù)中序線索化 Thrt = (BiThrTree)malloc(sizeof(BiThrNode);Thrt->LTag

14、 = 0;Thrt->RTag = 1;Thrt->rchild = Thrt;if(!T) Thrt->lchild = Thrt;elseThrt->lchild = T;pre = Thrt;InThreading(T);pre->rchild = Thrt;pre->RTag = 1;Thrt->rchild = pre; void InOrderTraverse_Thr(BiThrTree Thrt)/中序遍歷線索二叉樹(shù) BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode);p = Thrt-&g

15、t;lchild;printf("二叉樹(shù)中序遍歷結(jié)果為："); while(p!=Thrt)while(p->LTag=0) p = p->lchild;printf(" -> %c",p->data);while(p->RTag=1&&p->rchild!=Thrt)p = p->rchild;printf(" -> %c",p->data);p = p->rchild;puts("");/回車換行 BiThrTree Search(Bi

16、ThrTree T,ElemType key)/查找data = key 的結(jié)點(diǎn) ,并返回該節(jié)點(diǎn)的指針地址 BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode);p = T->lchild;while(p!=T)while(p->LTag=0) p = p->lchild;if(p->data=key) return p;while(p->RTag =1&&p->rchild!=T)p = p->rchild;if(p->data=key) return p;p = p->rch

17、ild;return NULL;BiThrTree SearchPre(BiThrTree point,BiThrTree child) / 查找以point為根，child的雙親結(jié)點(diǎn) BiThrTree p1,p2;if(point!=NULL)if(point->LTag!=1&&point->lchild=child)|(point->RTag!=1&&point->rchild=child) return point;/找到則返回elseif(point->LTag!=1) p1=SearchPre(point->lc

18、hild,child); if(p1!=NULL) return p1; if(point->RTag!=1) p2=SearchPre(point->rchild,child); if(p2!=NULL) return p2; return NULL; else return NULL; Status InsertTree(BiThrTree T)/線索二叉樹(shù)的插入函數(shù) BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode);/新結(jié)點(diǎn)，要插入的結(jié)點(diǎn) BiThrTree t ;/要插入結(jié)點(diǎn)的父母結(jié)點(diǎn) ElemType key;int n

19、= 1,temp = 0;while(temp=0)n = 1;t = NULL;InOrderTraverse_Thr(T);/遍歷輸出線索二叉樹(shù) printf("請(qǐng)輸入新結(jié)點(diǎn)的值：");scanf("%c",&(p->data);getchar(); printf("請(qǐng)問(wèn)新結(jié)點(diǎn)的父母結(jié)點(diǎn)為：");scanf("%c",&key);getchar();printf("請(qǐng)問(wèn)新結(jié)點(diǎn)是%c結(jié)點(diǎn)的左孩子or右孩子：(0-左,1-右)",key);while(1)/循環(huán)執(zhí)行 sca

20、nf("%d",&n);getchar(); if(n=0|n=1) break;puts("輸入的值應(yīng)為0或1，請(qǐng)重新輸入！");t = Search(T,key);if(!t) puts("輸入的父母結(jié)點(diǎn)不存在于樹(shù)中，查找失??！"); elseif(n = 0)/插入左子樹(shù) p->RTag = 1;p->rchild = t;/父母結(jié)點(diǎn)的前驅(qū)p->LTag = t->LTag;p->lchild = t->lchild; t->LTag = 0;t->lchild = p;t

21、 = p;if(p->LTag=0)/找到p的左子樹(shù)的最右結(jié)點(diǎn)，改為自己前驅(qū) p = p->lchild;while(p->RTag = 0)p = p->rchild;p->rchild = t;else/插入右子樹(shù) p->LTag = 1;p->lchild = t;p->RTag = t->RTag;p->rchild = t->rchild;t->RTag = 0;t->rchild = p;t = p;if(p->RTag=0)p = p->rchild;while(p->LTag = 0

22、)p = p->lchild;p->lchild = t;printf("繼續(xù) 插入結(jié)點(diǎn)請(qǐng)按 0 返回主界面 請(qǐng)按1：");while(1)scanf("%d",&temp);getchar(); if(temp = 1) break;else if(temp = 0) break;else puts("輸入錯(cuò)誤，應(yīng)輸入0-繼續(xù)插入 1-主界面：");return OK;Status DeleteTree(BiThrTree T)/線索二叉樹(shù)的刪除函數(shù) BiThrTree t,pre,save;/pre_待刪結(jié)點(diǎn)的

23、雙親，屏蔽了全局變量pre save_保留要?jiǎng)h除的結(jié)點(diǎn)，用以free(save); ElemType key;int n = -1,temp = 0;/temp 用來(lái)判斷是否循環(huán)，繼續(xù)使用刪除結(jié)點(diǎn)函數(shù) while(temp = 0) InOrderTraverse_Thr(T);/遍歷輸出 printf("請(qǐng)輸入要?jiǎng)h除的結(jié)點(diǎn)：");scanf("%c",&key);getchar();t = Search(T,key);/在頭結(jié)點(diǎn)為T(mén)的樹(shù)中找到key結(jié)點(diǎn)的位置 if(!t) puts("所要?jiǎng)h除的結(jié)點(diǎn)不存在！");elsepr

24、e = SearchPre(T,t);save = t;if(t->LTag=1&&t->RTag=1)/要?jiǎng)h除的結(jié)點(diǎn)沒(méi)有孩子 if(pre->lchild=t)pre->LTag = t->LTag;pre->lchild = t->lchild;else if(pre->rchild=t)pre->RTag = t->RTag;pre->rchild = t->rchild;else puts("查找雙親結(jié)點(diǎn)可能有誤1");else if(t->LTag=1&&

25、t->RTag=0)/要?jiǎng)h除的結(jié)點(diǎn)僅有右孩子 if(pre->lchild=t)/被刪結(jié)點(diǎn)是雙親的左孩子 pre->lchild = t->rchild;pre = t;t = t->rchild;while(t->LTag=0) t = t->lchild;t->lchild = pre->lchild;else if(pre->rchild=t)/被刪結(jié)點(diǎn)是雙親的右結(jié)點(diǎn) pre->rchild = t->rchild;t = t->rchild;while(t->LTag=0) t = t->lchi

26、ld;t->lchild = pre;else puts("查找雙親結(jié)點(diǎn)可能有誤2");else if(t->LTag=0&&t->RTag=1)/要?jiǎng)h除的結(jié)點(diǎn)僅有左孩子 if(pre->lchild=t)/被刪結(jié)點(diǎn)是雙親的左孩子pre->lchild = t->lchild;pre = t;pre = pre->lchild;/修改pre為待刪結(jié)點(diǎn)的左孩子 while(pre->RTag=0) pre = pre->rchild;pre->rchild = t->rchild;else if

27、(pre->rchild=t)/被刪結(jié)點(diǎn)是雙親的右孩子pre->rchild = t->lchild;pre = t;pre = pre->lchild;while(pre->RTag) pre = pre->rchild;pre->rchild = t->rchild;else puts("查找雙親結(jié)點(diǎn)可能有誤3");else/要?jiǎng)h除的結(jié)點(diǎn)有兩個(gè)孩子 if(pre->lchild=t)pre->lchild = t->lchild;/被刪除結(jié)點(diǎn)的左樹(shù)作為根節(jié)點(diǎn) pre = t->lchild;/開(kāi)始查

28、找t的前驅(qū)while(pre->RTag=0) pre = pre->rchild;pre->RTag = 0;pre->rchild = t->rchild;t = t->rchild;/開(kāi)始查找t的后繼while(t->LTag=0) t = t->lchild;t->LTag = 1;t->lchild = pre; else if(pre->rchild=t)pre->rchild = t->lchild;pre = t->lchild;/開(kāi)始查找t的前驅(qū)while(pre->RTag=0) pr

29、e = pre->rchild;pre->RTag = 0;pre->rchild = t->rchild;t = t->rchild;/開(kāi)始查找t的后繼while(t->LTag=0) t = t->lchild;t->LTag = 1;t->lchild = pre; else puts("查找雙親結(jié)點(diǎn)可能有誤4");free(save);printf("繼續(xù)刪除結(jié)點(diǎn) 請(qǐng)按 0 返回主界面 請(qǐng)按1：");while(1)scanf("%d",&temp);getchar(); if(temp = 1) break;else if(temp = 0) break;else puts("輸入錯(cuò)