線索二叉樹生成及其遍歷

1、數(shù)據(jù)結構課程設計題 目: 線索二叉樹的生成及其遍歷 學 院： 理學院 班 級： 數(shù)學13-2班 學 生 姓 名：孫晴、張炳赫、張美娜、董自鵬 學 生 學 號： 8、12、13、22 指 導 教 師： 張?zhí)l(fā) 2014 年 12月 24日課程設計任務書姓名X y z s班級設計題目線索二叉樹的生成及其遍歷理論要點二叉樹的遍歷本質(zhì)上是將一個復雜的非線性結構轉(zhuǎn)換為線性結構，使每個結點都有且僅有一個直接前驅(qū)結點和直接后繼結點（第一個結點無前驅(qū)，最后一個結點無后繼）。但是二叉樹中每個結點在這個序列中的直接前驅(qū)結點和直接后繼結點是什么？二叉樹的存儲結構中并沒有反映出來，只能在對二叉樹遍歷的動態(tài)過程中得到這

2、些信息。為了保留結點在某種遍歷序列中直接前驅(qū)喝直接后繼的位置信息，有兩種方法。一是在結點結構中增加向前和向后的指針fwd和bkd，這種方法增加了存儲開銷，不可??；二是利用二叉樹的二叉鏈表的那些空指針域來指示。建立線索二叉樹，或者說對二叉樹線索化，實質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結點的操作是檢查當前的左,右指針域是否為空，將它們改為指向前驅(qū)結點或后續(xù)結點的線索。為實現(xiàn)這一過程，設指針pre始終指向剛剛訪問的結點，即若指針p指向當前結點，則pre指向它的前驅(qū)，以便設線索。 另外，在對一顆二叉樹加線索時，必須首先申請一個頭結點，建立頭結點與二叉樹的根結點的指向關系，對二叉樹線索化后，還需

3、建立最后一個結點與頭結點之間的線索。中序線索二叉樹：若結點的ltag=1，lchild指向其前驅(qū)；否則，該結點的前驅(qū)是以該結點為根的左子樹上按中序遍歷的最后一個結點。若rtag=1，rchild指向其后繼；否則，該結點的后驅(qū)是以該結點為根的右子樹上按中序遍歷的第一個結點。設計目標以二叉鏈表作為存儲結構時，只能找到結點的左、右孩子的信息，而得不到結點的前驅(qū)與后繼信息，為了使這種信息只有在遍歷的動態(tài)過程中才能得到。增設兩個指針分別指示其前驅(qū)結點和后繼結點，并且利用結點的空鏈域存放（線索鏈表）。同時為了記下遍歷過程中訪問結點的先后關系，附設一個指針pre始終指向剛剛訪問過的結點，若指針 p 指向當前

4、訪問的結點，則 pre指向它的前驅(qū)。由此得到中序遍歷建立中序線索化鏈表的算法預期結果對已生成的二叉樹進行中序線索化并利用中序線索實現(xiàn)對二叉樹的遍歷。小組人員具體分工 s：報告填寫 z：程序設計、運行 y：答辯 x：ppt設計制作計劃與進步的安排在兩周（共10天）內(nèi)完成課程設計，具體安排如下： 1.查找所需要的相關資料，進行整理； 2天 2.系統(tǒng)學習相關理論和算法，設計總體流程； 2天 3.編寫源代碼，上機調(diào)試，并進行修改逐步完善代碼； 3天 4.編寫課程設計報告； 2天 5.進行后續(xù)整理工作。 1天目錄摘要I1 題目分析1 1.1相關思想及概念介紹.1 1.2線索二叉樹的結構.1 1.3需求分

