線索二叉樹課程設(shè)計

1、信息科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目名稱： 線索二叉樹的計算 學(xué)生姓名： 劉 少 博 學(xué) 號: * 專業(yè)班級： 計算機科學(xué)與技術(shù) 指導(dǎo)教師： 高 攀 2014年 1月 8 1、設(shè)計的目的與要求 此程序需要完成如下要求：建立線索二叉樹，并實現(xiàn)線索二叉樹的插入、刪除和恢復(fù)線索的實現(xiàn)。實現(xiàn)本程序需要解決以下幾個問題：1、 如何建立線索二叉樹。2、 如何實現(xiàn)線索二叉樹的插入。3、 如何實現(xiàn)線索二叉樹的刪除。4、 如何實現(xiàn)線索二叉樹恢復(fù)線索的實現(xiàn)。此題目是線索二叉樹的一系列操作問題。首先就要明白線索二叉樹是什么，利用二叉鏈表的空指 針域?qū)⒖盏淖蠛⒆又羔樣蚋臑橹赶蚱淝膀?qū)，空的右孩子指針域改為指向其后

2、繼，這種改變指向的指針稱為線索，加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹。 在這個問題中，要解決的任務(wù)是：實現(xiàn)線索二叉樹的建立、插入、刪除、恢復(fù)線索的實現(xiàn)。N個 結(jié) 點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下 的前趨和后繼結(jié)點的指針（這種附加的指針稱為"線索"）。這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。在此次課程設(shè)計中，采用的是中序線索二叉樹。 目 錄摘

3、要41、 引言52、 設(shè)計任務(wù)與目的 53、 設(shè)計方案與實施5 1、總體設(shè)計 52、 詳細設(shè)計 7 3、程序清單 134、程序調(diào)試與體會245、運行結(jié)果（截圖） 24四、結(jié)論27五、致謝27 六、參考文獻27 摘 要隨著人們生活水平的提高，計算機發(fā)展異常迅速。如今，計算機已經(jīng)深入到我們社會的各個領(lǐng)域，計算機的使用也已不再局限于科學(xué)計算，它已進入人類社會的各個領(lǐng)域并發(fā)揮著越來越重要的作用。通過計算機對各類問題求解已經(jīng)成為一種高效、快捷的方式。樹在計算機領(lǐng)域也得到了廣方的應(yīng)用，如在編譯程序中，可以用樹表示原程序的語法結(jié)構(gòu)。 本次課程設(shè)計主要運用二叉樹的一些特點，來實現(xiàn)線索二叉樹的建立、插入、刪除、

4、恢復(fù)線索等等。關(guān)鍵詞：二叉樹，線索鏈表，線索化，線索。Abstract Key words: Binary tree, Clues linked list, Clues optimization, Clues. As people living standard rise, computer to abnormal development rapidly. Today, computers have deeply into every field of our society, the use of computers is no longer limited to scientific co

5、mputing, it entered the human society eachdomain and plays a more and more important role. Through computer for all kinds of problem solving has become an efficient, quick way. Trees in the field of computer also got wide square applications, such as in compiler, can use the tree says the original p

6、rogram grammatical structures. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-線索二叉樹的計算一、引 言樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點）按分支關(guān)系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。結(jié)構(gòu)樹在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)都可用樹形象表示。樹在計算機領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序時，可用樹表示源程序的語法結(jié)構(gòu)。又如在數(shù)據(jù)系統(tǒng)庫中，樹型結(jié)構(gòu)也是信息的重要組織形式之一。一切具有層次關(guān)系的問題都可用樹來描述。 二、設(shè)計目的與任務(wù)通過本課程設(shè)計教學(xué)所要求達到的目的是：建立線索二叉樹，并實現(xiàn)線索二叉樹的插入、刪除和恢復(fù)線索的實現(xiàn)。三、

