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

1、9 / 9題 目 : 二叉樹的建立和后序遍歷的演示初始條件： 理論：學習了數(shù)據(jù)結(jié)構課程，掌握了基本的數(shù)據(jù)結(jié)構和常用的算 法；實踐：計算機技術系實驗室提供計算機及軟件開發(fā)環(huán)境。要求完成的主要任務 : （包括課程設計工作量及其技術要求， 以及說明書撰寫 等具體要求）1、系統(tǒng)應具備的功能：（1）選擇樹的存儲結(jié)構 , 建立二叉樹（2）用遞歸算法和非遞歸算法實現(xiàn)二叉樹的后序遍歷2、數(shù)據(jù)結(jié)構設計；3、主要算法設計；4、編程及上機實現(xiàn)；5、撰寫課程設計報告，包括：（1）設計題目；（2）摘要和關鍵字（中文和英文） ；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構設計、算法設計、程序?qū)崿F(xiàn) 及測試、不足之處、設計體會等

2、；（4）結(jié)束語；（5）參考文獻。時間安排： 2007年 7月 2日7日 （第 18周）7月 2日 查閱資料7月 3日 系統(tǒng)設計，數(shù)據(jù)結(jié)構設計，算法設計7月4日-5 日 編程并上機調(diào)試7月 6日 撰寫報告7月 7日 驗收程序，提交設計報告書。指導教師簽名：2007 年 7 月 6 日系主任（或責任教師）簽名：2007 年 月 日二叉樹的建立和后序遍歷演示計算機 0502 班周其鳳摘要：該程序的主要部分有：建立一個二叉樹以及二叉樹的后序遍歷算法的演示關鍵字：二叉樹，左右子樹，根結(jié)點，后序遍歷0.引言設計不同的結(jié)點結(jié)構可構成不同形式的鏈式存儲結(jié)構。由二叉樹的定義 得知，二叉樹的結(jié)點由一個數(shù)據(jù)元素和分

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

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

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

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

7、 *T=NULL;else *T=(BiTree)malloc(sizeof(BiTNode);(*T)->data=ch; / 生成根結(jié)點CreateBiTree(&(*T)->lchild);/ 構造左子樹CreateBiTree(&(*T)->rchild);/ 構造右子樹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 采用”標記棧法“的后序遍歷非遞歸算法( while-whilevoid PostOrder_zb(BiTree t) int tag100,top=0; /*tag為標記棧 */BiTree stack100;while(t|top) while(t) stack+top=t;tagtop=0; /* 標記棧置為 0：第一次訪問 */ t=t->lchild;if(top) 形式）如果if(tagtop=1) printf("%c ",stacktop->data); -top; /* 這個結(jié)點訪問了兩次，輸出之 */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("請輸入字符：n");gets(tree);CreateBiTree(&T);prin tf(&q

12、uot;nPostOrder output:");PostOrder(T);prin tf("nPostOrder_zb output:");PostOrder_zb(T);getch();4. 程序運行結(jié)果主界面：輸入字符abde e c f運行結(jié)果:5. 有關技術的討論我這個程序主要用了二叉鏈表的生成、分別用遞歸與非遞歸的算法實現(xiàn)了后 序遍歷二叉樹；主要加深了對二叉鏈表的理解，也使我進一步認識了二叉樹的建 立和遍歷（特別是后序遍歷）的算法實現(xiàn)。6. 設計體會做程序很累，也很煩，但做好了之后很有成就感，編程中苦樂并行，其中的 苦樂只有自己親身經(jīng)歷后才能真正體會到。 當你在修正程序中的一個錯誤而使程 序能夠正常運行時， 那其中的快感是不能有語言表達的， 真的能讓你感到其樂無 窮。通過這次的課程設計， 我收獲頗多。這個星期的課程設計使我對 c 語言中的 一個難點指針有了進一步的認識， 以前都搞不清楚指針的真正作用， 現(xiàn)在對它 總算是有了一定程度的理解了。還有就是對二叉樹以及二叉鏈表有了一定的認 識，二叉樹是數(shù)據(jù)結(jié)構中一個基礎且很重要的內(nèi)容， 學好二叉樹的存儲對以后的 學習有很大的幫助； 也使我了解了二叉樹的遍歷算法： 遞歸算法及非遞歸算法的 實現(xiàn)等等。還有最重要的是這次課程設計是我迄今為止獨立完成的一個