5、析.2 2概要設計2 2.1抽象數(shù)據(jù)類型的定義.3 2.2主程序的流程.3 2.3各程序模塊之間的層次(調(diào)用)關系.53詳細設計64調(diào)試分析105用戶使用說明106 測試結果117課程設計體會128 參考文獻129 源程序13摘要針對以二叉鏈表作為存儲結構時，只能找到結點的左、右孩子的信息，而得不到結點的前驅(qū)與后繼信息，為了使這種信息只有在遍歷的動態(tài)過程中才能得到。增設兩個指針分別指示其前驅(qū)和后繼，并且利用結點的空鏈域存放（線索鏈表）。同時為了記下遍歷過程中訪問結點的先后關系，附設一個指針pre始終指向剛剛訪問過的結點，若指針 p 指向當前訪問的結點，則 pre指向它的前驅(qū)。由此得到中序遍歷建

6、立中序線索化鏈表的算法本文通過建立二叉樹， 實現(xiàn)二叉樹的中序線索化并實現(xiàn)中序線索二叉樹的遍歷。實現(xiàn)對已生成的二叉樹進行中序線索化并利用中序線索實現(xiàn)對二叉樹的遍歷的效果。關鍵詞：二叉樹，中序線索二叉樹，中序線索二叉樹的遍歷II數(shù)據(jù)結構程序設計1 題目分析1.1 相關思想及概念介紹（1）二叉樹遍歷二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結點，使每個結點被訪問一次且僅被訪問一次。遍歷二叉樹中經(jīng)常要用到的一種操作。因為在實際應用問題中，常常需要按一定順序?qū)Χ鏄渲械拿總€結點逐個進行訪問，查找具有某一特點的結點，然后對這些滿足條件的結點進行處理。通過一次完整的遍歷，可使二叉樹中結點信息由非線性排列

7、變?yōu)槟撤N意義上的線性序列。也就是說，遍歷操作使非線性結構線性化。由二叉樹的定義可知，一棵二叉樹由根結點、根結點的左子樹和根結點的右子樹三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。若以D、L、R分別表示訪問根結點、遍歷根結點的左子樹、遍歷根結點的右子樹，則二叉樹的遍歷方式有6種：DLR、LDR、LRD、DRL、RDL、和RLD。如果限定先左后右，則只有前三種方式，即DLR（先序遍歷）、LDR（中序遍歷）和LRD（后序遍歷）。（1）線索二叉樹按照某種遍歷方式對二叉樹進行遍歷，可以把二叉樹中所有結點排列為一個線性序列。在該序列中，除第一個結點外，每個結點有且僅有一個直接前驅(qū)結點；除

8、最后一個結點外，每個結點有且僅有一個直接后繼結點。但是，二叉樹中每個結點在這個序列中的直接前驅(qū)結點和直接后繼結點是什么，二叉樹的存儲結構中并沒有反映出來，只能在對二叉樹遍歷的動態(tài)過程中得到這些信息，可以利用二叉樹的二叉鏈表存儲結構中的那些空指針域來指示。這些指向直接前驅(qū)結點和指向直接后繼結點的指針被稱為線索，借了線索的二叉樹成為線索二叉樹。線索二叉樹將為二叉樹的遍歷提供許多方便。1.2 線索二叉樹的結構1、n個結點有n-1個前驅(qū)和n-1個后繼；一共有2n個鏈域，其中：n+1個空鏈域，n-1個指針域；因此, 可以用空鏈域來存放結點的前驅(qū)和后繼。線索二叉樹就是利用n+1個空鏈域來存放結點的前驅(qū)和后

9、繼結點的信息。2、線索：有效利用二叉鏈表中空的存儲空間，指定原有的孩子指針為空的域來存放指向前驅(qū)和后繼的信息，這樣的指針被稱為“線索”。加線索的過程稱為線索化，由此得到的二叉樹稱作線索二叉樹。若結點有左子樹，則左鏈域lchild指示其左孩子（ltag=0）；否則，令左鏈域指示其前驅(qū)（ltag=1）；若結點有右子樹，則右鏈域rchild指示其右孩子（rtag=0）；否則，令右鏈域指示其后繼（rtag=1）；增設一個頭結點，令其lchild指向二叉樹的根結點，ltag=0、rtag=1；并將該結點作為遍歷訪問的第一個結點的前驅(qū)和最后一個結點的后繼；最后用頭指針指示該頭結點。其rchild域的指針指

