1、課程設計說明書（數據結構課程設計）專 業: 網絡工程 課程名稱: 數據結構課程設計 班級: 網絡B11-1設計題目: 線索二叉樹的應用 設計時間: 2013-2-25 至 2013-3-8 評 語:_評閱成績: 評閱教師: 一、問題描述與需求分析1、問題描述 本實驗的問題是建立一個線索二叉樹，并實現線索二叉樹的插入、刪除、恢復線索等功能。2、功能需求分析 本程序要實現的功能是： 1. 線索二叉樹的建立。 2.線索二叉樹的插入。 3.線索二叉樹的刪除。 4.線索二叉樹的恢復。 想要完成上面的功能，我們首先是要知道上面是線索二叉樹。我們可以從數據結構的書上找到答案，利用二叉鏈表的空指針域將空的左孩

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

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

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

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

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

7、/建隊為指針類型Bithptr *CreatTree()front=1;rear=0; /置空隊if(ch!='') /不是虛結點.則建立結點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) /孩子和雙親結點都不是虛結點if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s;if(

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

9、使其前驅線索化，令p->lchild=pre；若*pre的左線索標志已經建立（pre->rtag=1），則可使其后繼線索化，令pre->rchild=p; 算法實現;void PreThread(Bithptr *root)PreThread(p->lchild); /左子樹線索化if(pre&&pre->rtag=1)pre->rchild=p; /前驅結點后繼線索化if(p->lchild=NULL) p->ltag=1; p->lchild=pre;if(p->rchild=NULL) /后繼結點前驅線索化p-&

10、gt;rtag=1;pre=p;PreThread(p->rchild);插入結點函數： 在書中插入一個結點，必須要以固定的規則來進行插入。本程序中樹的輸出使用了中序輸出的方法，所以插入的時候使用的規則就是以中序輸出為順序，先查找到一個點，再將要插入的結點，作為該結點的前驅插入樹中。如中序為：dbeafcg。插入的結點為：b,則插入后的順序為dwbeafcg。 使用查找孩子指針函數來查找結點位置的指針。在查找的過程中要處理好線索指針和孩子指針的關系，不能將線索也當做孩子來處理了。并且在循環的判斷中，且不能使用以前的空位結束語句，而是要用標志域來進行判斷。在查找的過程中，考慮到樹的遞歸性質

11、，所以講查找函數也設置成遞歸函數。 算法實現： Bithptr*SearchChild(Bithptr*point,char findnode)Bithptr *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

12、) /判斷是否有右子樹point2=SearchChild(point->rchild,findnode);/遞歸if(point2!=NULL)return point2;return NULL;elsereturn NULL; 在一棵樹種插入一個結點，因為插入的位置不同，就對應著不同的插入情況。當插入結點有左孩子時：找到左孩子的最右下結點將待插的結點插為其結點的右孩子。當插入結點沒有左孩子時：直接將帶插的結點插為其結點的左孩子。 算法實現：􀈎當結點有左子樹時.p2=child;child=child->lchild;while(child->rchild

13、&&child->rtag=0) /左子樹的最右下結點child=child->rchild;p1->rchild=child->rchild; /后繼線索化p1->rtag=1;child->rtag=0;child->rchild=p1; /連接結點p1->lchild=child; /前驅線索化p1->ltag=1;􀈎當結點沒左孩子的時.p1->lchild=child->lchild; /前驅化child->ltag=0;p1->ltag=1;child->lchild

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

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

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

17、rchild=child->rchild;要刪除結點有右無左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;要刪除結點左右都有.pre->lchild=child->lchild;s=child->rchild;wh

18、ile(s->lchild)s=s->lchild;s->lchild=child->lchild->rchild; /把要刪除結點的左孩子的右子樹接到孩子右子樹的最左下結點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;四、運行結果和調試分析輸

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

20、針對這些出現的問題，進行修改，是程序具有一個合理的結構，良好的可讀性和用戶友好性。 當然在整個過程中，也有很多的問題是我無法解決的，在這個時候我會求助于我的同學，他們都很樂意給予我幫助，對我提出的問題進行耐心個的分析，在這個過程中問題不僅解決了，我寫學習了同學的思想，他們對解決問題的方法。 此次課程設計還讓我感覺到，解決問題時的思想很重要，因為思想決定著你程序的走向，我解決問題的方法，可以說，學習程序設計，思想是很重要的。有一個好的思想，會對程序有很大的幫助。 參考文獻1嚴蔚敏，吳偉民編著數據結構（C語言版）清華大學出版社。源代碼：#include "stdio.h"#in

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

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

23、) /判斷是否為空結點s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;rear+;Qrear=s; /將結點地址加入隊列中if(rear=1)T=s; /輸入為第一個結點為根結點elseif(s!=NULL&&Qfront!=NULL) /孩子和雙親結點均不是虛結點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) /中序線索化算法?函數實現Bithptr *p;p=root;if(p)PreThread(p->lchild);/線索化左子樹if(pre&

25、&pre->rtag=1)pre->rchild=p; /前驅結點后繼線索化if(p->lchild=NULL)p->ltag=1;p->lchild=pre;if(p->rchild=NULL) /后繼結點前驅線索化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);/如果是第一個結點if(f->ltag=1&&f->lchild!=NULL) printf("%c 【%c 】",f->lchild->data,f->data); /如果此結點有前驅就輸出前驅和此結點if(f->ltag=1&&f->rtag=1&&f->rchild!=NULL)printf("%c",f->rchild->data); /如果此結點有前驅也有后繼?就輸出后繼els

27、e if(f->rtag=1&&f->rchild!=NULL) printf(" 【%c 】%c",f->data,f->rchild->data);/如果沒有前驅?就輸出此結點和后繼printf("n");if(f->ltag!=1)PrintIndex(f->lchild);if(f->rtag!=1)PrintIndex(f->rchild);Bithptr *SearchChild(Bithptr *point,char findnode) /查找孩子結點函數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) /查找父親結點函數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("請輸入要插入的結點的信息:");scanf("%c",&c);scanf("%c",&c);p1=(Bi

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

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

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

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

35、re->data);else/當是頭結點的時候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) /查找孩子左子樹的最右下結點s=s->rchild;q=child->rchild;while(q->lchild&&q->ltag!=1) /查找孩子右子樹的最左下結點q=q->lchild;s-

37、>rchild=child->rchild; /連接s->rtag=0;q->lchild=s;free(child);return t;if(child=pre->lchild|child=pre)/是父親結點的左孩子if(1=child->ltag&&1=child->rtag)/孩子結點無左右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)/孩子結點有左無右pre->lchild=child->lchild;s=child->lchild;while(s->rchild) /查找左子樹的最右下結點s=s->rchild;s->rchild=child->rchild;free(child);else if(1=child->ltag&&1!=child->rtag)/孩子結點有右無左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)/孩子結點左右都有pre->lchild=child->lchild;s

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

41、父親結點的右孩子if(1=child->ltag&&1=child->rtag)/孩子結點無左右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)/孩子結點有左無右pre->rchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=child->rchild;if(child->rchild!=NULL