線索二叉樹(shù)的運(yùn)算-數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2009 2010 學(xué)年第 二 學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱線索二叉樹(shù)的運(yùn)算學(xué)生姓名侯山虎學(xué)號(hào)0804012006專業(yè)班級(jí)08計(jì)本（2）班指導(dǎo)教師王昆侖 張貫虹2010 年 6 月一、問(wèn)題分析和任務(wù)定義（1）題目：線索二叉樹(shù)運(yùn)算:線索二叉樹(shù)的應(yīng)用，實(shí)現(xiàn)線索二叉樹(shù)的建立、插入、刪除、恢復(fù)線索。（2）任務(wù)定義： 此題目是線索二叉樹(shù)的一系列操作問(wèn)題。首先就要明白線索二叉樹(shù)是什么，利用二叉鏈表的空指針域?qū)⒖盏淖蠛⒆又羔樣蚋臑橹赶蚱淝膀?qū)，空的右孩子指針域改為指向其后繼，這種改變指向的指針?lè)Q為線索，加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)。

2、（3）分析:該任務(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ì)于具體的二叉樹(shù)應(yīng)該使初使用者明白輸入的格式。2，該程序重點(diǎn)內(nèi)容是有關(guān)于線索二叉樹(shù)的插入和刪除，在進(jìn)行具體的操作時(shí)，規(guī)則是什么，依照什么原則。3，在線索恢復(fù)中，依照插入刪除后的二叉樹(shù)結(jié)構(gòu)，應(yīng)該如何設(shè)計(jì)，是單獨(dú)恢復(fù)，還是在兩個(gè)重點(diǎn)程序中直接恢復(fù)線索。4，對(duì)于插入，刪除，恢復(fù)線索等，其結(jié)果是否符合預(yù)定的目標(biāo)，須由自己判定。由此，可以給出初步的分析： A。依照書(shū)上的相關(guān)內(nèi)容和二叉

3、樹(shù)的定義，線索二叉樹(shù)應(yīng)該是在二叉樹(shù)依照一定格式輸入完畢后，對(duì)其進(jìn)行線索化，線索化初步選定為中序線索化，然后線索化的結(jié)果進(jìn)行輸出。B、插入中，首先就要考慮要怎樣在二叉樹(shù)中插入結(jié)點(diǎn)。要插入結(jié)點(diǎn)，那么首先就應(yīng)該考慮要在那里插入結(jié)點(diǎn)，那么就引入了結(jié)點(diǎn)的查找問(wèn)題。結(jié)點(diǎn)的查找將建立一個(gè)獨(dú)立的子函數(shù)。找到了結(jié)點(diǎn)的位置以后，由于目標(biāo)節(jié)點(diǎn)有左右子樹(shù)，設(shè)計(jì)兩種情況，選擇后就要考慮怎么插入了。若選擇了左子樹(shù)后，目標(biāo)節(jié)點(diǎn)又有兩種情況：一是已經(jīng)有左子樹(shù)，二是沒(méi)有左子樹(shù)，此時(shí)根據(jù)相應(yīng)的情況，設(shè)計(jì)正確的操作。 在刪除中也有類似的操作，不同的是在刪除的過(guò)程中，因?yàn)橐紤]被刪除結(jié)點(diǎn)的左右子樹(shù)的連接問(wèn)題，必須知道要查找結(jié)點(diǎn)的父親

4、結(jié)點(diǎn)。那么就需要另外一個(gè)子函數(shù)來(lái)查找孩子結(jié)點(diǎn)的父親結(jié)點(diǎn)。被刪除結(jié)點(diǎn)和其父親結(jié)點(diǎn)確定以后，就要考慮刪除過(guò)程中的各種情況。C、恢復(fù)線索過(guò)程中，由于和插入刪除操作分離后考慮的過(guò)程復(fù)雜，并且從設(shè)計(jì)的目標(biāo)來(lái)說(shuō)應(yīng)該是要在刪除和插入的過(guò)程中實(shí)現(xiàn)對(duì)線索的恢復(fù)，故選擇了插入刪除中直接恢復(fù)線索。D、在輸出中，輸出的操作分為兩個(gè)一是專門(mén)用于二叉樹(shù)的輸出判別是否是要線索化的二叉樹(shù)，此時(shí)用中序輸出來(lái)體現(xiàn)二叉樹(shù)的結(jié)點(diǎn)情況。二是以輸出線索來(lái)觀察在各種操作的過(guò)程中線索的變化情況。（4）測(cè)試用例： 其中為虛節(jié)點(diǎn)，#為結(jié)束標(biāo)記：1.輸入數(shù)據(jù)：abcd# 完全二叉樹(shù) 插入結(jié)點(diǎn)為信息為 t； 插入的位置在點(diǎn)：c 刪除結(jié)點(diǎn)為 t； 插

