1、課程設(shè)計(jì)說明書（數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)）專 業(yè): 網(wǎng)絡(luò)工程 課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 班級: 網(wǎng)絡(luò)B11-1設(shè)計(jì)題目: 線索二叉樹的應(yīng)用 設(shè)計(jì)時間: 2013-2-25 至 2013-3-8 評 語:_評閱成績: 評閱教師: 一、問題描述與需求分析1、問題描述 本實(shí)驗(yàn)的問題是建立一個線索二叉樹，并實(shí)現(xiàn)線索二叉樹的插入、刪除、恢復(fù)線索等功能。2、功能需求分析 本程序要實(shí)現(xiàn)的功能是： 1. 線索二叉樹的建立。 2.線索二叉樹的插入。 3.線索二叉樹的刪除。 4.線索二叉樹的恢復(fù)。 想要完成上面的功能，我們首先是要知道上面是線索二叉樹。我們可以從數(shù)據(jù)結(jié)構(gòu)的書上找到答案，利用二叉鏈表的空指針域?qū)⒖盏淖蠛?/p>

2、子指針域改為指向其前驅(qū)，空的右孩子指針域改為指向其后繼。這種改變指向的指針稱為線索，加上了線索的二叉鏈表稱為線索鏈表。 N個結(jié)點(diǎn)的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)的在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針，這種加上了線索的二叉鏈表稱為線索鏈表。相應(yīng)的二叉樹稱為線線索二叉樹。根據(jù)線索二叉樹性質(zhì)的不同，線索二叉樹可以分為前序線索二叉樹，中序線索二叉樹和后續(xù)線索二叉樹三種，此次課程設(shè)計(jì)中使用的是中序線索二叉樹。二、概要設(shè)計(jì)1、總體設(shè)計(jì)思路 首先就是要建立一個二叉樹，然后再對二叉樹進(jìn)行線索化。 線索鏈表中的結(jié)點(diǎn)結(jié)構(gòu)為：其中：線索二叉樹及其存儲結(jié)構(gòu)如在線索樹上進(jìn)行遍歷

3、，只需先找到序列中的第一個結(jié)點(diǎn)，然后依次找結(jié)點(diǎn)后繼為空時而止。以上圖為例子說明在線索樹中查找結(jié)點(diǎn)的后繼。樹中所有葉子的結(jié)點(diǎn)是線索，則右鏈域直接指示結(jié)點(diǎn)的后繼，如結(jié)點(diǎn)b的后繼為結(jié)點(diǎn)*。樹中所有非終端結(jié)點(diǎn)的右鏈均為指針，則無法由此得到后繼的信息。然而根據(jù)中序遍歷的規(guī)律可知，結(jié)點(diǎn)的后繼應(yīng)是遍歷其右子樹時訪問的第一個結(jié)點(diǎn)，即右子樹最左下的結(jié)點(diǎn)。列入在找結(jié)點(diǎn)*的后繼時，首先沿右指針找到其右子樹的根結(jié)點(diǎn)“”，然后順其左指針往下直至其左標(biāo)志為1的結(jié)點(diǎn)，即為結(jié)點(diǎn)* 的后繼，在圖中是結(jié)點(diǎn)c。反之，在中序結(jié)點(diǎn)中找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若其左標(biāo)志為“1”，則左鏈為線索，指示其前驅(qū)，否則遍歷左子樹時最后訪問的一個結(jié)點(diǎn)（左