10、向中序遍歷時訪問的最后一個結點；反之，令二叉樹中序序列中的第一個結點的lchild域指針和最后一個結點rchild域的指針均指向頭結點，這好比為二叉樹建立了一個雙向線索鏈表，既可以從第一個結點起順后繼進行遍歷，也可以從最后一個結點起順前驅(qū)進行遍歷。3、例子：如下圖a示的二叉樹，其中序線索二叉樹為圖b所示：1.3 需求分析以二叉鏈表作為存儲結構時，只能找到結點的左、右孩子的信息，而得不到結點的前驅(qū)與后繼信息，為了使這種信息只有在遍歷的動態(tài)過程中才能得到。增設兩個指針分別指示其前驅(qū)和后繼，并且利用結點的空鏈域存放（線索鏈表）。同時為了記下遍歷過程中訪問結點的先后關系，附設一個指針pre始終指向剛剛

11、訪問過的結點，若指針 p 指向當前訪問的結點，則 pre指向它的前驅(qū)。由此得到中序遍歷建立中序線索化鏈表的算法本文通過建立二叉樹， 實現(xiàn)二叉樹的中序線索化并實現(xiàn)中序線索二叉樹的遍歷。實現(xiàn)對已生成的二叉樹進行中序線索化并利用中序線索實現(xiàn)對二叉樹的遍歷的效果。主要任務：1.建立二叉樹； 2.將二叉樹進行中序線索化；3.編寫程序，運行并修改； 4.利用中序線索遍歷二叉樹 5.書寫課程設計論文并將所編寫的程序完善。2 概要設計2.1抽象數(shù)據(jù)類型的定義二叉樹的存儲結構struct node ElemenType data; /數(shù)據(jù)域int ltag; /左標志域int rtag; /右標志域struct

12、 node *lchild; /左指針域struct node *rchild; /右指針域BTree;2.2主程序的流程 NNCTRL+CYYYNYYYYNNN選擇菜單輸出廣義表形式，前（中，后）遞歸遍歷定義線索二叉樹創(chuàng)建線索二叉樹開始輸入（13）123其他前續(xù)非遞歸中序非遞歸后序非遞歸輸入想查找的結點（有無此結點)輸入想查找的結點輸入想查找的 結點后繼結點后繼結點后繼結點二叉樹無此結點結束2.3各程序模塊之間的層次(調(diào)用)關 3 詳細設計（一）算法的C語言實現(xiàn)#include "stdio.h"#include "stdlib.h"#define O

13、K 1typedef char TElemType;typedef int Status;typedef enum PointerTag Link,Thread; /link=0:pointer,Thread=1:threadtypedef struct BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree; BiThrTree pre; / 全局變量,始終指向剛剛訪問過的結點 void InThreading(BiThrTree p)if(p) In

14、Threading(p->lchild);/左子樹線索化 if(!p->lchild)p->LTag=Thread;p->lchild=pre;/前驅(qū)線索 if(!pre->rchild)pre->RTag=Thread;pre->rchild=p;/后續(xù)線索 pre=p; /保持pre指向p的前驅(qū) InThreading(p->rchild);/右子樹線索化 /if/InThreading Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍歷二叉樹，并將其中序線索化，Thrt

15、指向頭結點/BiThrTree Thrt;if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(-1);Thrt->LTag=Link; /建立頭結點Thrt->RTag=Thread; /右指針回指Thrt->rchild=Thrt;if(!T) Thrt->rchild=Thrt; /若二叉樹為空，則左指針回指else Thrt->lchild=T; pre=Thrt; InThreading(T); /中序遍歷進行中序線索化 pre->rchild=Thrt;/最后一個結點線索化 pre->RTag

