數(shù)據(jù)結構課程設計線索二叉樹的應用

1、數(shù)據(jù)結構課程設計報告（2010 / 2011 學年第二學期）題目： 線索二叉樹的應用專業(yè)班級： 09計算機（2）班學生姓名：學號：指導教師：設計周數(shù)： 19、20周設計成績：2011年7 月4 日一、 需求分析：1、題目：線索二叉樹的應用2、目的和任務：數(shù)據(jù)結構課程設計是計算機科學與技術專業(yè)集中實踐性環(huán)節(jié)之一，是學習完數(shù)據(jù)結構課程后進行的一次全面的綜合練習。其目的就是要達到理論與實際應用相結合，使學生能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)良好的程序設計技能。其任務為：要求：實現(xiàn)線索樹建立、插入、刪除、恢復線索的實現(xiàn)。3、數(shù)據(jù)輸入輸出：原

2、始數(shù)據(jù)要求輸入二叉樹的7個結點：1234567，輸出的是一個二叉樹，這就實現(xiàn)了二叉樹的建立過程。然后對二叉樹進行線索化。對其進行插入：在7結點處插入結點8；刪除：刪除結點8;恢復線索等功能。進行二叉樹的初始化，依次輸入，以*結束：1234567*線索二叉樹的應用*1、進行二叉樹線索化2、進行插入操作3、刪除4、中序輸出5、線索輸出0、退出請選擇：1已經(jīng)實現(xiàn)二叉樹的線索化，可選擇5查看線索4、設計算法測試用例：（1）輸入結點:1234567;(2)對輸入的二叉樹進行線索化；（3）查看二叉樹的中序線索輸出：4-2-5-1-6-3-7；（4）在7結點處插入結點8，此時完成線索化恢復，查看二叉樹的中序

3、線索輸出：4-2-5-1-6-3-8-7;(5)刪除結點8，此時完成線索化恢復，發(fā)現(xiàn)結點8，ltag=1,rtag=1,查看二叉樹的中序線索輸出：4-2-5-1-6-3-7;(6)繼續(xù)刪除結點r，發(fā)現(xiàn)無該結點，則輸入錯誤。二、數(shù)據(jù)結構的選擇和概要設計1、數(shù)據(jù)結構二叉樹是由n（n=0）個結點組成的有限集合，其中：（1）當n0時，為空二叉樹。（2）當n0時，有且僅有一個特定的結點，稱為二叉樹的根，不相交的子集，其中每一個子集本身又是一棵二叉樹，分別稱為左子樹和右子樹。線索化是將二叉樹轉換成線索二叉樹的過程。按某種遍歷將二叉樹線索化，只需在遍歷過程中將二叉樹中每個結點的空的左右孩子指針域分別修改為指

4、向其前驅和后繼結點。（1）線索二叉樹的結點的結構如下：ltaglchilddatartagrchild約定：ltag=0 /表示lchild域指示該結點的左孩子ltag=1 /表示lchild域指示該結點的前驅rtag=0 /表示rchild域指示該結點的右孩子rtag=1 /表示rchild域指示該結點的后繼 (2)線索鏈表中結點類型說明： typedef char datatype; typedef struct node int ltag,rtag; datatype data; struct node *lchild,*rchild;bithptr;(3)線索化算法：結點*pre 是結

5、點*p的前驅，而*p是*pre的后繼。這樣，當遍歷到結點*p時，可以進行以下三步操作：1）若*p有空指針域，則將相應的標志置1.2）若*p的左線索標志已經(jīng)建立（p-ltag=1）,則可使其前驅線索化，令p-lchild=pre.3)若*pre的右線索標志已經(jīng)建立（pre-rtag=1）,則可使其后繼線索化，令pre-rchild=p.如此，二叉樹的線索化可以在二叉樹的遍歷過程完成，該算法應為相應順序的遍歷算法的一種變化形式。（4）二叉鏈表的建立：其算法描述如下：bitree *crt_bt_pre(bitree *bt) char ch; ch=getchar( ); if(ch=) bt=n