4、子樹最右下的結(jié)點(diǎn)）為其前驅(qū)。 開始定義二叉樹 建立二叉樹 選擇菜單輸入i(1-5) N N N N I=3 I=2 I=1 I=5 I=4 輸出線索二叉樹二叉樹的線索化中序輸出二叉樹Y Y Y Y Y刪除結(jié)點(diǎn)并線索haunted插入結(jié)點(diǎn)并線索化 結(jié)束 程序流程圖2、 模塊簡介 本程序有五個模塊功能。每個模塊功能均實(shí)現(xiàn)特定的功能。1. 二叉樹的建立：中序輸入二叉樹，為程序提供數(shù)據(jù)，輸入的時候空域用表示。2. 進(jìn)行二叉樹的線索化： 按中序遍歷順序?qū)⒍鏄渚€索化，只需要在遍歷的過程中將二叉樹的每個結(jié)點(diǎn)的空的左右孩子的指針域分別修改為指向其前驅(qū)和后繼，若其左子樹為空，則將其左孩子域線索化，使其左孩子指

5、針lchild指向其后繼，并且ltag置1. 3插入操作： 輸入要插入的結(jié)點(diǎn)信息，然后再查找要插入結(jié)點(diǎn)的位置，插入新結(jié)點(diǎn)。 4刪除操作，確定要刪除的結(jié)點(diǎn)，查找出要刪除的結(jié)點(diǎn)，找到之后會顯示ltag和rtag信息。 5輸出線索二叉樹，輸出的線索二叉樹為經(jīng)過處理的二叉樹。 三、詳細(xì)設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 程序采用線索鏈表做存儲結(jié)構(gòu)。程序中有二叉樹的建立，插入，刪除，恢復(fù)線索，這些操作都是基于線索鏈表作的。2、 算法分析與實(shí)現(xiàn)二叉樹的建立： 建立一個二叉樹，需要按照某種順序依次輸入二叉樹中的結(jié)點(diǎn)，且該輸入順序必須隱含結(jié)點(diǎn)間的邏輯結(jié)構(gòu)信息。這種建立的方法，按全二叉樹的層次順序，一次輸入結(jié)點(diǎn)信息建立二叉鏈

6、表的過程。以表示空結(jié)點(diǎn)，以#表示輸入結(jié)束的標(biāo)志，。 一次輸入結(jié)點(diǎn)信息，若其不是虛結(jié)點(diǎn)，則建立一個新結(jié)點(diǎn)。若新結(jié)點(diǎn)是第一個結(jié)點(diǎn)，則令其為跟結(jié)點(diǎn)，否則將新結(jié)點(diǎn)作為孩子鏈接到它的父親結(jié)點(diǎn)上。 在函數(shù)中設(shè)置一個隊(duì)列，該隊(duì)列是一個指針類型的數(shù)組，保存以輸入的結(jié)點(diǎn)的地址。使隊(duì)列指針front指向當(dāng)前與孩子建立鏈接的父親結(jié)點(diǎn)，隊(duì)尾指針rear指向當(dāng)前輸入的結(jié)點(diǎn)。若rear為偶數(shù)，則該結(jié)點(diǎn)為父結(jié)點(diǎn)的左孩子，若rear為奇數(shù)，則為父結(jié)點(diǎn)的右孩子。若父結(jié)點(diǎn)或孩子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無需鏈接，若父結(jié)點(diǎn)與其兩個孩子結(jié)點(diǎn)鏈接完畢，則使front指向下一個等待鏈接的父結(jié)點(diǎn)。 算法實(shí)現(xiàn)： Bithptr *Qmaxsize;

7、/建隊(duì)為指針類型Bithptr *CreatTree()front=1;rear=0; /置空隊(duì)if(ch!='') /不是虛結(jié)點(diǎn).則建立結(jié)點(diǎn)s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;if(s!=NULL&&Qfront!=NULL) /孩子和雙親結(jié)點(diǎn)都不是虛結(jié)點(diǎn)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s;if(

8、rear%2=1)front+; /結(jié)點(diǎn)*Qfront的兩個孩子處理完front+1線索化算法：線索過程需要按照一定的順序進(jìn)行，此次程序使用的是中序遍歷，所以線索化也將使用中序線索化。按照某種遍歷順序?qū)⒍鏄渚€索化，只需在遍歷的過程中將二叉樹的每個結(jié)點(diǎn)空的左右孩子的指針分別修改為指向其前驅(qū)和后繼。若其左右樹為空，則將其左孩子域線索化，使其左孩子指針lchild指向其后繼，并且ltag為1.要實(shí)現(xiàn)線索化，就要知道結(jié)點(diǎn)*pre是*p的前驅(qū)，而*p是*pre的后繼。這樣，當(dāng)遍歷到結(jié)點(diǎn)*p時，可以進(jìn)行，若*P有空指針域，則將相應(yīng)的標(biāo)志為1,；若*p的左線索標(biāo)志已經(jīng)建立（p->ltag=1），則可