5、入刪除完成后得： 線索輸出得：b-d-a-c- 2.輸入數(shù)據(jù)：abcdef# 插入結(jié)點(diǎn)為r ; 插入的位置在b點(diǎn)，沒(méi)有左孩子的情況 刪除結(jié)點(diǎn)為 d; 插入刪除完成后得： 線索輸出得：b-r-a-c- 二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)（1）數(shù)據(jù)結(jié)構(gòu)的選擇：因?yàn)榇顺绦蚓褪菍?duì)二叉樹(shù)進(jìn)行各種操作，所以程序中必然使用的是樹(shù)形結(jié)構(gòu)。在將樹(shù)存儲(chǔ)到計(jì)算機(jī)中時(shí)，就有了為存樹(shù)而使用的存儲(chǔ)結(jié)構(gòu)。因?yàn)閷?duì)線索有大量的操作，所以選擇鏈接存儲(chǔ)結(jié)構(gòu)。在存儲(chǔ)的過(guò)程中還使用了隊(duì)類型的數(shù)據(jù)結(jié)構(gòu)。隊(duì)的定義為：BItree *Qmaxlen; /存放建樹(shù)過(guò)程中的每個(gè)結(jié)點(diǎn)的指針樹(shù)的結(jié)點(diǎn)類型定義為： Typedef struct node I

6、nt ltag , rtag; /用來(lái)指示指針域指的為孩子還是前驅(qū)或后繼 char data; /存放結(jié)點(diǎn)信息 struct node *lchild , *rchild; /記錄孩子結(jié)點(diǎn)信息 Bithptr;結(jié)構(gòu)圖如圖1為：ltag data rtaglchild rchild 圖1結(jié)構(gòu)圖二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)如圖2:圖2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)選擇原因：要存儲(chǔ)樹(shù)在計(jì)算機(jī)中，為了使用鏈接存儲(chǔ)結(jié)構(gòu)，就要對(duì)結(jié)點(diǎn)進(jìn)行設(shè)計(jì)。要存儲(chǔ)結(jié)點(diǎn)信息就要有data域來(lái)存儲(chǔ)信息，并分別設(shè)有左右孩子指針域分別記錄此結(jié)點(diǎn)的左右孩子指針，使在建樹(shù)的過(guò)程中每個(gè)結(jié)點(diǎn)的左右孩子指針指向其左右孩子，實(shí)現(xiàn)整個(gè)二叉樹(shù)的建立。這樣的存儲(chǔ)結(jié)構(gòu)對(duì)

7、于二叉樹(shù)的存儲(chǔ)已經(jīng)足夠，但是此程序處理的是線索二叉樹(shù)。在存儲(chǔ)上就要為結(jié)點(diǎn)加上標(biāo)志域，分別用來(lái)指示其指針是指向孩子還是前驅(qū)或后繼。當(dāng)tag標(biāo)志為0時(shí)，表示指針指向的是該結(jié)點(diǎn)的左右孩子，當(dāng)tag標(biāo)志為1時(shí)，表示指向的是該結(jié)點(diǎn)的前驅(qū)或后繼。 概要設(shè)計(jì)：在程序中設(shè)計(jì)有完成各種功能的函數(shù)。二叉樹(shù)的建立函數(shù)：BiThrNode *creat(BiThrNode *T)中序遍歷函數(shù)： void inorder(BiThrNode *T)中序線索化函數(shù)： void PreThread(BiThrNode *root)輸出線索函數(shù)： void Inorder(BiThrNode *T)查找孩子指針函數(shù)：BiTh

8、rNode *SearchChild(BiThrNode *T,char key_name)查找父親指針函數(shù)：BiThrNode *SearchPre(BiThrNode *T,BiThrNode *key)插入函數(shù)： void Insert(BiThrNode *root)刪除函數(shù)： BiThrNode *Delete(BiThrNode *t)主函數(shù)： void main(); （4）主要算法和結(jié)構(gòu)流程圖：程序的模塊結(jié)構(gòu)如圖3插入函數(shù)查找孩子指針函數(shù)查找父親指針函數(shù)二叉樹(shù)的建立函數(shù)中序遍歷函數(shù)中序線索化函數(shù)刪除函數(shù)輸出線索函數(shù)退出 結(jié)束輸出頭指針圖4：開(kāi)始建隊(duì)并置空 、輸入結(jié)點(diǎn)數(shù)據(jù) 判斷是

