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

1、9 / 9題 目 : 二叉樹的建立和后序遍歷的演示初始條件： 理論：學(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)具備的功能：（1）選擇樹的存儲(chǔ)結(jié)構(gòu) , 建立二叉樹（2）用遞歸算法和非遞歸算法實(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ì)題目；（2）摘要和關(guān)鍵字（中文和英文） ；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序?qū)崿F(xiàn) 及測(cè)試、不足之處、設(shè)計(jì)體會(huì)等

2、；（4）結(jié)束語；（5）參考文獻(xiàn)。時(shí)間安排： 2007年 7月 2日7日 （第 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ù)元素和分

3、別指向其左、右子樹的兩個(gè)分支構(gòu) 成，則表示二叉樹的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域和左、右指針域。 利用這種結(jié)點(diǎn)結(jié)構(gòu)所得的二叉樹的存儲(chǔ)結(jié)構(gòu)稱之為二叉鏈表。遍歷二叉樹即如何按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均 被訪問一次，而且僅被訪問一次。后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。1.需求分析：1.1先序次序輸入建立二叉樹；1.2后序遍歷二叉樹的遞歸算法；1.3后序遍歷二叉樹的非遞歸算法。2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：/ 二叉樹的鏈表存儲(chǔ)表示typedef struct BiTNode char data;struct

4、BiTNode *lchild,*rchild;/ 左右孩子指針BiTNode,*BiTree;/基本操作的函數(shù)原型說明（部分） Status CreateBiTree（BiTree & T）;/按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹/ 構(gòu)造二叉鏈表表示的二叉樹 T.Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/先序遍歷二叉樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit 一次且僅一次/一旦 Visit() 失敗，則操作失敗。Status

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

6、derTraverse(BiTree T,Status(*Visit)(TElemType e);/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu), Visit 是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。/層次遍歷二叉樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit 一次且僅一次/ 一旦 Visit() 失敗,則操作失敗。3算法設(shè)計(jì)：3.1 先序建立二叉樹這個(gè)函數(shù)主要是生成二叉樹。void CreateBiTree(BiTree *T) / 按先序次序輸入二叉樹中結(jié)點(diǎn)的值(一個(gè)字符) ,空格字符表示空樹 / 構(gòu)造二叉鏈表表示的二叉樹 T.char ch;ch=treeti+;if(ch=NULL) return;if(ch=' ')

7、 *T=NULL;else *T=(BiTree)malloc(sizeof(BiTNode);(*T)->data=ch; / 生成根結(jié)點(diǎn)CreateBiTree(&(*T)->lchild);/ 構(gòu)造左子樹CreateBiTree(&(*T)->rchild);/ 構(gòu)造右子樹3.2 二叉樹的后序遍歷演示算法：3.2.1 二叉樹的后序遍歷遞歸算法 :void PostOrder(BiTree T) if(T) PostOrder(T->lchild);PostOrder(T->rchild);printf("%c ",T-&g

8、t;data);3.2.2 采用”標(biāo)記棧法“的后序遍歷非遞歸算法( while-whilevoid PostOrder_zb(BiTree t) int tag100,top=0; /*tag為標(biāo)記棧 */BiTree stack100;while(t|top) while(t) stack+top=t;tagtop=0; /* 標(biāo)記棧置為 0：第一次訪問 */ t=t->lchild;if(top) 形式）如果if(tagtop=1) printf("%c ",stacktop->data); -top; /* 這個(gè)結(jié)點(diǎn)訪問了兩次，輸出之 */else 否則置

9、棧頂為：第二次訪問 */t=stacktop; /*tagtop=1;t=t->rchild;3.3 源代碼#include <stdio.h>#include <stdlib.h>#include <string.h> char tree30; int ti=0;typedef struct BiTNode char data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree; void CreateBiTree(BiTree *T) char ch;ch=treeti+; if(ch=NULL) ret

10、urn; if(ch=' ') *T=NULL; else *T=(BiTree)malloc(sizeof(BiTNode); (*T)->data=ch;CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild);void PostOrder(BiTree T) if(T) PostOrder(T->lchild);PostOrder(T->rchild);printf("%c ",T->data);void PostOrder_zb(BiTree

11、t) int tag100,top=0;BiTree stack100; 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;mai n() BiTree T=NULL;prin tf("請(qǐng)輸入字符：n");gets(tree);CreateBiTree(&T);prin tf(&q

12、uot;nPostOrder output:");PostOrder(T);prin tf("nPostOrder_zb output:");PostOrder_zb(T);getch();4. 程序運(yùn)行結(jié)果主界面：輸入字符abde e c f運(yùn)行結(jié)果:5. 有關(guān)技術(shù)的討論我這個(gè)程序主要用了二叉鏈表的生成、分別用遞歸與非遞歸的算法實(shí)現(xiàn)了后 序遍歷二叉樹；主要加深了對(duì)二叉鏈表的理解，也使我進(jìn)一步認(rèn)識(shí)了二叉樹的建 立和遍歷（特別是后序遍歷）的算法實(shí)現(xiàn)。6. 設(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ì)是我迄今為止獨(dú)立完成的一個(gè)