9、使其前驅(qū)線索化，令p->lchild=pre；若*pre的左線索標(biāo)志已經(jīng)建立（pre->rtag=1），則可使其后繼線索化，令pre->rchild=p; 算法實(shí)現(xiàn);void PreThread(Bithptr *root)PreThread(p->lchild); /左子樹線索化if(pre&&pre->rtag=1)pre->rchild=p; /前驅(qū)結(jié)點(diǎn)后繼線索化if(p->lchild=NULL) p->ltag=1; p->lchild=pre;if(p->rchild=NULL) /后繼結(jié)點(diǎn)前驅(qū)線索化p-&

10、gt;rtag=1;pre=p;PreThread(p->rchild);插入結(jié)點(diǎn)函數(shù)： 在書中插入一個結(jié)點(diǎn)，必須要以固定的規(guī)則來進(jìn)行插入。本程序中樹的輸出使用了中序輸出的方法，所以插入的時候使用的規(guī)則就是以中序輸出為順序，先查找到一個點(diǎn)，再將要插入的結(jié)點(diǎn)，作為該結(jié)點(diǎn)的前驅(qū)插入樹中。如中序?yàn)椋篸beafcg。插入的結(jié)點(diǎn)為：b,則插入后的順序?yàn)閐wbeafcg。 使用查找孩子指針函數(shù)來查找結(jié)點(diǎn)位置的指針。在查找的過程中要處理好線索指針和孩子指針的關(guān)系，不能將線索也當(dāng)做孩子來處理了。并且在循環(huán)的判斷中，且不能使用以前的空位結(jié)束語句，而是要用標(biāo)志域來進(jìn)行判斷。在查找的過程中，考慮到樹的遞歸性質(zhì)

11、，所以講查找函數(shù)也設(shè)置成遞歸函數(shù)。 算法實(shí)現(xiàn)： Bithptr*SearchChild(Bithptr*point,char findnode)Bithptr *point1,*point2;if(point!=NULL)if(point->data=findnode)return point; /找到結(jié)點(diǎn)的信息.返回指針elseif(point->ltag!=1) / 判斷是否有左子樹point1=SearchChild(point->lchild,findnode);/遞歸if(point1!=NULL)return point1;if(point->rtag!=1

12、) /判斷是否有右子樹point2=SearchChild(point->rchild,findnode);/遞歸if(point2!=NULL)return point2;return NULL;elsereturn NULL; 在一棵樹種插入一個結(jié)點(diǎn)，因?yàn)椴迦氲奈恢貌煌蛯?yīng)著不同的插入情況。當(dāng)插入結(jié)點(diǎn)有左孩子時：找到左孩子的最右下結(jié)點(diǎn)將待插的結(jié)點(diǎn)插為其結(jié)點(diǎn)的右孩子。當(dāng)插入結(jié)點(diǎn)沒有左孩子時：直接將帶插的結(jié)點(diǎn)插為其結(jié)點(diǎn)的左孩子。 算法實(shí)現(xiàn)：􀈎當(dāng)結(jié)點(diǎn)有左子樹時.p2=child;child=child->lchild;while(child->rchild

13、&&child->rtag=0) /左子樹的最右下結(jié)點(diǎn)child=child->rchild;p1->rchild=child->rchild; /后繼線索化p1->rtag=1;child->rtag=0;child->rchild=p1; /連接結(jié)點(diǎn)p1->lchild=child; /前驅(qū)線索化p1->ltag=1;􀈎當(dāng)結(jié)點(diǎn)沒左孩子的時.p1->lchild=child->lchild; /前驅(qū)化child->ltag=0;p1->ltag=1;child->lchild