7、設(shè)計方案1、總體設(shè)計 首先建立二叉樹，然后對二叉樹進行線索化。線索鏈表的結(jié)點結(jié)構(gòu)    線索鏈表中的結(jié)點結(jié)構(gòu)為： 圖(1) 線索鏈表中的結(jié)點結(jié)構(gòu)中序線索二叉樹的圖示  圖(2) 中序線索二叉樹 建立二叉樹（即指在內(nèi)存中建立二叉樹的存儲結(jié)構(gòu)），建立一個二叉鏈表，需按某種順序一次輸入二叉樹中的結(jié)點，且輸入順序必須隱含結(jié)點間的邏輯結(jié)構(gòu)信息。對于一般的二叉樹，需添加虛結(jié)點，使其成為完全二叉樹。 關(guān)鍵在于如何將新結(jié)點作為左孩子和右孩子連接到它的父結(jié)點上。可以設(shè)置一個隊列，該隊列是一個指針類型的數(shù)組，保存已輸入的結(jié)點地址。 （1）令隊頭指針front指向其孩子結(jié)點當(dāng)

8、前輸入的建立鏈接的父結(jié)點，隊尾指針 rear指向當(dāng)前輸入的結(jié)點，初始：front=1,rear=0; （2）若rear為偶數(shù)，則該結(jié)點為父結(jié)點的左孩子；若rear為奇數(shù)，則該結(jié)點的右孩子；若父結(jié)點和孩子結(jié)點為虛結(jié)點，則無需鏈接。 （3）若父結(jié)點與其兩個孩子結(jié)點的鏈接完畢，則令front=front+1,使front指向下一個等待鏈接的父結(jié)點。二叉樹的中序索化算法與中序歷算法類似。只需要將遍歷算法中訪問結(jié)點的操作具體化為建立正在訪問的結(jié)點與其非空中前趨結(jié)點間線索。該算法應(yīng)附設(shè)一個指針pre始終指向剛剛訪問過的結(jié)點（pre的初值應(yīng)為NULL），而指針p指示當(dāng)前正在訪問的結(jié)點。結(jié)點*pre是結(jié)點*p

9、的前趨，而*p是*pre的后繼。程序流程圖:圖(3) 程序流程圖 2、詳細設(shè)計(1) 建樹算法：1、分析：建立一個二叉鏈表，需要按照某種順序依次輸入二叉樹中的結(jié)點，且該輸入順序必須隱含結(jié)點間的邏輯結(jié)構(gòu)的信息。這個建立的方法，按完全二叉樹的層次順序，依次輸入結(jié)點信息建立二叉鏈表的過程。以表示空結(jié)點，以#表示輸入結(jié)束的標(biāo)志 。2、算法思想：依次輸入結(jié)點信息，若其不是虛結(jié)點，則建立一個新結(jié)點。若新結(jié)點是第一個結(jié)點，則令其為根結(jié)點，否則將新結(jié)點作為孩子鏈接到它的父親結(jié)點上。3、實現(xiàn)：在函數(shù)中設(shè)置一隊列，該隊列是一個指針類型的數(shù)組，保存已輸入的結(jié)點的地址。使隊頭指針front指向當(dāng)前與孩子建立鏈接的父親

10、結(jié)點，隊尾指針rear指向當(dāng)前輸入的結(jié)點。若rear為偶數(shù)，則該結(jié)點為父結(jié)點的左孩子，若rear為奇數(shù)，則為父結(jié)點的右孩子。若父結(jié)點或孩子結(jié)點為虛結(jié)點，則無需鏈接。若父結(jié)點與其兩個孩子結(jié)點鏈接完畢，則使front指向下一個等待鏈接的父結(jié)點。4、主要過程： Bithptr *Qmaxsize; /建隊為指針類型 Bithptr *CreatTree() front=1;rear=0; /置空隊 if(ch!='') /不是虛結(jié)點，則建立結(jié)點 s=(Bithptr *)malloc(sizeof(Bithptr); s->data=ch; s->lchild=NULL;

11、 s->rchild=NULL; s->rtag=0; s->ltag=0; if(s!=NULL&&Qfront!=NULL) /孩子和雙親結(jié)點都不是虛結(jié)點 if(rear%2=0) Qfront->lchild=s; else Qfront->rchild=s; if(rear%2=1)front+; /結(jié)點*Qfront的兩個孩子處理完，front+1(2) 線索化算法：1、分析：線索過程必須要按照一定的順序來進行，在本程序中因為樹的遍歷過程使用的是中序遍歷，所以為了方便，線索化的過程也是使用中序線索化。2、方法：按某種遍歷順序?qū)⒍鏄渚€索化

