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

《二叉樹的建立和后序遍歷的演示.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、設(shè)計、算法設(shè)計、程序?qū)崿F(xiàn)及測試、不足之處、設(shè)計體會等；（4）結(jié)束語；（5）參考文獻。時間安排：2007年7月2日－7日（第18周）7月2日查閱資料7月3日系統(tǒng)設(shè)計，數(shù)據(jù)結(jié)構(gòu)設(shè)計，算法設(shè)計7月4日-5日編程并上機調(diào)試7月6日撰寫報告7月7日驗收程序，提交設(shè)計報告書。指導(dǎo)教師簽名：2007年7月6日系主任（或責(zé)任教師）簽名：2007年月日二叉樹的建立和后序遍歷演示周其鳳計算機0502班摘要：該程序的主要部分有：建立一個二叉樹以及二叉樹的后序遍歷算法的演示。關(guān)鍵字：二叉樹，左右子樹，根結(jié)點，后序遍歷0.引言設(shè)計不同的

3、結(jié)點結(jié)構(gòu)可構(gòu)成不同形式的鏈式存儲結(jié)構(gòu)。由二叉樹的定義得知，二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左、右子樹的兩個分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點至少包含三個域：數(shù)據(jù)域和左、右指針域。利用這種結(jié)點結(jié)構(gòu)所得的二叉樹的存儲結(jié)構(gòu)稱之為二叉鏈表。遍歷二叉樹即如何按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。1.需求分析：1.1先序次序輸入建立二叉樹；1.2后序遍歷二叉樹的

4、遞歸算法；1.3后序遍歷二叉樹的非遞歸算法。2．?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計：//-------二叉樹的鏈表存儲表示-------typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;//-------基本操作的函數(shù)原型說明（部分）---------StatusCreateBiTree(BiTree&T);//按先序次序輸入二叉樹中結(jié)點的值（一個字符），空格字符表示空樹//構(gòu)造二叉鏈表表示的二叉樹T.StatusP

5、reOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對結(jié)點操作的應(yīng)用函數(shù)。//先序遍歷二叉樹T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦Visit()失敗，則操作失敗。StatusinOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對結(jié)點操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//

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

7、歷二叉樹T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦Visit()失敗，則操作失敗。3．算法設(shè)計：3.1先序建立二叉樹這個函數(shù)主要是生成二叉樹。voidCreateBiTree(BiTree*T){//按先序次序輸入二叉樹中結(jié)點的值（一個字符），空格字符表示空樹//構(gòu)造二叉鏈表表示的二叉樹T.charch;ch=tree[ti++];if(ch==NULL)return;if(ch=='')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->da

8、ta=ch;//生成根結(jié)點CreateBiTree(&(*T)->lchild);//構(gòu)造左子樹CreateBiTree(&(*T)->rchild);//構(gòu)造右子樹}}3.2二叉樹的后序遍歷演示算法：3.2.1二叉樹的后序遍歷遞歸算法:voidPostOrder(BiTreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);prin