9、否為結(jié)束 Y輸出頭指針 N 判斷是否為空 N Y建立結(jié)點(diǎn)結(jié)束 加入隊(duì)中 是否為頭結(jié)點(diǎn) Y N節(jié)點(diǎn)是否為空 Y連接給對(duì)頭 N將節(jié)點(diǎn)給左右子樹(shù) 是否為右孩子 N隊(duì)頭指針加一 Y 圖4樹(shù)的建立函數(shù)如圖 是否找到此點(diǎn)查找插入點(diǎn)結(jié)點(diǎn)指針插入函數(shù)流程圖如圖 5：開(kāi)始輸入要插入點(diǎn)信息 查找插入點(diǎn)結(jié)點(diǎn)指針結(jié)點(diǎn)是否有左子樹(shù)結(jié)點(diǎn) Y1 Y2 直接插入為此結(jié)點(diǎn)的右結(jié)點(diǎn)恢復(fù)線索1直接插入為此結(jié)點(diǎn)的左結(jié)點(diǎn)恢復(fù)線索2結(jié)束圖5插入函數(shù)流程圖如圖輸入刪除結(jié)點(diǎn)信息開(kāi)始刪除函數(shù)流程圖如圖6查找結(jié)點(diǎn)信息查找父親結(jié)點(diǎn) 是否為父結(jié)點(diǎn)左孩子 Y N左右孩子都有有左孩子沒(méi)右孩子有右孩子沒(méi)左孩子沒(méi)有左右孩 把右子樹(shù)接到左子樹(shù)的最右下結(jié)點(diǎn)的右

10、子樹(shù)左右孩子都有有左孩子沒(méi)右孩子沒(méi)有左右孩子有右孩子沒(méi)左孩子把左孩子作為頭結(jié)點(diǎn)把右孩子作為頭結(jié)點(diǎn)直接刪除結(jié)點(diǎn)右子樹(shù)接為左子樹(shù)的最右下結(jié)點(diǎn)的右子樹(shù)把左孩子作為父結(jié)點(diǎn)左孩子直接刪除把右孩子作為父結(jié)點(diǎn)左孩子 恢復(fù)線索結(jié)束圖6刪除函數(shù)流程圖三、詳細(xì)設(shè)計(jì)和編碼(1) 創(chuàng)建二叉樹(shù)：1、分析：建立一個(gè)二叉鏈表，需要按照某種順序依次輸入二叉樹(shù)中的結(jié)點(diǎn)，且該輸入順序必須隱含結(jié)點(diǎn)間的邏輯結(jié)構(gòu)的信息。這個(gè)建立依照層次關(guān)系由上往下，由左往右 。以表示空結(jié)點(diǎn)，以#表示結(jié)束的標(biāo)志 。2、實(shí)現(xiàn)：在函數(shù)中設(shè)置一隊(duì)列，該隊(duì)列是一個(gè)指針類型的數(shù)組，保存已輸入的結(jié)點(diǎn)的地址。使隊(duì)頭指針front指向當(dāng)前需要與孩子建立鏈接的父親結(jié)點(diǎn)，

11、隊(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)，則無(wú)需鏈接。若父結(jié)點(diǎn)與其兩個(gè)孩子結(jié)點(diǎn)鏈接完畢，則使front指向下一個(gè)等待鏈接的父結(jié)點(diǎn)。4、主要過(guò)程： BiThrNode *qmaxlen;BiThrNode *creat(BiThrNode *T)/創(chuàng)建二叉樹(shù)char ch; int front=1,rear=0; BiThrNode *s; T=NULL; ch=getchar(); while(ch!=#)/當(dāng)沒(méi)有結(jié)束輸入時(shí) s=NULL; if(ch!=) s=(BiThrNode *)m

12、alloc(sizeof(BiThrNode); s-data=ch; s-ltag=0;s-rtag=0;/先置0，在線索化中重新設(shè)置 s-lchild=NULL; s-rchild=NULL; rear+; qrear=s; if(rear=1) T=qrear; else if(s!=NULL&qfront!=NULL) if(rear%2=0) /根從1開(kāi)始，當(dāng)為2的倍數(shù)時(shí)，為左子樹(shù) qfront-lchild=s; else /余1時(shí)，為右子樹(shù) qfront-rchild=s; if(rear%2=1)/右子樹(shù)已輸入完畢，父親節(jié)點(diǎn)往下移 front+; ch=getchar(); r

13、eturn T;5、建樹(shù)圖示如圖7： 0 1 2 3 4 5 6 圖7建樹(shù)圖示(2)二叉樹(shù)線索化：1、分析：線索過(guò)程必須要按照一定的順序來(lái)進(jìn)行。2、實(shí)現(xiàn)：要實(shí)現(xiàn)線索化，就要知道結(jié)點(diǎn)*pre是結(jié)點(diǎn)*p的前驅(qū)，而*p是*pre的后繼。這樣，當(dāng)遍歷到結(jié)點(diǎn)*p時(shí)，可以進(jìn)行，若*p有空指針域，則將相應(yīng)的標(biāo)志置1；若*p的左線索標(biāo)志已經(jīng)建立（p-ltag=1），則可使其前驅(qū)線索化,令p-lchild=pre；若*pre的左線索標(biāo)志已經(jīng)建立（pre-rtag=1），則可使其后繼線索化，令pre-rchild=p;3.具體實(shí)現(xiàn)：BiThrNode *pre=NULL;void PreThread(BiThrN

14、ode *root) /中序線索化算法，函數(shù)實(shí)現(xiàn) BiThrNode *p; p=root; if(p) PreThread(p-lchild); /線索化左子樹(shù) if(pre&pre-rtag=1) /前驅(qū)結(jié)點(diǎn)后繼線索化pre-rchild=p; 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); (3)二叉樹(shù)中插入結(jié)點(diǎn)1、方法：在樹(shù)中插入一個(gè)結(jié)點(diǎn)，就必須要以一定的規(guī)則來(lái)進(jìn)行插入。找到要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)，然后選擇是左孩子是右孩