12、，只需要在遍歷的過程中將二叉樹中每個結(jié)點的空的左右孩子指針域分別修改為指向其前驅(qū)和后繼。若其左子樹為空，則將其左孩子域線索化，使其左孩子指針lchild指向其后繼，并且ltag置1。3、實現(xiàn)：要實現(xiàn)線索化，就要知道結(jié)點*pre是結(jié)點*p的前驅(qū)，而*p是*pre的后繼。這樣，當(dāng)遍歷到結(jié)點*p時，可以進行，若*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;4、主要過程： void

13、PreThread(Bithptr *root) PreThread(p->lchild); /左子樹線索化if(pre&&pre->rtag=1)pre->rchild=p; /前驅(qū)結(jié)點后繼線索化 if(p->lchild=NULL) p->ltag=1;p->lchild=pre;if(p->rchild=NULL) /后繼結(jié)點前驅(qū)線索化p->rtag=1;pre=p;PreThread(p->rchild);(3) 插入結(jié)點函數(shù)1、方法：在樹中插入一個結(jié)點，就必須要以固定的規(guī)則來進行插入。在本程序中對樹的輸出使用了中序

14、輸出的方法，所以插入的時候使用的規(guī)則就是以中序輸出為順序，先查找到一個點，再將要插入的結(jié)點作為該結(jié)點的前驅(qū)插入樹中。如中序為：dbeafcg 插入的結(jié)點為：w 要插入的位置為：b 則插入結(jié)點后的順序為：dwbeafcg 2、查找：使用查找孩子指針函數(shù)來查找結(jié)點位置的指針。在查找的過程中要處理好線索指針和孩子指針的關(guān)系，不能將線索也當(dāng)作孩子處理了。并且在循環(huán)的判斷過程中，再不能使用以前的以空為結(jié)束語句，而是要用標(biāo)志域來進行判斷。在查找的過程中，考慮到樹的遞歸性質(zhì)，所以將查找函數(shù)也設(shè)置為遞歸函數(shù)。3、查找函數(shù)實現(xiàn)：Bithptr*SearchChild(Bithptr*point,char fin

15、dnode) Bithptr *point1,*point2; if(point!=NULL)if(point->data=findnode)return point; /找到結(jié)點的信息，返回指針 else if(point->ltag!=1) /判斷是否有左子樹point1=SearchChild(point->lchild,findnode);/遞歸if(point1!=NULL)return point1; if(point->rtag!=1) /判斷是否有右子樹point2=SearchChild(point->rchild,findnode);/遞歸if

16、(point2!=NULL)return point2; return NULL; else return NULL;4、插入方法：在一棵樹中插入一個結(jié)點，因為插入的位置不同，就對應(yīng)著不同的插入情況。通過分析總結(jié)出各種情況： 插入結(jié)點有左孩子時：插入的方法是，找到左子樹的最右下結(jié)點，將待插的結(jié)點插為其結(jié)點的右孩子。 插入結(jié)點沒有左孩子時： 插入的方法是，直接將待插的結(jié)點插為其結(jié)點的左孩子。5、插入實現(xiàn)：（當(dāng)結(jié)點有左子樹時）p2=child;child=child->lchild;while(child->rchild&&child->rtag=0) /左子樹的

17、最右下結(jié)點child=child->rchild;p1->rchild=child->rchild; /后繼線索化p1->rtag=1;child->rtag=0;child->rchild=p1; /連接結(jié)點p1->lchild=child; /前驅(qū)線索化p1->ltag=1;（當(dāng)結(jié)點沒左孩子的時）p1->lchild=child->lchild; /前驅(qū)化child->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=childp1->rtag=1; 6、圖形

