資源描述：
《數(shù)據(jù)結(jié)構(gòu)課程設計-苑聰聰》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、河北工程大學科信學院數(shù)據(jù)結(jié)構(gòu)課程設計報告（2010/2011學年第?二?學期）題????目：線索二叉樹的應用專業(yè)班級：09計算機（2）班學生姓名：苑聰聰學????號：090212236指導教師：??陳麗、楊榮愛設計周數(shù)：????19、20周設計成績：2011???年?7月?4日一、需求分析：1、題目：線索二叉樹的應用2、目的和任務：《數(shù)據(jù)結(jié)構(gòu)》課程設計是計算機科學與技術專業(yè)集中實踐性環(huán)節(jié)之一，是學習完《數(shù)據(jù)結(jié)構(gòu)》課程后進行的一次全面的綜合練習。其目的就是要達到理論與實際應用相結(jié)合，使學生能夠根據(jù)數(shù)據(jù)對
2、象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)良好的程序設計技能。其任務為：要求：實現(xiàn)線索樹建立、插入、刪除、恢復線索的實現(xiàn)。3、數(shù)據(jù)輸入輸出：原始數(shù)據(jù)要求輸入二叉樹的7個結(jié)點：1234567，輸出的是一個二叉樹，這就實現(xiàn)了二叉樹的建立過程。然后對二叉樹進行線索化。對其進行插入：在7結(jié)點處插入結(jié)點8；刪除：刪除結(jié)點8;恢復線索等功能。進行二叉樹的初始化，依次輸入，以*結(jié)束：1234567*線索二叉樹的應用****************************1、進
3、行二叉樹線索化2、進行插入操作3、刪除4、中序輸出5、線索輸出0、退出請選擇：1已經(jīng)實現(xiàn)二叉樹的線索化，可選擇5查看線索4、設計算法測試用例：（1）輸入結(jié)點:1234567;(2)對輸入的二叉樹進行線索化；（3）查看二叉樹的中序線索輸出：4->2->5->1->6->3->7；（4）在7結(jié)點處插入結(jié)點8，此時完成線索化恢復，查看二叉樹的中序線索輸出：4->2->5->1->6->3->8->7;(5)刪除結(jié)點8，此時完成線索化恢復，發(fā)現(xiàn)結(jié)點8，ltag=1,rtag=1,查看二叉樹的中序線索輸出：4-
4、>2->5->1->6->3->7;(6)繼續(xù)刪除結(jié)點r，發(fā)現(xiàn)無該結(jié)點，則輸入錯誤。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設計1、數(shù)據(jù)結(jié)構(gòu)二叉樹是由n（n>=0）個結(jié)點組成的有限集合，其中：（1）當n＝0時，為空二叉樹。（2）當n>0時，有且僅有一個特定的結(jié)點，稱為二叉樹的根，不相交的子集，其中每一個子集本身又是一棵二叉樹，分別稱為左子樹和右子樹。線索化是將二叉樹轉(zhuǎn)換成線索二叉樹的過程。按某種遍歷將二叉樹線索化，只需在遍歷過程中將二叉樹中每個結(jié)點的空的左右孩子指針域分別修改為指向其前驅(qū)和后繼結(jié)點。（1）線索二叉樹的
5、結(jié)點的結(jié)構(gòu)如下：ltaglchilddatartagrchild約定：Ltag=0//表示lchild域指示該結(jié)點的左孩子Ltag=1//表示lchild域指示該結(jié)點的前驅(qū)Rtag=0//表示rchild域指示該結(jié)點的右孩子Rtag=1//表示rchild域指示該結(jié)點的后繼(2)線索鏈表中結(jié)點類型說明：Typedefchardatatype;Typedefstructnode{Intltag,rtag;Datatypedata;Structnode*lchild,*rchild;}bithptr;(3
6、)線索化算法：結(jié)點*pre是結(jié)點*p的前驅(qū)，而*p是*pre的后繼。這樣，當遍歷到結(jié)點*p時，可以進行以下三步操作：1）若*p有空指針域，則將相應的標志置1.2）若*p的左線索標志已經(jīng)建立（p->ltag=1）,則可使其前驅(qū)線索化，令p->lchild=pre.3)若*pre的右線索標志已經(jīng)建立（pre->rtag=1）,則可使其后繼線索化，令pre->rchild=p.如此，二叉樹的線索化可以在二叉樹的遍歷過程完成，該算法應為相應順序的遍歷算法的一種變化形式。（4）二叉鏈表的建立：其算法描述如下：B
7、itree*crt_bt_pre(bitree*bt){Charch;Ch=getchar();If(ch==‘?！?Bt=null;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)存中建立二叉樹的存儲結(jié)構(gòu)），建立一個二叉鏈表，需按某種順序一次輸入二叉樹中的
8、結(jié)點，且輸入順序必須隱含結(jié)點間的邏輯結(jié)構(gòu)信息。對于一般的二叉樹，需添加虛結(jié)點，使其成為完全二叉樹。關鍵在于如何將新結(jié)點作為左孩子和右孩子連接到它的父結(jié)點上?？梢栽O置一個隊列，該隊列是一個指針類型的數(shù)組，保存已輸入的結(jié)點地址。操作：（1）令隊頭指針front指向其孩子結(jié)點當前輸入的建立鏈接的父結(jié)點，隊尾指針rear指向當前輸入的結(jié)點，初始：front=1,rear=0;（2）若rear為偶數(shù)，則該結(jié)點為父結(jié)點的左孩子；若rear為奇數(shù)，則該結(jié)點的右孩子；若