14、=p1;p1->rchild=childp1->rtag=1;刪除結(jié)點(diǎn)函數(shù)： 要在函數(shù)中刪除一個結(jié)點(diǎn)，有幾種不同的情況，在刪除結(jié)點(diǎn)之前要先找到要刪除的結(jié)點(diǎn)，調(diào)用查找孩子結(jié)點(diǎn)的函數(shù)Bithptr *SearchChild(Bithptr*point,char findnode)，找到其結(jié)點(diǎn)指針的指針。刪除過程中設(shè)計(jì)的指針變換需要父親結(jié)點(diǎn)的指針，所以就調(diào)用查找父親結(jié)點(diǎn)的函數(shù)Bithptr*SearchPre(Bithptr *point,Bithptr *child)來查找該結(jié)點(diǎn)的父親結(jié)點(diǎn)的指針。 刪除的過程中有不同的情況。 1當(dāng)要刪除結(jié)點(diǎn)為父親的左孩子時 若要刪除結(jié)點(diǎn)沒有左右孩子：則

15、直接刪除； 若要刪除結(jié)點(diǎn)有左孩子沒有右孩子：則要刪除結(jié)點(diǎn)的左孩子給父親結(jié)點(diǎn)的左孩子； 若要刪除結(jié)點(diǎn)有右孩子沒有左孩子：則將要刪除結(jié)點(diǎn)的右孩子給父親結(jié)點(diǎn)的左孩子； 若要刪除結(jié)點(diǎn)左右孩子都有：將要刪除結(jié)點(diǎn)的左子樹的右子樹接到孩子結(jié)點(diǎn)的右子樹的最左下結(jié)點(diǎn)的左子樹.再將孩子結(jié)點(diǎn)的右子樹接到孩子結(jié)點(diǎn)左子樹的右子樹。 2當(dāng)要刪除結(jié)點(diǎn)是父親結(jié)點(diǎn)的右孩子時 若要刪除結(jié)點(diǎn)沒有左右孩子。則直接將空給頭指針。 若要刪除結(jié)點(diǎn)有左孩子沒右孩子，則將孩子結(jié)點(diǎn)的左孩子作為頭結(jié)點(diǎn)。 若要刪除結(jié)點(diǎn)有右孩子沒左孩子，則將孩子結(jié)點(diǎn)的右孩子作為頭結(jié)點(diǎn)。 若要刪除結(jié)點(diǎn)左右孩子都有，則將孩子結(jié)點(diǎn)的左孩子作為頭結(jié)點(diǎn)，將孩子結(jié)點(diǎn)的右子樹插入

16、孩子結(jié)點(diǎn)的左子樹的最右下結(jié)點(diǎn)的右子樹。 算法實(shí)現(xiàn)： 􀈎只列出要刪除結(jié)點(diǎn)是父結(jié)點(diǎn)的左子樹的情況.要刪除結(jié)點(diǎn)無左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;要刪除結(jié)點(diǎn)有左無右pre->lchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->

17、rchild=child->rchild;要刪除結(jié)點(diǎn)有右無左pre->lchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;要刪除結(jié)點(diǎn)左右都有.pre->lchild=child->lchild;s=child->rchild;wh

18、ile(s->lchild)s=s->lchild;s->lchild=child->lchild->rchild; /把要刪除結(jié)點(diǎn)的左孩子的右子樹接到孩子右子樹的最左下結(jié)點(diǎn)if(child->lchild->rtag!=1)s->ltag=0;q=child->lchild;while(q->rchild)q=q->rchild;q->rchild=s;child->lchild->rchild=child->rchild;child->lchild->rtag=0;四、運(yùn)行結(jié)果和調(diào)試分析輸

