叉樹的建立和后序遍歷的演示

1、題目：二叉樹的建立和后序遍歷的演示初始條件：理論：學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，掌握了基本的數(shù)據(jù)結(jié)構(gòu)和常用的算法；實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件開發(fā)環(huán)境。要求完成的主要任務(wù):(包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求)1、系統(tǒng)應(yīng)具備的功能：選擇樹的存儲(chǔ)結(jié)構(gòu)，建立二義樹用遞歸算法和非遞歸算法實(shí)現(xiàn)二義樹的后序遍歷2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程及上機(jī)實(shí)現(xiàn)；5、撰寫課程設(shè)計(jì)報(bào)告，包括：(1) 設(shè)計(jì)題目；摘要和關(guān)鍵字(中文和英文)；正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序?qū)崿F(xiàn)及測(cè)試、不足之處、設(shè)計(jì)體會(huì)等；結(jié)束語；參考文獻(xiàn)。時(shí)間安排：2007年7月2日一7日(第

2、18周)7月2日查閱資料7月3日系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)7月4日-5日編程并上機(jī)調(diào)試7月6日撰寫報(bào)告7月7日驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書。指導(dǎo)教師簽名：2007年7月6日系主任(或責(zé)任教師)簽名：2007年月曰計(jì)算機(jī)0502班周其鳳摘要：該程序的主要部分有：建立一個(gè)二義樹以及二義樹的后序遍歷算法的演示關(guān)鍵字：二義樹，左右子樹，根結(jié)點(diǎn)，后序遍歷0.引言設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由二義樹的定義得知，二義樹的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左、右子樹的兩個(gè)分支構(gòu)成，則表示二義樹的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域和左、右指針域。利用這種結(jié)點(diǎn)結(jié)構(gòu)所得的二義樹的存儲(chǔ)結(jié)構(gòu)稱之為二義

3、鏈表。遍歷二義樹即如何按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。后序遍歷二義樹的操作定義為：(1) 若二義樹為空，則空操作；否則后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。1. 需求分析：1.1先序次序輸入建立二義樹；1.2后序遍歷二義樹的遞歸算法；1.3后序遍歷二義樹的非遞歸算法。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：/二義樹的鏈表存儲(chǔ)表示typedefstructBiTNode(chardata;structBiTNode*lchild,*rchild;/左右孩子指針BiTNode,*BiTree;/基本操作的函數(shù)原型說明(部分)StatusCreateBiTree(BiT

4、ree&T);/按先序次序輸入二義樹中結(jié)點(diǎn)的值(一個(gè)字符)，空格字符表示空樹/構(gòu)造二義鏈表表示的二義樹T.StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二義鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/先序遍歷二義樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。/一旦Visit()失敗，則操作失敗。StatusinOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二義鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/中序遍歷二義樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)V

5、isit一次且僅一次。/一旦Visit()失敗，則操作失敗。StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二義鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/后序遍歷二義樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。/一旦Visit()失敗，則操作失敗。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二義鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/層次遍歷二義樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。/一旦Visit()失敗

