數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)線索二叉樹

1、安徽省巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 線索二叉樹 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí) 10計(jì)本2班 學(xué)號(hào)10012082姓名 聯(lián)系方式 指導(dǎo)教師20 11 年 12 月 27 日目 錄1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目1.2、要求2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)2.2、所有功能模塊的流程圖3、詳細(xì)設(shè)計(jì)3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說明3.2、算法的設(shè)計(jì)思想3.3、線索二叉樹的基本操作4、調(diào)試與測(cè)試：4.1、調(diào)試方法與步驟：4.2、測(cè)試結(jié)果的分析與討論：4.3、測(cè)試過程中遇到的主要問題及采取的解決措施：5、時(shí)間復(fù)雜度的分析：6、源程序清單和執(zhí)行結(jié)果

2、7、c程序設(shè)計(jì)總結(jié)8、致謝9、參考文獻(xiàn)1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目線索二叉樹1.2、要求（1）建立中序線索二叉樹,并且遍歷（2）求中序線索二叉樹上已知結(jié)點(diǎn)中序的前驅(qū)和后繼（3）插入節(jié)點(diǎn)到指定位置,試著刪除指定結(jié)點(diǎn)2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)根據(jù)課程設(shè)計(jì)題目的功能要求，各個(gè)功能模塊的組成框圖如下：lchildltagdatartagrchild其中: ltag= o, lchild域指示結(jié)點(diǎn)的左孩子 1， lchild域指示結(jié)點(diǎn)的前驅(qū) rtag= 0， rchild域指示結(jié)點(diǎn)的右孩子 1， lchild域指示結(jié)點(diǎn)的后繼2.2、所有功能模塊的流程圖3、詳細(xì)設(shè)計(jì)模塊功能說明：如函數(shù)功能

3、、入口及出口參數(shù)說明，函數(shù)調(diào)用關(guān)系描述等；開始輸出主菜單的選擇界面輸入choice的值choice=?1.中序線索化輸出中序遍歷結(jié)果3退出程序2后序線索化輸出后續(xù)遍歷結(jié)果 結(jié)束3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說明在某程序中所用二叉樹需經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后繼，則應(yīng)采用線索鏈表作存儲(chǔ)結(jié)構(gòu)。/-二叉樹的二叉線索存儲(chǔ)表示-/二叉樹的二叉線索存儲(chǔ)表示#include<stdio.h>#include<stdlib.h>typedef enum pointertagpointertype;/link=0,指針,thread=1,線索typede