19、入數(shù)據(jù)，中序建立二叉樹。選擇1，中序輸出二叉樹。選擇2，進(jìn)行二叉樹的線索化。選擇5可以查看線索化后的二叉樹。選擇一個要插入的結(jié)點(diǎn)信息，輸入要查找的結(jié)點(diǎn)信息。輸入5可輸出進(jìn)行插入操作之后的線索二叉樹。選擇刪除操作，輸入要刪除的結(jié)點(diǎn)信息，發(fā)現(xiàn)結(jié)點(diǎn)后輸出結(jié)點(diǎn)信息，刪除結(jié)點(diǎn)操作成功。 五、總結(jié)體會 此次課程設(shè)計(jì)讓我充分學(xué)習(xí)了一個程序的開發(fā)過程。代碼的編寫是一個枯燥的過程，但是其中不乏很多挑戰(zhàn)，一個好的程序不僅是要能完成一個特定的任務(wù)，更重要的是要能高效的完成任務(wù)。 編寫完程序之后，大部分的時間就是在對程序進(jìn)行測試，可想而知，編代碼的時間很短，耗費(fèi)時間的是測試階段，因?yàn)樵谶@個過程中我發(fā)現(xiàn)了很多的問題，再

20、針對這些出現(xiàn)的問題，進(jìn)行修改，是程序具有一個合理的結(jié)構(gòu)，良好的可讀性和用戶友好性。 當(dāng)然在整個過程中，也有很多的問題是我無法解決的，在這個時候我會求助于我的同學(xué)，他們都很樂意給予我?guī)椭瑢ξ姨岢龅膯栴}進(jìn)行耐心個的分析，在這個過程中問題不僅解決了，我寫學(xué)習(xí)了同學(xué)的思想，他們對解決問題的方法。 此次課程設(shè)計(jì)還讓我感覺到，解決問題時的思想很重要，因?yàn)樗枷霙Q定著你程序的走向，我解決問題的方法，可以說，學(xué)習(xí)程序設(shè)計(jì)，思想是很重要的。有一個好的思想，會對程序有很大的幫助。 參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民編著數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社。源代碼：#include "stdio.h"#in

21、clude "malloc.h"#define maxsize 20 /規(guī)定樹中結(jié)點(diǎn)的最大數(shù)目#include"windows.h"typedef struct node /定義數(shù)據(jù)結(jié)構(gòu)int ltag,rtag; /表示child 域指示該結(jié)點(diǎn)是否孩子char data; /記錄結(jié)點(diǎn)的數(shù)據(jù)struct node *lchild,*rchild; /記錄左右孩子的指針Bithptr;Bithptr *Qmaxsize; /建隊(duì)，保存已輸入的結(jié)點(diǎn)的地址Bithptr *CreatTree() /建樹函數(shù)，返回根指針char ch;int front,rea

22、r;Bithptr *T,*s;T=NULL;front=1;rear=0; /置空二叉樹printf(" *n");printf(" * *n");printf(" * 線索二叉樹的運(yùn)算。 *n");printf(" * *n");printf(" *n");printf(" 請依次輸入數(shù)據(jù)表示空結(jié)點(diǎn)，以#結(jié)束n");ch=getchar(); /輸入第一個字符while(ch!='#') /判斷是否為結(jié)束字符s=NULL;if(ch!=''

23、) /判斷是否為空結(jié)點(diǎn)s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;rear+;Qrear=s; /將結(jié)點(diǎn)地址加入隊(duì)列中if(rear=1)T=s; /輸入為第一個結(jié)點(diǎn)為根結(jié)點(diǎn)elseif(s!=NULL&&Qfront!=NULL) /孩子和雙親結(jié)點(diǎn)均不是虛結(jié)點(diǎn)if(rear%2=0)Qfront->lchild=s;else Qfront->rchild=s;if(rear%2=1)fr