18、顯示：如插入abcdefg# 中序為：dbeafcg 插入的結(jié)點為：w 要插入的位置為：b 建樹后，結(jié)點的線索變化如圖4和圖5；其中虛線為待插結(jié)點在插入過程中將要變化的線索 a b ce d g dvvv f圖(4) 結(jié)點的線索變化圖a 則插入結(jié)點后的順序為：dwbeafcg w a g fe c d b圖(5) 結(jié)點的線索變化 圖b (4) 刪除結(jié)點函數(shù) 1、分析：要在函數(shù)中刪除一個結(jié)點，也要考慮各種不同的情況。在刪除結(jié)點之前也要先找到要刪除的點，就調(diào)用查找孩子結(jié)點函數(shù)Bithptr *SearchChild(Bithptr *point,char findnode)找到其結(jié)點的指針。再后面

19、的操作就是怎樣刪除了，就發(fā)現(xiàn)在刪除過程中涉及的指針變換需要父親結(jié)點的指針，所以就調(diào)用查找父親結(jié)點函數(shù)Bithptr *SearchPre(Bithptr *point,Bithptr *child)來查找該結(jié)點的父親結(jié)點指針。 2、刪除方法：考慮在刪除的過程中的各種不同的情況，就要在程序的設(shè)計中進行不同的分類，進行不同的處理，考慮不同的處理過程。通過總結(jié)可以知道各種不同的情況。（當(dāng)要刪除結(jié)點是父親結(jié)點的左孩子時） 若要刪除結(jié)點沒有左右孩子：則直接刪除； 若要刪除結(jié)點有左孩子沒右孩子：則將要刪除結(jié)點的左孩子給父親結(jié)點的左孩子； 若要刪除結(jié)點有右孩子沒左孩子：則將要刪除結(jié)點的右孩子給父親結(jié)點的左孩

20、子； 若要刪除結(jié)點左右孩子都有：將要刪除結(jié)點的左子樹的右子樹接到孩子結(jié)點的右子樹的最左下結(jié)點的左子樹，再將孩子結(jié)點的右子樹接到孩子結(jié)點左子樹的右子樹。（當(dāng)要刪除結(jié)點是父親結(jié)點的右孩子時） 若要刪除結(jié)點沒有左右孩子：則直接刪除； 若要刪除結(jié)點有左孩子沒右孩子：則將要刪除結(jié)點的左孩子給父親結(jié)點的右孩子； 若要刪除結(jié)點有右孩子沒左孩子：則將要刪除結(jié)點的右孩子給父親結(jié)點的右孩子； 若要刪除結(jié)點左右孩子都有：將要刪除結(jié)點的右子樹的左子樹接到孩子結(jié)點的左子樹的最右下結(jié)點的右子樹，再將孩子結(jié)點的右子樹接到孩子結(jié)點右子樹的左子樹。(當(dāng)要刪除結(jié)點是整個二叉樹的頭結(jié)點時) 若要刪除結(jié)點沒有左右孩子，則直接將空給頭

21、指針。 若要刪除結(jié)點有左孩子沒右孩子，則將孩子結(jié)點的左孩子作為頭結(jié)點。 若要刪除結(jié)點有右孩子沒左孩子，則將孩子結(jié)點的右孩子作為頭結(jié)點。 若要刪除結(jié)點左右孩子都有，則將孩子結(jié)點的左孩子作為頭結(jié)點，將孩子結(jié)點的右子樹插入孩子結(jié)點的左子樹的最右下結(jié)點的右子樹。 3、實現(xiàn)：（只列出要刪除結(jié)點是父結(jié)點的左子樹的情況） 要刪除結(jié)點無左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;要

22、刪除結(jié)點有左無右：pre->lchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=child->rchild;要刪除結(jié)點有右無左：pre->lchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild;if(child->lchild!=NULL) if(child->lchild->

23、rtag=1)child->lchild->rchild=pre;要刪除結(jié)點左右都有：pre->lchild=child->lchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild->rchild; /把要刪除結(jié)點的左孩子的右子樹接到孩子右子樹的最左下結(jié)點if(child->lchild->rtag!=1)s->ltag=0;q=child->lchild;while(q->rchild)q=q->rchil

24、d;q->rchild=s;child->lchild->rchild=child->rchild;child->lchild->rtag=0;4、圖形顯示如圖6：如刪除結(jié)點e 中序為：dbeafcg 刪除后：dbafcg g f e d c b a圖（6）刪除結(jié)點圖示3、 程序清單#include "stdio.h"#include "malloc.h"#define maxsize 20 /規(guī)定樹中結(jié)點的最大數(shù)目typedef struct node /定義數(shù)據(jù)結(jié)構(gòu)int ltag,rtag; /表示child域指