15、子插入，在看要插入的位置是否已經(jīng)有其他節(jié)點(diǎn)，若有節(jié)點(diǎn)，則將要插入的結(jié)點(diǎn)作為該結(jié)點(diǎn)的前驅(qū)插入樹(shù)中。若沒(méi)有，則直接插入。 2、查找：在查找中，由于采用非遞歸形式會(huì)引入棧的操作，其麻煩程度有所不值，故依照中序線索輸出，可以得到線索化后可以用的查找功能。 3、查找函數(shù)實(shí)現(xiàn)：BiThrNode *SearchChild(BiThrNode *T,char key_name) /查找孩子結(jié)點(diǎn)函數(shù) BiThrNode *p,*q; if(T!=NULL) if(T-data=key_name) /找到時(shí)，直接返回 return T; else if(T-ltag!=1) /左孩子不為空，進(jìn)入遞歸 p=Sea

16、rchChild(T-lchild,key_name); if(p!=NULL) return p;if(T-rtag!=1) /右孩子不為空,進(jìn)入遞歸 q=SearchChild(T-rchild,key_name); if(q!=NULL) return q; return NULL; else return NULL;4、插入方法：在一棵樹(shù)中插入一個(gè)結(jié)點(diǎn)，因?yàn)椴迦氲奈恢貌煌?，就?duì)應(yīng)著不同的插入情況。通過(guò)分析總結(jié)出各種情況： 插入結(jié)點(diǎn)有左(右)孩子：直接將節(jié)點(diǎn)插入到目標(biāo)位置，若該位置已有節(jié)點(diǎn)，則插入節(jié)點(diǎn)作為已有節(jié)點(diǎn)的父親節(jié)點(diǎn)，若沒(méi)有，直接插入，同時(shí)，對(duì)插入后的二叉樹(shù)進(jìn)行線索化。5、具體實(shí)現(xiàn)

17、：void Insert2(BiThrNode *p,BiThrNode *r) /右孩子插入BiThrNode *s; if(p-rtag=0) /當(dāng)目標(biāo)結(jié)點(diǎn)有右孩子的時(shí)候 s=p-rchild; /保存右孩子，設(shè)置r的后繼 r-rchild=s; /后繼化 r-rtag=0; r-ltag=1; r-lchild=p; /連接 p-rchild=r; /前驅(qū)化 s-lchild=r; else /當(dāng)目標(biāo)結(jié)點(diǎn)沒(méi)有右孩子的時(shí)候 r-rchild=p-rchild; /前驅(qū)化 r-rtag=1; p-rchild=r; p-rtag=0; r-lchild=p; r-ltag=1; printf

18、(插入結(jié)點(diǎn)操作已經(jīng)完成，并同時(shí)完成了線索化的恢復(fù)n);void Insert1(BiThrNode *p,BiThrNode *r) /左孩子插入BiThrNode *s; if(p-ltag=0) /當(dāng)目標(biāo)結(jié)點(diǎn)有左孩子的時(shí)候,接到左孩子最右下端 s=p-lchild; r-lchild=s; /前驅(qū)化 r-ltag=0; r-rchild=p; /后繼化 r-rtag=1; p-lchild=r; s-rchild=r; else /當(dāng)目標(biāo)結(jié)點(diǎn)沒(méi)有左孩子的時(shí)候，直接接入 r-lchild=p-lchild; /前驅(qū)化 r-ltag=1; p-lchild=r; p-ltag=0; r-rch