24、ont+;ch=getchar();return T;void Inorder(Bithptr *T) /中序遍歷if(T)if(T->ltag!=1)Inorder(T->lchild);printf("%c",T->data);if(T->rtag!=1)Inorder(T->rchild);Bithptr *pre=NULL;void PreThread(Bithptr *root) /中序線索化算法?函數(shù)實(shí)現(xiàn)Bithptr *p;p=root;if(p)PreThread(p->lchild);/線索化左子樹if(pre&

25、&pre->rtag=1)pre->rchild=p; /前驅(qū)結(jié)點(diǎn)后繼線索化if(p->lchild=NULL)p->ltag=1;p->lchild=pre;if(p->rchild=NULL) /后繼結(jié)點(diǎn)前驅(qū)線索化p->rtag=1;pre=p;PreThread(p->rchild);void PrintIndex(Bithptr *t) /輸出線索Bithptr *f;f=t;if(f)if(f->ltag=1&&f->lchild=NULL&&f->rtag=1) printf(

26、" 【%c 】",f->data);/如果是第一個結(jié)點(diǎn)if(f->ltag=1&&f->lchild!=NULL) printf("%c 【%c 】",f->lchild->data,f->data); /如果此結(jié)點(diǎn)有前驅(qū)就輸出前驅(qū)和此結(jié)點(diǎn)if(f->ltag=1&&f->rtag=1&&f->rchild!=NULL)printf("%c",f->rchild->data); /如果此結(jié)點(diǎn)有前驅(qū)也有后繼?就輸出后繼els

27、e if(f->rtag=1&&f->rchild!=NULL) printf(" 【%c 】%c",f->data,f->rchild->data);/如果沒有前驅(qū)?就輸出此結(jié)點(diǎn)和后繼printf("n");if(f->ltag!=1)PrintIndex(f->lchild);if(f->rtag!=1)PrintIndex(f->rchild);Bithptr *SearchChild(Bithptr *point,char findnode) /查找孩子結(jié)點(diǎn)函數(shù)Bithptr

28、*point1,*point2;if(point!=NULL)if(point->data=findnode) return point;elseif(point->ltag!=1) point1=SearchChild(point->lchild,findnode);if(point1!=NULL)return point1;if(point->rtag!=1) point2=SearchChild(point->rchild,findnode);if(point2!=NULL)return point2;return NULL;elsereturn NULL;