6、，則操作失敗。3. 算法設(shè)計(jì)：3.1先序建立二叉樹這個(gè)函數(shù)主要是生成二義樹。voidCreateBiTree(BiTree*T)/按先序次序輸入二義樹中結(jié)點(diǎn)的值(一個(gè)字符)，空格字符表示空樹/構(gòu)造二義鏈表表示的二義樹T.charch;ch=treeti+;if(ch=NULL)return;if(ch='')*T=NULL;else(*T=(BiTree)malloc(sizeof(BiTNode);(*T)->data=ch;/生成根結(jié)點(diǎn)CreateBiTree(&(*T)->lchild);/構(gòu)造左子樹CreateBiTree(&(*T)->

7、;rchild);/構(gòu)造右子樹3.2二叉樹的后序遍歷演示算法：3.2.1二叉樹的后序遍歷遞歸算法：voidPostOrder(BiTreeT)(if(T)(PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->data);3.2.2采用”標(biāo)記棧法“的后序遍歷非遞歸算法(while-while形式)voidPostOrder_zb(BiTreet)(inttag100,top=0;/*tag為標(biāo)記棧*/BiTreestack100;while(t|top)(while(t)(stack+top=t;

8、tagtop=0;/*標(biāo)記棧置為0：第一次訪問*/t=t->lchild;if(top)(if(tagtop=1)(printf("%c”,stacktop->data);-top;/*如果這個(gè)結(jié)點(diǎn)訪問了兩次，輸出之*/else(t=stacktop;/*否則置棧頂為：第二次訪問*/tagtop=1;t=t->rchild;3.3源代碼#include<stdio.h>#include<stdlib.h>#include<string.h>chartree30;intti=0;typedefstructBiTNode(charda

9、ta;structBiTNode*lchild,*rchild;BiTNode,*BiTree;voidCreateBiTree(BiTree*T)(charch;ch=treeti+;if(ch=NULL)return;if(ch='')*T=NULL;else(*T=(BiTree)malloc(sizeof(BiTNode);(*T)->data=ch;CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild);voidPostOrder(BiTreeT)(if(T)(PostOrder

10、(T->lchild);PostOrder(T->rchild);printf("%c",T->data);voidPostOrder_zb(BiTreet)(inttag100,top=0;BiTreestack100;while(t|top)(while(t)(stack+top=t;tagtop=0;t=t->lchild;if(top)(if(tagtop=1)(printf("%c",stacktop->data);-top;else(t=stacktop;tagtop=1;t=t->rchild;main(

11、)(BiTreeT=NULL;printf(-請(qǐng)輸入字符:n");gets(tree);CreateBiTree(&T);printf("nPostOrderoutput:");PostOrder(T);printf("nPostOrder_zboutput:");PostOrder_zb(T);getch();程序運(yùn)行結(jié)果主界面：輸入字符口回區(qū)I運(yùn)行結(jié)果:.C;WIHDO¥S.OsysteM32cMd.exe請(qǐng)輸入字符：4. abdgecfPostOrderoutput:gedfcbaPostOrder_zboutput:g

12、edfcba有關(guān)技術(shù)的討論我這個(gè)程序主要用了二義鏈表的生成、分別用遞歸與非遞歸的算法實(shí)現(xiàn)了后序遍歷二義樹；主要加深了對(duì)二義鏈表的理解，也使我進(jìn)一步認(rèn)識(shí)了二義樹的建立和遍歷（特別是后序遍歷）的算法實(shí)現(xiàn)。5. 設(shè)計(jì)體會(huì)做程序很累，也很煩，但做好了之后很有成就感，編程中苦樂并行，其中的苦樂只有自己親身經(jīng)歷后才能真正體會(huì)到。當(dāng)你在修正程序中的一個(gè)錯(cuò)誤而使程序能夠正常運(yùn)行時(shí)，那其中的快感是不能有語言表達(dá)的，真的能讓你感到其樂無窮。通過這次的課程設(shè)計(jì)，我收獲頗多。這個(gè)星期的課程設(shè)計(jì)使我對(duì)c語言中的一個(gè)難點(diǎn)一指針有了進(jìn)一步的認(rèn)識(shí)，以前都搞不活楚指針的真正作用,現(xiàn)在對(duì)它總算是有了一定程度的理解了。還有就是對(duì)二義樹以及二義鏈表有了一定的認(rèn)識(shí)，二義樹是數(shù)據(jù)結(jié)構(gòu)中一個(gè)基礎(chǔ)且很重要的內(nèi)容，學(xué)好二義樹的存儲(chǔ)對(duì)以后的學(xué)習(xí)有很大的幫助；也使我了解了二義樹的遍歷算法：遞歸算法及非遞歸算法的實(shí)現(xiàn)等等。還有最重要的是這次課程設(shè)計(jì)是我迄