19、ild=p; r-rtag=1; printf(插入結(jié)點(diǎn)操作已經(jīng)完成，并同時(shí)完成了線索化的恢復(fù)n); 6、圖形顯示：如插入abcd# 中序?yàn)?a-b-c-d- 插入的結(jié)點(diǎn)為：g 要插入的位置為：d 建樹(shù)后，結(jié)點(diǎn)的線索變化如圖8和圖9；其中虛線為待插結(jié)點(diǎn)在插入過(guò)程中將要變化的線索 a g dvvv c b 待插入元素 d圖8結(jié)點(diǎn)的線索變化(1) 則插入結(jié)點(diǎn)后的順序?yàn)椋篵-g-d-a-c- a c b g d圖9結(jié)點(diǎn)的線索變化(2)(4) 刪除結(jié)點(diǎn)函數(shù) 1、分析：要在函數(shù)中刪除一個(gè)結(jié)點(diǎn)，也要考慮各種不同的情況。在刪除結(jié)點(diǎn)之前也要先找到要?jiǎng)h除的點(diǎn)，就調(diào)用查找孩子結(jié)點(diǎn)函數(shù)BiThrNode *Sear

20、chChild(BiThrNode *T,char key_name)找到其結(jié)點(diǎn)的指針。再后面的操作就是怎樣刪除了，就發(fā)現(xiàn)在刪除過(guò)程中涉及的指針變換需要父親結(jié)點(diǎn)的指針，所以就調(diào)用查找父親結(jié)點(diǎn)BiThrNode *SearchPre(BiThrNode *T,BiThrNode *key)來(lái)查找該結(jié)點(diǎn)的父親結(jié)點(diǎn)指針。 2、刪除具體情況： 1).當(dāng)結(jié)點(diǎn)是父親結(jié)點(diǎn)的左孩子時(shí) 1.若孩子結(jié)點(diǎn)沒(méi)有左右孩子：則直接刪除； 2.若孩子結(jié)點(diǎn)有左孩子沒(méi)右孩子：則將孩子結(jié)點(diǎn)的左孩子給父親結(jié)點(diǎn)的左孩子； 3.若孩子結(jié)點(diǎn)有右孩子沒(méi)左孩子：則將孩子結(jié)點(diǎn)的右孩子給父親結(jié)點(diǎn)的左孩子； 4.若孩子結(jié)點(diǎn)左右孩子都有：將左孩子上

21、提，孩子結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)接到孩子結(jié)點(diǎn)的右子樹(shù)的最左下結(jié)點(diǎn)的左子樹(shù)，再將孩子結(jié)點(diǎn)的右子樹(shù)接到孩子結(jié)點(diǎn)左子樹(shù)的右子樹(shù)。2).當(dāng)結(jié)點(diǎn)是父親結(jié)點(diǎn)的右孩子: 1若孩子結(jié)點(diǎn)沒(méi)有左右孩子：則直接刪除； 2.若孩子結(jié)點(diǎn)有左孩子沒(méi)右孩子：則將孩子結(jié)點(diǎn)的左孩子給父親結(jié)點(diǎn)的右孩子； 3.若孩子結(jié)點(diǎn)有右孩子沒(méi)左孩子：則將孩子結(jié)點(diǎn)的右孩子給父親結(jié)點(diǎn)的右孩子； 4.若孩子結(jié)點(diǎn)左右孩子都有：將右孩子上提，將孩子結(jié)點(diǎn)的右子樹(shù)的左子樹(shù)接到孩子結(jié)點(diǎn)的左子樹(shù)的最右下結(jié)點(diǎn)的右子樹(shù)，再將孩子結(jié)點(diǎn)的左子樹(shù)接到孩子結(jié)點(diǎn)右子樹(shù)的左子樹(shù)。 3、具體實(shí)現(xiàn)：（只列出孩子結(jié)點(diǎn)是父結(jié)點(diǎn)的左子樹(shù)的情況） 孩子結(jié)點(diǎn)無(wú)左右 if(child=pre-l

22、child|child=pre) /是父親結(jié)點(diǎn)的左孩子 if(child-ltag=1&child-rtag=1) /孩子結(jié)點(diǎn)無(wú)左右 pre-lchild=child-lchild; /child結(jié)點(diǎn)后繼指向pre,只要保存前驅(qū) pre-ltag=1; /原來(lái)是0 free(child); else if(child-ltag!=1&child-rtag=1)/孩子結(jié)點(diǎn)有左無(wú)右 pre-lchild=child-lchild; /把child左孩子上提 s=child-lchild; /查找child左孩子的最右下端節(jié)點(diǎn)(往下) while(s-rchild) /該節(jié)點(diǎn)是child的前驅(qū)，保存