6、ull; else bt=(bitree *)malloc(sizeof(bitree); bt-data=c; bt-lchild=crt_bt_pre(bt-lchild); bt-rchild=crt_bt_pre(bt-rchild); return(bt);2、設計思想建立二叉樹（即指在內(nèi)存中建立二叉樹的存儲結構），建立一個二叉鏈表，需按某種順序一次輸入二叉樹中的結點，且輸入順序必須隱含結點間的邏輯結構信息。對于一般的二叉樹，需添加虛結點，使其成為完全二叉樹。關鍵在于如何將新結點作為左孩子和右孩子連接到它的父結點上?？梢栽O置一個隊列，該隊列是一個指針類型的數(shù)組，保存已輸入的結點地址。

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

8、指針p指示當前正在訪問的結點。結點*pre是結點*p的前趨，而*p是*pre的后繼。結點插入算法：由線索二叉樹的定義易知插入的節(jié)點定是個葉子節(jié)點，需注意線索的修改，可分為兩種情況：1）：插入的節(jié)點t是右兒子，t的中序后繼是其父親的中序后繼，中序前驅是其父親。2）：插入的節(jié)點t是左兒子，t的中序前驅是其父親的中序前驅，中序后繼是其父親。結點刪除算法：刪除的情況與搜索二叉樹的刪除的類似1）：刪除的節(jié)點p是葉子節(jié)點，直接刪除，修改其父親的線索。2）：刪除的節(jié)點p有一個兒子，p有一個左兒子，以p為根的左子樹中的具有最大值節(jié)點的t中序后繼是p的中序后繼，中序前驅不變；p有一個右兒子，以p為根的右子中的具

9、有最小值節(jié)點t中序前驅是p的中序前驅，中序后繼不變。3）：刪除的節(jié)點p有二個兒子，轉化為葉子節(jié)點或只有一個兒子節(jié)點的刪除。3、流程圖開始定義二叉樹t=creattree( )1=i輸入i!=0輸入選擇菜單輸入ii=1prethred(t)i=2insert(t)i=3deletenode(t)i=4inorder(t)退出三、 詳細設計和編碼1、主函數(shù)void main()bithptr *t;int i;/system(color 1a);t=creattree();printf(n);i=1;while(i)printf(t1 進行二叉樹線索化n);printf(t2 進行插入操作n);p

10、rintf(t3 進入刪除操作n);printf(t4 中序輸出n);printf(t5 線索輸出n);printf(t0 退出n);printf(t 請選擇:);scanf(%d,&i);printf(n);switch(i)case 1:prethread(t);printf(t已經(jīng)實現(xiàn)二叉樹的線索化n);printf(n);break;case 2:insert(t);printf(n);break;case 3:t=deletenode(t);printf(n);break;case 4:inorder(t);printf(n);break;case 5:printindex(t);b

11、reak;case 0:exit(1);default:printf(errornt請繼續(xù)選擇:);2、中序線索化算法：void prethread(bithptr *root) /中序線索化算法，函數(shù)實現(xiàn)bithptr *p;p=root; if(p) 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-rtag=1;pre=p;prethread(p-rchild

12、);四、 上機調(diào)試做這個課程設計，想到用各種數(shù)據(jù)結構和主要的思想，反反復復的修改和改進，花費了好幾天的時間。正式著手寫程序只用了大概一天的時間，但是調(diào)試的時候卻用了好幾天。1、當用二叉鏈表作為二叉樹的存儲結構時?？梢苑奖愕卣业侥硞€結點的左右孩子，但一般情況下，無法直接摘到該結點在沒中遍歷序列中的前驅和后繼接待你。為了解決這個問題，所以采用線索二叉樹。但是在編寫過程中，忽略了線索二叉樹的改變，沒有改變空的左孩子指針域，而后再看了一遍數(shù)據(jù)結構的相關指導教材，發(fā)現(xiàn)了錯誤，及時改正，將空的左孩子指針域改為指向其前驅。2、在進行線索化的編寫過程中，出現(xiàn)了問題。開始只能對幾點進行前驅線索化，而不能進行后繼

13、線索化。為此做了相應調(diào)整：（1）若*p有空指針域，則將相應的標志置1。 （2）若*p的左線索標志已經(jīng)建立，則可使其前驅線索化，令p-lchild=pre。 （3）若*pre的右線索標志已經(jīng)建立，則可使其后繼線索化，令pre-rchild=p。 3、在編寫中序線索二叉樹中的后繼查找算法時，只編寫了其中一種情況，應該有兩種情況(1)*p的右子樹為空，則p-rchild為右線索，指向*p的后繼結點。（2）若*p的右子樹非空，根據(jù)中序遍歷的順序，*p的后繼結點為其右子樹中最左下的結點。五、 心得體會本次課程設計，使我對數(shù)據(jù)結構這門課程有了更深入的理解。數(shù)據(jù)結構是一門實踐性較強的課程，為了學好這門課程，

14、必須在掌握理論知識的同時，加強上機實踐。我的課程設計題目是線索二叉樹的應用。剛開始做這個程序的時候，感到完全無從下手，甚至讓我覺得完成這次程序設計根本就是不可能的，于是開始查閱各種資料以及參考文獻，之后便開始著手寫程序，寫完運行時有很多問題。特別是實現(xiàn)線索二叉樹的刪除運算時很多情況沒有考慮周全，經(jīng)常運行出現(xiàn)錯誤，但通過同學間的幫助最終基本解決問題。在本課程設計中，我明白了理論與實際應用相結合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設計技能以及合作能力。這次課程設計同樣提高了我的綜合運用所學知識的能力。并對vc有了更深入的了解。數(shù)據(jù)結構是一門實踐性很強的課程，

15、上機實習是對學生全面綜合素質進行訓練的一種最基本的方法，是與課堂聽講、自學和練習相輔相成的、必不可少的一個教學環(huán)節(jié)。上機實習一方面能使書本上的知識變“活”，起到深化理解和靈活掌握教學內(nèi)容的目的；另一方面，上機實習是對學生軟件設計的綜合能力的訓練，包括問題分析，總體結構設計，程序設計基本技能和技巧的訓練。此外，還有更重要的一點是：機器是比任何教師更嚴厲的檢查者。因此，在“數(shù)據(jù)結構”的學習過程中，必須嚴格按照老師的要求，主動地、積極地、認真地做好每一個實驗，以不斷提高自己的編程能力與專業(yè)素質。通過這段時間的課程設計，我認識到數(shù)據(jù)結構是一門比較難的課程。需要多花時間上機練習。這次的程序訓練培養(yǎng)了我實

16、際分析問題、編程和動手能力，使我掌握了程序設計的基本技能，提高了我適應實際，實踐編程的能力。 總的來說，這次課程設計讓我獲益匪淺，對數(shù)據(jù)結構也有了進一步的理解和認識。六、測試結果及其分析如圖1所示，初始化輸入二叉樹，實現(xiàn)線索化，查看線索輸出： 圖1如圖2所示，在7結點處插入結點8，恢復線索化，查看中序線索輸出為： 圖2如圖3所示，刪除結點8，恢復線索化，查看中序線索輸出為： 圖3如圖4所示，刪除結點r，發(fā)現(xiàn)無該結點，則輸出為： 圖4七、參考文獻（1）嚴慰敏 編數(shù)據(jù)結構習題集清華大學出版社（2）胡學軍 編數(shù)據(jù)結構高等教育出版社附錄：源程序：#include #include malloc.h#i

17、nclude windows.h#define maxsize 30 /規(guī)定樹中結點的最大數(shù)目typedef struct node /定義數(shù)據(jù)結構int ltag,rtag; /表示child域指示該結點是否孩子char data; /記錄結點的數(shù)據(jù)struct node *lchild,*rchild; /記錄左右孩子的指針bithptr;bithptr *qmaxsize; /建隊，保存已輸入的結點的地址bithptr *creattree() /建樹函數(shù)，返回根指針char ch;int front,rear;bithptr *t,*s;t=null;front=1;rear=0; /

18、置空二叉樹printf(進行初始化，請依次輸入n);ch=getchar(); /輸入第一個字符while(ch!=#) /判斷是否為結束字符s=null;if(ch!=) /判斷是否為虛結點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)qfr

19、ont-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,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);/線索化左子

20、樹if(pre&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(【%c】,f-data); /如果是第一個結點if(f-ltag=1&f-lchild!=null)printf(%c【

21、%c】,f-lchild-data,f-data); /如果此結點有前驅就輸出前驅和此結點if(f-ltag=1&f-rtag=1&f-rchild!=null)printf(%c,f-rchild-data); /如果此結點有前驅也有后繼，就輸出后繼else 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 *se

22、archchild(bithptr *point,char findnode) /查找孩子結點函數(shù)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) point2=searchchild(point-rchild,findnode);if(point2!=null)retur

23、n point2;return null;elsereturn null;bithptr *searchpre(bithptr *point,bithptr *child) /查找父親結點函數(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!=null)return

24、 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=(bithptr *)malloc(sizeof(bithptr); /插入的結點信息p1-data=c;p1-lchild=nu

25、ll;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);system(pause);return ;else printf(發(fā)現(xiàn)結點%cn,child-data);if(child-ltag=0) /當孩子結點有左孩子的時候p2=child;child=child-lchild;while(child-rchild&child-rtag=0) /找到

26、左子樹下，最右結點child=child-rchild;printf(發(fā)現(xiàn)結點%cn,child-data);p1-rchild=child-rchild; /后繼化p1-rtag=1;child-rtag=0;child-rchild=p1; /連接p1-lchild=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插入結點操作已經(jīng)完成，并同時完成了線索化的恢

27、復n);bithptr * deletenode(bithptr *t)bithptr *child,*pre,*s,*q;char ch;printf(輸入查找的結點信息:);ch=getchar();ch=getchar();child=searchchild(t,ch);printf(發(fā)現(xiàn)結點:%cn,child-data);printf(ltag=%d,rtag=%dn,child-ltag,child-rtag);pre=searchpre(t,child);printf(發(fā)現(xiàn)結點:%cn,pre-data);if(null=child)printf(沒有找到結點:);return

28、t;system(pause);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-rchild=pre;free(child);else if(1!=child-ltag&1=child-rtag)/孩子結點有左無右pre-lchild=child-lchild;s=child-lchild;while(s

29、-rchild)s=s-rchild;s-rchild=child-rchild;free(child);else if(1=child-ltag&1!=child-rtag)/孩子結點有右無左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;free(child);else if(1!=child-ltag&1!=child-rtag

30、)/孩子結點左右都有pre-lchild=child-lchild;s=child-rchild;while(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;free(child);if(child=pre-rchild

31、) /是父親結點的右孩子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(c

32、hild-rchild!=null)if(child-rchild-ltag=1)child-rchild-lchild=pre;free(child);else if(1=child-ltag&1!=child-rtag)/孩子結點有右無左pre-rchild=child-rchild;s=child-rchild;while(s-lchild)s=s-lchild;s-lchild=child-lchild;free(child);else if(1!=child-ltag&1!=child-rtag)/孩子結點左右都有/*pre-lchild=child-lchild;s=child-rchild;while(