16、=Thread; Thrt->rchild=pre; return OK;/InOrderThreading Status InOrderTraverse_Thr(BiThrTree T)/T指向頭結點，頭結點的左鏈lchild指向根結點，非遞歸算法BiThrTree p;p=T->lchild;while(p!=T) /空樹或遍歷結束時，Tp while(p->LTag=Link) p=p->lchild; printf("%cn",p->data); /訪問其左子樹為空的結點 while(p->RTag=Thread&&

17、;p->rchild!=T) p=p->rchild; printf("%cn",p->data); /訪問后續(xù)結點 /while p=p->rchild; /whilereturn OK;/InOrderT_Thr Status CreateBitree(BiThrTree &T)/按先序次序輸入二叉樹char ch,enter;scanf("%c%c",&ch,&enter);if(ch=' ') T=NULL;else if(!(T=(BiThrTree)malloc(sizeof(B

18、iThrNode) exit(1); T->data=ch; CreateBitree(T->lchild); CreateBitree(T->rchild); /elsereturn OK;/CreateBitree int main()BiThrTree T,Thrt;CreateBitree(T);/創(chuàng)建InOrderThreading(Thrt,T);/線索化InOrderTraverse_Thr(Thrt);/遍歷訪問return OK;注意點：在輸入字符創(chuàng)立二叉樹時，要注意葉子結點的輸入形式，即葉子結點的左右空指針也要輸入，在我們這里輸入空格。（二）建立中序二叉樹

19、的遞歸算法，其中pre為全局變量。 BiThrNodeType *pre; BiThrTree InOrderThr(BiThrTree T) /*中序遍歷二叉樹T，并將其中序線索化，pre為全局變量*/ BiThrTree head; head=(BitThrNodeType *)malloc（sizeof（BiThrType）;/*設申請頭結點成功*/ head->ltag=0;head->rtag=1;/*建立頭結點*/ head->rchild=head;/*右指針回指*/ if(！T)head->lchild=head;/*若二叉樹為空，則左指針回指*/ el

20、sehead->lchild=T;pre=head; InThreading(T);/*中序遍歷進行中序線索化*/ pre->rchild=head; pre->rtag=1;/*最后一個結點線索化*/ head->rchild=pre; ; return head; void InThreading(BiThrTree p) /*通過中序遍歷進行中序線索化*/ if(p) InThreading(p->lchild);/*左子樹線索化*/ if(p->lchild=NULL)/*前驅(qū)線索*/ p->ltag=1; p->lchild=pre;

21、if(p->rchild=NULL)p->rtag=1;/*后驅(qū)線索*/ if(pre!=NULL && pre->rtag=1) pre->rchild=p; pre=p; InThreading(p->rchild);/*右子樹線索化*/ 進行中序線索化的算法：bithptr*pre; /* 全程變量*/ voidINTHREAD(bithptr *p) if(p!=NULL) INTHREAD(p->lchild); /* 左子樹線索化*/ if(p->lchild=NULL) p->ltag=1;p->lchild=

22、pre; if(p->rchild=NULL) p->rtag=1; if(pre!=NULL && pre->rtag=1)pre->rchild=p; pre=p; /* 前驅(qū)指向當前結點*/ INTHREAD(p->rchild); /* 右子樹線索化*/ 4 調(diào)試分析該程序在調(diào)試過程中遇到的問題是：對已學知識運用能力欠缺，尤其是在編程方面，由于C語言等計算機基礎課程知識沒有很好的掌握同時在學習數(shù)據(jù)結構時也沒有真正弄懂導致編程時小錯誤不斷，而且在遇到許多小的錯誤時靠自己很難再調(diào)整過來，但整體上是一次對所學知識的運用鞏固，特別是對二叉樹的建立以

23、及對它進行線索方面，翻閱大量的書籍及搜集資料并求教于計算機系的同學，才找到一些解決問題的方法，在用中序遍歷線索二叉樹時總是搞混不過也因此讓我對前序，中序，后序遍歷更加理解。同時，在經(jīng)歷了很多次修改重寫課程設計報告的悲慘經(jīng)歷后，懂得了很多關于辦公軟件方面的知識尤其是自己做的東西一定要保存并備份。主要出現(xiàn)了兩方面問題：A. 語法錯誤（經(jīng)過多次調(diào)試發(fā)現(xiàn)有一處缺少了引號）B. 邏輯錯誤。聲明一個指針只是在內(nèi)存中開辟了一個這種數(shù)據(jù)類型的空間,并讓這個指針指向它,由于它還沒有指向任何變量,因此不能引用其指向的任何成員。5 用戶使用使用該程序時在打開程序的主界面后，輸入相應要求的輸入形式，然后就輸出中序遍歷

24、，方便簡潔。例如：運行時，分別輸入（前序輸入）：1 2 3 0 0 4 0 5 0 0 6 0 0建立如下所示的二叉樹：                      1                  2 &#

25、160;     6               3     4                        5 中序

26、遍歷輸出：3  2  4  5  1  66 測試結果運行時，分別輸入（前序輸入）：1 2 3 0 0 4 0 5 0 0 6 0 0建立如下所示的二叉樹：                      1           

27、60;      2       6               3     4                 

28、60;      5 中序遍歷輸出：3  2  4  5  1  67 結論體會在這次的課程設計中，我們明白了理論和實際還是相差很大的，理論知識能學明白單不代表程序就能編出來，大多數(shù)情況下，我們還是不具備完成這項項目的能力的。它需要我們不僅能夠?qū)⒁郧皩W過的知識與現(xiàn)學的知識融會貫通同時還要求我們學會怎樣如何整合做項目所需要的全部知識以及對為學知識的查詢及自學能力。更重要的時它還要求我們敢于實踐勤于動手，遇到有些不會處理的，我們會上網(wǎng)去查，或者去問老師，或者去問同學。例如以前我們對二叉樹的

29、相關內(nèi)容并不是很熟悉，但經(jīng)過這次課程設計后現(xiàn)在我們不僅掌握了它們的使用方法，更重要的是我們學會了如何去學習，然后快速地應用到我們所需要的項目當中。同時我們還得到了很多關于本門課程的體會：在編寫程序的過程中，把整個系統(tǒng)的框架準確的描述出來是非常重要的而且寫程序是需要步步為營不然一不小心就會出錯。我們們的C語言老師曾經(jīng)說過良好的代碼風格是成功的一半。例如在寫代碼時會有大量的小括號，大括號等，老師曾說這些代碼在書寫時一定要同時寫一對，這樣就可以避免丟掉或忘寫其中的一個。真的是深有體會??！還有在編碼的過程中需要時常進行修改，如果程序的可讀性不強，代碼量又龐大的話，那么對于我們們來說是一件非常不幸的事情

30、，程序反復的改來改去是非常繁瑣的。因此我們們一定要養(yǎng)成良好的書寫代碼的習慣?？傊ㄟ^一次的課程設計，我們不僅對我們所設計的內(nèi)容有了更深的了解同時這門課程的知識掌握也更加牢固了，而且還學到很多關于辦公軟件方面的知識更重要的是通過和計算機方面的老師和同學的交流了解到了很多關于計算機方面及計算機相關工作的一些知識這位我們在選方向時提供了很珍貴的意見?？偠灾@次收獲頗多！8 參考文獻1.嚴蔚敏，吳偉民 數(shù)據(jù)結構C語言版 ：清華大學出版社 ，20092.譚浩強著.C程序設計（第三版）.北京：清華大學出版社，20053.于海英，王國權編著的C語言程序設計.清華大學出版社2012年版4.備注：還有一些是

31、通過查找網(wǎng)站內(nèi)容搜索整理的。9 源程序#include <stdio.h>#include <malloc.h>typedef enumLink,Thread PointerTag; /指針標志typedef int DataType;typedef struct BiThreTree /定義結點元素 PointerTag LTag,RTag; DataType data; struct BiThreTree *lchild,*rchild; BiThreTree;BiThreTree *pre; /全局變量，用于二叉樹的線索化BiThreTree *CreateTree() /按前序輸入建立二叉樹 BiThreTree *T; DataType e; scanf("%d",&e); if(e=0) T=NULL; else T=(BiThreTree *)malloc(sizeof(BiThreTree); T->data=e; T->LTag=Link; /初始化時指針標志均為Link T->RTag=Link; T->lchild=CreateTree(); T-&