23、child后繼 s=s-rchild; s-rchild=child-rchild; /保存child后繼，s右標(biāo)為1 free(child); else if(child-ltag=1&child-rtag!=1)/孩子結(jié)點(diǎn)有右無(wú)左 pre-lchild=child-rchild; /把右孩子上提 s=child-rchild; /查找child的后繼節(jié)點(diǎn)，位置在右孩子的最左下端 while(s-lchild!=NULL) s=s-lchild; s-lchild=child-lchild; /把child前驅(qū)給s保存,s左標(biāo)為1 free(child); else if(child-lta

24、g!=1&child-rtag!=1)/孩子結(jié)點(diǎn)左右都有 pre-lchild=child-lchild; /child左孩子上提到child位置 s=child-rchild; /child左孩子的右子樹(shù)會(huì)與child右子樹(shù)沖突 while(s-lchild) s=s-lchild; s-lchild=child-lchild-rchild;/若child-lchild右子樹(shù)非空,把child的左孩子的右子樹(shù)接到孩子 /右子樹(shù)的最左下結(jié)點(diǎn) if(child-lchild-rtag!=1) /child-lchild右子樹(shù)非空，此時(shí)s-ltag本為1 s-ltag=0; q=child-lch

25、ild; while(q-rchild!=NULL) q=q-rchild; q-rchild=s; /把q的后繼指到s上 child-lchild-rchild=child-rchild;/child左孩子的右子樹(shù)設(shè)置 child-lchild-rtag=0; /原本不知是否為0，但可以一起考慮 free(child); 4、圖形顯示如圖10和圖11：如刪除結(jié)點(diǎn)g 中序?yàn)? bgdac 刪除后: bdac c b a g d圖10圖形顯示刪除結(jié)點(diǎn)g圖11圖形顯示刪除結(jié)點(diǎn)b四上機(jī)調(diào)試在調(diào)試時(shí)，按照原有的思路，查找二叉樹(shù)中目標(biāo)節(jié)點(diǎn)，用的是出棧和入棧相關(guān)操作，但是在具體設(shè)計(jì)時(shí)，遇到的問(wèn)題有點(diǎn)復(fù)雜，

26、結(jié)果是在循環(huán)時(shí)找到了問(wèn)題所在，由于本身思想的設(shè)計(jì)就有問(wèn)題，重新思考了一下，感覺(jué)比較麻煩，重新利用線索后二叉樹(shù)輸出函數(shù)改出遞歸遍歷，在插入刪除時(shí)，具體情況具體對(duì)待，分出不同的情況，插入刪除操作中，規(guī)則是咨詢了王教授，要求是自己設(shè)計(jì)，于是選擇了不改變線索為原則，和下面的恢復(fù)線索可以對(duì)照著完成，在完成時(shí)，由于設(shè)計(jì)好了情況與應(yīng)對(duì)操作，故總體上能夠完成，在細(xì)節(jié)時(shí)，參考了數(shù)據(jù)結(jié)構(gòu)-c語(yǔ)言描述.五、測(cè)試結(jié)果及分析程序運(yùn)行后1、建立線索二叉樹(shù)（見(jiàn)下圖）圖12建立線索二叉樹(shù)2、對(duì)線索二叉樹(shù)進(jìn)行插入操作（見(jiàn)下圖）圖13線索二叉樹(shù)的插入3、對(duì)線索二叉樹(shù)進(jìn)行刪除操作（見(jiàn)下圖）圖14線索二叉樹(shù)刪除操作分析：由以上結(jié)果均

27、符合預(yù)期的目標(biāo)，成功完成。六、用戶使用說(shuō)明本程序是在VC+ 6.0中編寫(xiě)，程序運(yùn)行環(huán)境：DOS根據(jù)程序的提示即可完成文本編輯器的各項(xiàng)功能。其中具體的操作可依照程序運(yùn)行時(shí)的說(shuō)明。七、參考文獻(xiàn)王昆侖、李紅。數(shù)據(jù)結(jié)構(gòu)與算法。北京：中國(guó)鐵道出版社。八、附錄#includestdio.h#includemalloc.h#includestdlib.h#define NULL 0#define maxlen 20typedef struct node char data; struct node *lchild, *rchild; /*左右孩子子樹(shù)*/ int ltag,rtag;BiThrNode; B