25、示該結(jié)點是否孩子 char data; /記錄結(jié)點的數(shù)據(jù)struct node *lchild,*rchild; /記錄左右孩子的指針Bithptr; Bithptr *Qmaxsize; /建隊，保存已輸入的結(jié)點的地址 Bithptr *CreatTree() /建樹函數(shù)，返回根指針char ch;int front,rear;Bithptr *T,*s;T=NULL;front=1;rear=0; /置空二叉樹printf("*n"); printf("* *n"); printf("* 課程設(shè)計題目：線索二叉樹的運算。*n");

26、 printf("* *n"); printf("*n"); printf("創(chuàng)建二叉樹，請依次輸入，表示虛結(jié)點，以#結(jié)束n");ch=getchar(); /輸入第一個字符while(ch!='#') /判斷是否為結(jié)束字符s=NULL;if(ch!='') /判斷是否為虛結(jié)點s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;rea

27、r+; Qrear=s; /將結(jié)點地址加入隊列中if(rear=1)T=s; /輸入為第一個結(jié)點為根結(jié)點else if(s!=NULL&&Qfront!=NULL) /孩子和雙親結(jié)點均不是虛結(jié)點if(rear%2=0) Qfront->lchild=s; else Qfront->rchild=s;if(rear%2=1)front+;ch=getchar();return T;void Inorder(Bithptr *T) /中序遍歷if(T)if(T->ltag!=1)Inorder(T->lchild);printf("%c"

28、,T->data);if(T->rtag!=1)Inorder(T->rchild);Bithptr *pre=NULL;void PreThread(Bithptr *root) /中序線索化算法，函數(shù)實現(xiàn)Bithptr *p;p=root; if(p) PreThread(p->lchild);/線索化左子樹 if(pre&&pre->rtag=1)pre->rchild=p; /前驅(qū)結(jié)點后繼線索化 if(p->lchild=NULL) p->ltag=1;p->lchild=pre;if(p->rchild=NU

29、LL) /后繼結(jié)點前驅(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("【%c】",f->data); /如果是第一個結(jié)點if(f->ltag=1&&f->lchild!=NULL) printf("%c【%c】",f->l

30、child->data,f->data); /如果此結(jié)點有前驅(qū)就輸出前驅(qū)和此結(jié)點 if(f->ltag=1&&f->rtag=1&&f->rchild!=NULL) printf("%c",f->rchild->data); /如果此結(jié)點有前驅(qū)也有后繼，就輸出后繼else if(f->rtag=1&&f->rchild!=NULL) printf("【%c】%c",f->data,f->rchild->data);/如果沒有前驅(qū)，就輸出

31、此結(jié)點和后繼printf("n");if(f->ltag!=1)PrintIndex(f->lchild);if(f->rtag!=1)PrintIndex(f->rchild); Bithptr *SearchChild(Bithptr *point,char findnode) /查找孩子結(jié)點函數(shù) Bithptr *point1,*point2; if(point!=NULL) if(point->data=findnode) return point; else if(point->ltag!=1) point1=SearchChi

32、ld(point->lchild,findnode); if(point1!=NULL)return point1; if(point->rtag!=1) point2=SearchChild(point->rchild,findnode); if(point2!=NULL)return point2; return NULL; else return NULL; Bithptr *SearchPre(Bithptr *point,Bithptr *child) /查找父親結(jié)點函數(shù) Bithptr *point1,*point2; if(point!=NULL) if(poi

33、nt->ltag!=1&&point->lchild=child)|(point->rtag!=1&&point->rchild=child) return point;/找到則返回 else if(point->ltag!=1) point1=SearchPre(point->lchild,child); if(point1!=NULL) return point1; if(point->rtag!=1) point2=SearchPre(point->rchild,child); if(point2!=NULL

34、) return point2; return NULL; else return NULL;void Insert(Bithptr *root)char ch;char c;Bithptr *p1,*child,*p2;printf("請輸入要插入的結(jié)點的信息:"); scanf("%c",&c);scanf("%c",&c); p1=(Bithptr *)malloc(sizeof(Bithptr); /插入的結(jié)點信息p1->data=c;p1->lchild=NULL;p1->rchild=NU

35、LL;p1->rtag=0;p1->ltag=0;printf("輸入查找的結(jié)點信息:"); scanf("%c",&ch);scanf("%c",&ch);child=SearchChild(root,ch); /查孩子結(jié)點的地址if(child=NULL)printf("沒有找到結(jié)點n");return ;else printf("發(fā)現(xiàn)結(jié)點%cn",child->data);if(child->ltag=0) /當(dāng)孩子結(jié)點有左孩子的時候p2=child

36、;child=child->lchild;while(child->rchild&&child->rtag=0) /找到左子樹下，最右結(jié)點child=child->rchild;p1->rchild=child->rchild; /后繼化 p1->rtag=1;child->rtag=0;child->rchild=p1; /連接 p1->lchild=child; /前驅(qū)化p1->ltag=1; else /當(dāng)孩子結(jié)點沒有左孩子的時候p1->lchild=child->lchild; /前驅(qū)化chi

37、ld->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=child;p1->rtag=1;printf("nt插入結(jié)點操作已經(jīng)完成，并同時完成了線索化的恢復(fù)n");Bithptr * DeleteNode(Bithptr *t)Bithptr *child,*pre,*s,*q;char ch;printf("輸入查找的結(jié)點信息:"); ch=getchar();ch=getchar();child=SearchChild(t,ch); /查找該結(jié)點的孩子結(jié)點printf(&quo

38、t;發(fā)現(xiàn)結(jié)點:%cn",child->data);printf("ltag=%d,rtag=%dn",child->ltag,child->rtag);if(NULL=child)printf("沒有找到結(jié)點:");return t;if(child!=t)pre=SearchPre(t,child);printf("發(fā)現(xiàn)結(jié)點:%cn",pre->data);else /當(dāng)是頭結(jié)點的時候if(child->ltag=1&&child->rtag=1) /沒有左右孩子t=NU

39、LL;else if(t->ltag=1&&t->rtag!=1) /有右孩子沒有左孩子t=child->rchild;child->rchild->lchild=NULL;free(child);return t;else if(t->ltag!=1&&t->rtag=1) /有左孩子沒有右孩子t=child->lchild;child->lchild->rchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag!

40、=1) /有左孩子也有右孩子t=child->lchild;s=child->lchild;while(s->rchild&&s->rtag!=1) /查找孩子左子樹的最右下結(jié)點s=s->rchild;q=child->rchild;while(q->lchild&&q->ltag!=1) /查找孩子右子樹的最左下結(jié)點q=q->lchild;s->rchild=child->rchild; /連接s->rtag=0;q->lchild=s;free(child);return t; i

41、f(child=pre->lchild|child=pre) /是父親結(jié)點的左孩子if(1=child->ltag&&1=child->rtag)/孩子結(jié)點無左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;free(child);else if(1!=child->ltag&&1=child->rtag)/孩

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

43、>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é)點左右都有 pre->lchild=child->lchild;s=child->rchild;while(s->lchild&&s->ltag!=1) /找到右子樹的最左下結(jié)點

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

45、child=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é)點有左無右pre->rchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=ch

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

47、ild);else if(1!=child->ltag&&1!=child->rtag) /孩子結(jié)點左右都有pre->rchild=child->rchild;s=child->rchild;while(s->lchild&&s->ltag!=1) /找到右子樹的最左下結(jié)點s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1) /找到左子樹下最右下結(jié)點q=q->rchild;s->lchild=child->

48、;lchild; /將孩子結(jié)點的左子樹接到右子樹下最左下結(jié)點s->ltag=0;q->rchild=s;free(child);printf("nt刪除結(jié)點操作已經(jīng)完成，并同時完成了線索化的恢復(fù)n");return t;void main()Bithptr *T;int i;T=CreatTree();printf("n");i=1;while(i) printf("t1 中序輸出二叉樹n");printf("t2 進行二叉樹線索化n");printf("t3 進行插入操作n");printf("t4 進入刪除操作n");printf("t5 輸出線索二叉樹n");printf("t0 退出n");printf("t 請選擇:");s