4、f char telemtype;typedef struct bithrnode telemtype data; struct bithrnode *lchild,*rchild; /左右孩子指針 pointertype ltag,rtag; /左右標(biāo)志bithrnode,*bithrtree;bithrtree pre; /前驅(qū)指針void createbithrtree(bithrtree *t)/建樹 char ch; scanf("%c",&ch); fflush(stdin); if(ch=' ') else if(!(*t=(bithr

5、tree)malloc(sizeof(bithrnode) exit(exit_failure); (*t)->data = ch; (*t)->lchild = (*t)->rchild = null; (*t)->ltag = (*t)->rtag = link; createbithrtree(&(*t)->lchild); createbithrtree(&(*t)->rchild); void inthreading(bithrtree t) /建立線索 if(t) inthreading(t->lchild); /左子

6、樹線索化 if(!t->lchild)/前驅(qū)線索 t->ltag = thread; t->lchild = pre; if(!pre->rchild)/后繼線索 pre->rtag = thread; pre->rchild = t; pre = t; inthreading(t->rchild); void inorderthreading(bithrtree *thrt,bithrtree t)/建立線索頭結(jié)點(diǎn) /中序遍歷二叉樹t，并將其中序線索化，thrt指向頭結(jié)點(diǎn)。 if(!(*thrt=(bithrtree)malloc(sizeof(bi

7、thrnode) exit(1); (*thrt)->ltag = link; /建立頭結(jié)點(diǎn) (*thrt)->rtag = thread; (*thrt)->rchild = *thrt; /右指針回指 if(!t) (*thrt)->lchild = *thrt; /若二叉樹空,左指針也回指 else (*thrt)->lchild = t; pre = *thrt; inthreading(t); /進(jìn)行中序線索化 pre->rchild = *thrt; pre->rtag = thread; /最后一個(gè)結(jié)點(diǎn)線索化 (*thrt)->rc

8、hild = pre; void inordertraverse_thr(bithrtree t)/線索化中序遍歷 /t指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)左鏈lchild指向根結(jié)點(diǎn)。 bithrtree p; p = t->lchild; /p指向根結(jié)點(diǎn) while(p!=t) /空樹或遍歷結(jié)束時(shí)，p=t while(p->ltag=link) p = p->lchild; /左子樹為空時(shí)訪問 printf("%c ",p->data); while(p->rtag=thread && p->rchild!=t) p = p->rc

9、hild; printf("%c ",p->data); /訪問后繼結(jié)點(diǎn) p = p->rchild; int main(void) bithrtree tree,treehead; createbithrtree(&tree); inorderthreading(&treehead,tree); printf("ninordertraverse:n"); inordertraverse_thr(treehead); return 0; 3.2、算法的設(shè)計(jì)思想a）構(gòu)建建立線索二叉樹，或者說對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一顆二叉

10、樹。在遍歷過程中，訪問結(jié)點(diǎn)的草所是檢查當(dāng)前的左，右指針域是否為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后續(xù)結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便設(shè)線索。另外，在對(duì)一顆二叉樹加線索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹的跟結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。b）遍歷以中序?yàn)槔?，利用在中序線索二叉樹上需找后續(xù)結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的算法，就可以遍歷到二叉樹的所有結(jié)點(diǎn)，即先找到按某序遍歷的一個(gè)結(jié)點(diǎn)，然后再一次查詢其后續(xù)；或先找到按某序遍歷的最后一個(gè)結(jié)點(diǎn)，然后再一次查詢其前驅(qū)。這樣，既不用棧也不用遞歸

11、就可以訪問但二叉樹的所有結(jié)點(diǎn)。4、調(diào)試與測(cè)試：4.1、調(diào)試方法與步驟：1程序首先要解決文件的形式問題，即文件中存儲(chǔ)樹的形式，可以給出樹的先序遍歷序列，也可以給出樹的廣義表形式。該程序中，是給出的廣義表的形式。2改程序可以從文件中讀取信息，然后把二叉樹建立起來。3建立二叉樹后，就需要對(duì)二叉樹進(jìn)行線索化。這就必須知道線索二叉樹的定義，才能知道對(duì)二叉樹線索化的大概算法，最終把線索二叉樹通過函數(shù)建立起來。4線索化完成后，還要對(duì)樹經(jīng)行遍歷。若對(duì)樹經(jīng)行普通的中序或后續(xù)遍歷，則對(duì)改程序沒有任何的意義。所以，要充分理解線索二叉樹的好處與優(yōu)勢(shì)，并分析出對(duì)線索二叉樹遍歷的比較快速的算法。5要完成該程序，必須對(duì)樹這

12、種數(shù)據(jù)結(jié)構(gòu)有充分的理解和認(rèn)識(shí)。并且，對(duì)遞歸型的算法有一定的研究。4.2、測(cè)試結(jié)果的分析與討論： 4程序運(yùn)行的運(yùn)行過程為： 以上為中序遍歷結(jié)果！以上為后續(xù)遍歷結(jié)果！5、時(shí)間復(fù)雜度的分析：在遞歸過程中對(duì)每個(gè)結(jié)點(diǎn)做僅做一次訪問，所以對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹，線索化的算法時(shí)間復(fù)雜度為o(n)。6、源程序清單和執(zhí)行結(jié)果struct nodechar ch; /每個(gè)結(jié)點(diǎn)的信息域int ltag; /左孩子指針標(biāo)志域int rtag; /右孩子指針標(biāo)志域node *left; /左孩子node *right; /右孩子node *parent; /雙親結(jié)點(diǎn);線索二叉樹的抽象數(shù)據(jù)類型class threadtre

13、e /線索二叉樹的抽象數(shù)據(jù)類型public:threadtree(); /構(gòu)造函數(shù)bool creatbintree(); /從文件中讀取數(shù)據(jù)并建立二叉樹void creatinthread(); /對(duì)二叉樹進(jìn)行中序線索化void creatinthread(node *current,node *&front);node* infirst(node *current); /尋找中序下的第一個(gè)結(jié)點(diǎn)node* innext(node *current); /尋找中序下當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)void inorder(); /對(duì)中序線索二叉樹進(jìn)行遍歷void creatpostthread();

14、 /對(duì)二叉樹進(jìn)行后序線索化void creatpostthread(node *current,node *&front);node* postfirst(node *current); /需找后序下的第一個(gè)結(jié)點(diǎn)node* postnext(node *current); /尋找后序下當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)void postorder(); /對(duì)后序線索二叉樹進(jìn)行遍歷void deleteintree(); /析構(gòu)中序線索二叉樹void deleteposttree(); /析構(gòu)后續(xù)線索二叉樹7、c程序設(shè)計(jì)總結(jié)在這次設(shè)計(jì)過程中，不僅復(fù)習(xí)課本上所學(xué)知識(shí)，還通過查資料、問同學(xué)學(xué)到了課本上沒有的知識(shí)。從而啟發(fā)我，要想寫好程序，在寫好課本知識(shí)的同時(shí)還需要多讀和專業(yè)有關(guān)的一些書籍，同時(shí)還需要多動(dòng)腦子，盡量把所學(xué)的知識(shí)綜合起來應(yīng)用，力爭寫出完美的程序。除此之外，我還得到了一些有用的教訓(xùn)：寫程序時(shí)必須要細(xì)心，