28、iThrNode *qmaxlen;BiThrNode *creat(BiThrNode *T)/創(chuàng)建二叉樹(shù)char ch; int front=1,rear=0; BiThrNode *s; T=NULL; ch=getchar(); while(ch!=#)/當(dāng)沒(méi)有結(jié)束輸入時(shí) s=NULL; if(ch!=) s=(BiThrNode *)malloc(sizeof(BiThrNode); s-data=ch; s-ltag=0;s-rtag=0;/先置0，在線索化中重新設(shè)置 s-lchild=NULL; s-rchild=NULL; rear+; qrear=s; if(rear=1)

29、T=qrear; else if(s!=NULL&qfront!=NULL) if(rear%2=0) /根從1開(kāi)始，當(dāng)為2的倍數(shù)時(shí)，為左子樹(shù) qfront-lchild=s; else /余1時(shí)，為右子樹(shù) qfront-rchild=s; if(rear%2=1)/右子樹(shù)已輸入完畢，父親節(jié)點(diǎn)往下移 front+; ch=getchar(); return T;void inorder(BiThrNode *T) /中遍歷，只能在線索化前使用 if(T!=NULL) inorder(T-lchild); printf(%c ,T-data); inorder(T-rchild); void I

30、norder(BiThrNode *T) /中序遍歷 if(T) if(T-ltag!=1) Inorder(T-lchild); printf(%c,T-data); if(T-rtag!=1) Inorder(T-rchild); BiThrNode *SearchPre(BiThrNode *T,BiThrNode *key)/查找父親結(jié)點(diǎn)函數(shù) BiThrNode *p,*q; if(T!=NULL) if(T-ltag!=1&T-lchild=key)|(T-rtag!=1&T-rchild=key) return T; /找到時(shí)返回point，非空量 else if(T-ltag!=

31、1) /進(jìn)入左孩子遞歸查找 p=SearchPre(T-lchild,key); if(p!=NULL) return p; else if(T-rtag!=1) /進(jìn)入右孩子遞歸查找 q=SearchPre(T-rchild,key); if(q!=NULL) return q; return NULL; /分為層次性,在if里面,若前面return執(zhí)行，則該句不執(zhí)行 else return NULL;BiThrNode *SearchChild(BiThrNode *T,char key_name) /查找孩子結(jié)點(diǎn)函數(shù) BiThrNode *p,*q; if(T!=NULL) if(T-d

32、ata=key_name) /找到時(shí)，直接返回 return T; else if(T-ltag!=1) /左孩子不為空，進(jìn)入遞歸 p=SearchChild(T-lchild,key_name); if(p!=NULL) return p; if(T-rtag!=1) /右孩子不為空,進(jìn)入遞歸 q=SearchChild(T-rchild,key_name); if(q!=NULL) return q; return NULL; else return NULL;void Insert2(BiThrNode *p,BiThrNode *r) /右孩子插入 BiThrNode *s; if(p

33、-rtag=0) /當(dāng)目標(biāo)結(jié)點(diǎn)有右孩子的時(shí)候 s=p-rchild; /保存右孩子，設(shè)置r的后繼 r-rchild=s; /后繼化 r-rtag=0; r-ltag=1; r-lchild=p; /連接 p-rchild=r; /前驅(qū)化 s-lchild=r; else /當(dāng)目標(biāo)結(jié)點(diǎn)沒(méi)有右孩子的時(shí)候 r-rchild=p-rchild; /前驅(qū)化 r-rtag=1; p-rchild=r; p-rtag=0; r-lchild=p; r-ltag=1; printf(插入結(jié)點(diǎn)操作已經(jīng)完成，并同時(shí)完成了線索化的恢復(fù)n);void Insert1(BiThrNode *p,BiThrNode *r

34、) /左孩子插入 BiThrNode *s; if(p-ltag=0) /當(dāng)目標(biāo)結(jié)點(diǎn)有左孩子的時(shí)候,接到左孩子最右下端 s=p-lchild; r-lchild=s; /前驅(qū)化 r-ltag=0; r-rchild=p; /后繼化 r-rtag=1; p-lchild=r; s-rchild=r; else /當(dāng)目標(biāo)結(jié)點(diǎn)沒(méi)有左孩子的時(shí)候，直接接入 r-lchild=p-lchild; /前驅(qū)化 r-ltag=1; p-lchild=r; p-ltag=0;r-rchild=p; r-rtag=1; printf(插入結(jié)點(diǎn)操作已經(jīng)完成，并同時(shí)完成了線索化的恢復(fù)n);void Insert(BiT

35、hrNode *root)int n; char ch,c; BiThrNode *r,*p; printf(請(qǐng)輸入要插入的結(jié)點(diǎn)的信息:); getchar(); scanf(%c,&c); r=(BiThrNode *)malloc(sizeof(BiThrNode); /插入的結(jié)點(diǎn)信息 r-data=c; r-lchild=NULL; r-rchild=NULL; r-rtag=0; r-ltag=0; printf(輸入查找的結(jié)點(diǎn)信息:); getchar(); scanf(%c,&ch); p=SearchChild(root,ch); /查孩子結(jié)點(diǎn)的地址 if(p=NULL) pri

36、ntf(沒(méi)有找到結(jié)點(diǎn)n); system(pause); return ; else printf(發(fā)現(xiàn)結(jié)點(diǎn)%cn,p-data); printf(請(qǐng)選擇:n); printf(1.左孩子插入n); printf(2.右孩子插入n); scanf(%d,&n); if(n=1) Insert1(p,r); if(n=2) Insert2(p,r); BiThrNode *Delete(BiThrNode *t) BiThrNode *child,*pre,*s,*q; char ch,i; printf(輸入查找的結(jié)點(diǎn)信息:); ch=getchar(); ch=getchar();child

37、=SearchChild(t,ch); if(child=NULL) printf(沒(méi)有找到該結(jié)點(diǎn)!); return t; printf(要?jiǎng)h除節(jié)點(diǎn)信息如下:%cn,child-data); printf(ltag=%d,rtag=%dn,child-ltag,child-rtag); pre=SearchPre(t,child); printf(該節(jié)點(diǎn)的父節(jié)點(diǎn)信息:%cn,pre-data); printf(確定刪除該節(jié)點(diǎn)么(y,n):); getchar(); scanf(%c,&i); if(i=n) return t; else if(child=pre-lchild|child=p

38、re) /是父親結(jié)點(diǎn)的左孩子 if(child-ltag=1&child-rtag=1) /孩子結(jié)點(diǎn)無(wú)左右 pre-lchild=child-lchild; /child結(jié)點(diǎn)后繼指向pre,只要保存前驅(qū) pre-ltag=1; /原來(lái)是0 free(child); else if(child-ltag!=1&child-rtag=1)/孩子結(jié)點(diǎn)有左無(wú)右 pre-lchild=child-lchild; /把child左孩子上提 s=child-lchild; /查找child左孩子的最右下端節(jié)點(diǎn)(往下) while(s-rchild) /該節(jié)點(diǎn)是child的前驅(qū)，保存child后繼 s=s-r

39、child; s-rchild=child-rchild; /保存child后繼，s右標(biāo)為1 free(child); else if(child-ltag=1&child-rtag!=1)/孩子結(jié)點(diǎn)有右無(wú)左 pre-lchild=child-rchild; /把右孩子上提 s=child-rchild; /查找child的后繼節(jié)點(diǎn)，位置在右孩子的最左下端 while(s-lchild!=NULL) s=s-lchild; s-lchild=child-lchild; /把child前驅(qū)給s保存,s左標(biāo)為1 free(child); else if(child-ltag!=1&child-rt

40、ag!=1)/孩子結(jié)點(diǎn)左右都有 pre-lchild=child-lchild; /child左孩子上提到child位置 s=child-rchild; /child左孩子的右子樹(shù)會(huì)與child右子樹(shù)沖突 while(s-lchild) s=s-lchild; s-lchild=child-lchild-rchild;/若child-lchild右子樹(shù)非空,把child的左孩子的右子樹(shù)接到孩子，右子樹(shù)的最左下結(jié)點(diǎn) if(child-lchild-rtag!=1) /child-lchild右子樹(shù)非空，此時(shí)s-ltag本為1 s-ltag=0; q=child-lchild; while(q-r

41、child!=NULL) q=q-rchild; q-rchild=s; /把q的后繼指到s上 child-lchild-rchild=child-rchild;/child左孩子的右子樹(shù)設(shè)置 child-lchild-rtag=0; /原本不知是否為0，但可以一起考慮 free(child); if(child=pre-rchild) /是父親結(jié)點(diǎn)的右孩子 if(child-ltag=1&child-rtag=1)/孩子結(jié)點(diǎn)無(wú)左右 pre-rchild=child-rchild; /child右孩子上提 pre-rtag=1; /原本為0 free(child); else if(child

42、-ltag!=1&child-rtag=1)/孩子結(jié)點(diǎn)有左無(wú)右 pre-rchild=child-lchild; /child左孩子上提 s=child-lchild; while(s-rchild!=NULL) /child左孩子最右下節(jié)點(diǎn)，是child的前驅(qū) s=s-rchild; s-rchild=child-rchild;/把child后繼指給s保存 free(child); else if(child-ltag=1&child-rtag!=1)/孩子結(jié)點(diǎn)有右無(wú)左 pre-rchild=child-rchild;/child右孩子上提 s=child-rchild; /查找child右孩子最左下端 while(s-lchild) /是child的后繼s位置 s=s-lchild; s-lchild=child-lchild;/把child前驅(qū)指給s保存 free(child); e