29、Bithptr *SearchPre(Bithptr *point,Bithptr *child) /查找父親結(jié)點(diǎn)函數(shù)Bithptr *point1,*point2;if(point!=NULL)if(point->ltag!=1&&point->lchild=child)|(point->rtag!=1&&point->rchild=child)return point;/找到則返回elseif(point->ltag!=1)point1=SearchPre(point->lchild,child);if(point1!=N

30、ULL)return point1;if(point->rtag!=1)point2=SearchPre(point->rchild,child);if(point2!=NULL)return point2;return NULL;elsereturn NULL;void Insert(Bithptr *root)char ch;char c;Bithptr *p1,*child,*p2;printf("請輸入要插入的結(jié)點(diǎn)的信息:");scanf("%c",&c);scanf("%c",&c);p1=(Bi

31、thptr *)malloc(sizeof(Bithptr); /插入的結(jié)點(diǎn)信息p1->data=c;p1->lchild=NULL;p1->rchild=NULL;p1->rtag=0;p1->ltag=0;printf("輸入查找的結(jié)點(diǎn)信息:");scanf("%c",&ch);scanf("%c",&ch);child=SearchChild(root,ch); /查孩子結(jié)點(diǎn)的地址if(child=NULL)printf("沒有找到結(jié)點(diǎn)n");return ;el

32、se printf("發(fā)現(xiàn)結(jié)點(diǎn)%cn",child->data);if(child->ltag=0) /當(dāng)孩子結(jié)點(diǎn)有左孩子的時候p2=child;child=child->lchild;while(child->rchild&&child->rtag=0) /找到左子樹下?最右結(jié)點(diǎn)child=child->rchild;p1->rchild=child->rchild; /后繼化p1->rtag=1;child->rtag=0;child->rchild=p1; /連接p1->lchil

33、d=child; /前驅(qū)化p1->ltag=1;else /當(dāng)孩子結(jié)點(diǎn)沒有左孩子的時候p1->lchild=child->lchild; /前驅(qū)化child->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=child;p1->rtag=1;printf("nt 插入結(jié)點(diǎn)操作已經(jīng)完成?并同時完成了線索化的恢復(fù)n");Bithptr * DeleteNode(Bithptr *t)Bithptr *child,*pre,*s,*q;char ch;printf("輸入查找的結(jié)

34、點(diǎn)信息:");ch=getchar();ch=getchar();child=SearchChild(t,ch); /查找該結(jié)點(diǎn)的孩子結(jié)點(diǎn)printf("發(fā)現(xiàn)結(jié)點(diǎn):%cn",child->data);printf("ltag=%d,rtag=%dn",child->ltag,child->rtag);if(NULL=child)printf("沒有找到結(jié)點(diǎn):");return t;if(child!=t)pre=SearchPre(t,child);printf("發(fā)現(xiàn)結(jié)點(diǎn):%cn",p

35、re->data);else/當(dāng)是頭結(jié)點(diǎn)的時候if(child->ltag=1&&child->rtag=1) /沒有左右孩子t=NULL;else if(t->ltag=1&&t->rtag!=1) /有右孩子沒有左孩子t=child->rchild;child->rchild->lchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag=1) /有左孩子沒有右孩子t=child->lchild;child->lc

36、hild->rchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag!=1) /有左孩子也有右孩子t=child->lchild;s=child->lchild;while(s->rchild&&s->rtag!=1) /查找孩子左子樹的最右下結(jié)點(diǎn)s=s->rchild;q=child->rchild;while(q->lchild&&q->ltag!=1) /查找孩子右子樹的最左下結(jié)點(diǎn)q=q->lchild;s-

37、>rchild=child->rchild; /連接s->rtag=0;q->lchild=s;free(child);return t;if(child=pre->lchild|child=pre)/是父親結(jié)點(diǎn)的左孩子if(1=child->ltag&&1=child->rtag)/孩子結(jié)點(diǎn)無左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild-

38、>rchild=pre;free(child);else if(1!=child->ltag&&1=child->rtag)/孩子結(jié)點(diǎn)有左無右pre->lchild=child->lchild;s=child->lchild;while(s->rchild) /查找左子樹的最右下結(jié)點(diǎn)s=s->rchild;s->rchild=child->rchild;free(child);else if(1=child->ltag&&1!=child->rtag)/孩子結(jié)點(diǎn)有右無左pre->lch

39、ild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;free(child);else if(1!=child->ltag&&1!=child->rtag)/孩子結(jié)點(diǎn)左右都有pre->lchild=child->lchild;s

40、=child->rchild;while(s->lchild&&s->ltag!=1) /找到右子樹的最左下結(jié)點(diǎn)s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1) /找到左子樹下最右下結(jié)點(diǎn)q=q->rchild;q->rchild=child->rchild; /將孩子結(jié)點(diǎn)的右子樹接到左子樹下最右下結(jié)點(diǎn)q->rtag=0;s->lchild=q;free(child);else if(child=pre->rchild)/是

41、父親結(jié)點(diǎn)的右孩子if(1=child->ltag&&1=child->rtag)/孩子結(jié)點(diǎn)無左右pre->rchild=child->rchild;pre->rtag=1;if(child->rchild!=NULL)if(child->rchild->ltag=1)child->rchild->lchild=pre;free(child);else if(1!=child->ltag&&1=child->rtag)/孩子結(jié)點(diǎn)有左無右pre->rchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=child->rchild;if(child->rchild!=NULL