1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（二叉樹的建立和后序遍歷的演示）學(xué) 號(hào)： 0120710680326課 程 設(shè) 計(jì)題 目二叉樹的建立和后序遍歷的演示學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)軟件工程專業(yè)班 級(jí)軟件0703班姓 名張偉指導(dǎo)教師夏紅霞2009年7月2日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 張偉 專業(yè)班級(jí)： 軟件0703班 指導(dǎo)教師： 夏紅霞 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 二叉樹的建立和后序遍歷的演示初始條件：理論：學(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ù)要求，以及說(shuō)明書撰寫等具體要求）1、系統(tǒng)應(yīng)具

2、備的功能：（1）選擇樹的存儲(chǔ)結(jié)構(gòu),建立二叉樹（2）用遞歸算法和非遞歸算法實(shí)現(xiàn)二叉樹的后序遍歷（3）二叉樹后序遍歷的演示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ì)等；（4）結(jié)束語(yǔ)；（5）參考文獻(xiàn)。時(shí)間安排： 2009年6月29日2009年7月3日 （第20周）6月29日 查閱資料6月30日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)7月1日 編程并上機(jī)調(diào)試7月2日 撰寫報(bào)告7月3日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書。指導(dǎo)教師簽名： 2

3、009年6月26日 系主任（或責(zé)任教師）簽名： 2009年6月26日 目錄摘要和關(guān)鍵字-11 引言-22 需求分析-23 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-24算法設(shè)計(jì)-35程序?qū)崿F(xiàn)及測(cè)試-56不足之處-127設(shè)計(jì)體會(huì)-128 結(jié)束語(yǔ)-129參考文獻(xiàn)-12摘要：二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。遍歷是對(duì)樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列

4、來(lái)表示。后序遍歷是先按遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根節(jié)點(diǎn)。而訪問(wèn)下一層節(jié)點(diǎn)是，必須記錄上一層的節(jié)點(diǎn)信息，便于訪問(wèn)結(jié)束后退回上一層節(jié)點(diǎn)，所以用棧才存儲(chǔ)節(jié)點(diǎn)信息。 關(guān)鍵字：二叉樹 遞歸后序遍歷 非遞歸后序遍歷 棧1.引言在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆。后序遍歷是二叉樹遍歷的一種。后序遍歷指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹三者中，首先遍歷左子樹，然后遍歷右子樹，最后遍歷訪問(wèn)根結(jié)點(diǎn)，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后

5、遍歷右子樹，最后遍歷根結(jié)點(diǎn)。后序遍歷有遞歸算法和非遞歸算法兩種。棧（stack）在計(jì)算機(jī)科學(xué)中是限定僅在表尾進(jìn)行插入或刪除操作的線形表。它是是一種數(shù)據(jù)結(jié)構(gòu)，它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)）。所以它非常適合存儲(chǔ)二叉樹的節(jié)點(diǎn)信息。2.需求分析 二叉樹一種數(shù)據(jù)結(jié)構(gòu)，用于保存和處理樹狀的數(shù)據(jù)，比如家譜。他的應(yīng)用極為廣泛，因?yàn)楦鶕?jù)數(shù)據(jù)結(jié)構(gòu)的理論，任何復(fù)雜的樹夠可以轉(zhuǎn)換為二叉中并進(jìn)行處理，二叉樹在排序、查找、大規(guī)模數(shù)據(jù)索引方面有很多很多應(yīng)用。而且二叉樹排序是簡(jiǎn)單算法排序中速度最快的。 在二叉樹的一些應(yīng)用

6、中，常常要求在樹中查找具有某種特征的節(jié)點(diǎn)，或者對(duì)樹中全部節(jié)點(diǎn)逐一進(jìn)行某種處理。這就提出了遍歷二叉樹。根據(jù)遍歷的方向的選擇，就有了后序遍歷二叉樹。因此掌握二叉樹的后序遍歷二叉樹算法非常重要，而且高效的后序遍歷算法能夠節(jié)省很多成本。 3. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.1棧的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用線性存儲(chǔ)結(jié)構(gòu)template <class DataType>class Stackprivate:DataType *base; /棧尾DataType *top; /棧頂int stacksize; /棧分配的長(zhǎng)度;3.2二叉樹的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)二叉樹的節(jié)點(diǎn)類型，并作為二叉樹的友元類便于二叉樹進(jìn)行操作templa

7、te <class DataType>class TreeNodeTreeNode():lchild(NULL),rchild(NULL)friend class BiTree<DataType>private:DataType data;TreeNode *lchild,*rchild;二叉樹的存儲(chǔ)結(jié)構(gòu)template <class DataType>class BiTreeprivate:TreeNode<DataType>* root; /樹根DataType temp; /代表元素為空的符號(hào)，便于輸入時(shí)使用;4. 算法設(shè)計(jì)棧的算法：分配一

8、塊空間給棧底，棧頂指針指向最上面元素的上端，當(dāng)棧的空間不夠用時(shí)，追加空間。Stack<DataType>:Stack()if(!(base=(DataType*)malloc(STACK_INIT_SIZE*sizeof(DataType) exit(1);top=base;stacksize=STACK_INIT_SIZE;二叉樹非遞歸后序算法：先訪問(wèn)左子樹，并進(jìn)棧，直到為空，最后一個(gè)元素退棧，訪問(wèn)該節(jié)點(diǎn)，然后訪問(wèn)右子樹，并用一個(gè)標(biāo)志域標(biāo)記下來(lái)，當(dāng)右子樹為空時(shí)，訪問(wèn)該節(jié)點(diǎn)。template <class DataType>void BiTree<DataType

9、>:PosOrderTraverse()Stack<TreeNode<DataType>*> S;TreeNode<DataType>* p;TreeNode<DataType>* r; /使用r節(jié)點(diǎn)表示訪問(wèn)了右子樹替代標(biāo)志域p=root;while(p|!S.StackEmpty()if(p)S.Push(p);p=p->lchild;elseS.GetTop(p);if(p->rchild&&p->rchild!=r)p=p->rchild;S.Push(p);p=p->lchild;els

10、eS.Pop(p);cout<<p->data<<" "r=p;p=NULL;S.DestroyStack();5. 程序?qū)崿F(xiàn)及測(cè)試/*/ 名 稱(Unit Name): Stack.h 棧頭文件/ 作 者(Author ): Hector(張偉)/ 郵 箱(E-mail ): ourys/ 支 持(Support ): / 備 注(Remarks ): /*/#ifndef _STACK_H#define _STACK_H#define STACK_INIT_SIZE 100 /初始棧的最大長(zhǎng)度#define STACKINCREMENT 1

11、0 /每次新增的棧的長(zhǎng)度template <class DataType>class Stackpublic:Stack();void Push(DataType e); /插入為e的新棧頂元素int Pop(DataType &e); /刪除棧頂元素int GetTop(DataType &e); /取出棧頂元素int StackEmpty(); /判斷棧是否為空：空返回void DestroyStack(); /棧被銷毀private:DataType *base; /棧尾DataType *top; /棧頂int stacksize;/*- 構(gòu)造函數(shù)，創(chuàng)建一個(gè)

12、新的空棧 -*/template <class DataType>Stack<DataType>:Stack()if(!(base=(DataType*)malloc(STACK_INIT_SIZE*sizeof(DataType) exit(1);top=base;stacksize=STACK_INIT_SIZE;/*- 插入為e的新棧頂元素 -*/template <class DataType>void Stack<DataType>:Push(DataType e)if(top-base>=stacksize)if(!(base=

13、(DataType*)realloc(base,(stacksize+STACKINCREMENT)*sizeof(DataType) exit(1);top=base+stacksize;stacksize+=STACKINCREMENT;*top+=e;/*- 刪除棧頂元素 -*/template <class DataType>int Stack<DataType>:Pop(DataType &e)if(top=base) return 0;e=*-top;return 1;/*- 取出棧頂元素 -*/template <class DataType

14、>int Stack<DataType>:GetTop(DataType &e)if(top=base) return 0;e=*(top-1);return 1;/*- 判斷棧是否為空：空返回 -*/template <class DataType>int Stack<DataType>:StackEmpty()return top=base? 1:0;/*- 銷毀棧 -*/template <class DataType>void Stack<DataType>:DestroyStack()free(base);#e

15、ndif/*/ 名 稱(Unit Name): BiTree.h 二叉樹頭文件/ 作 者( Author ): Hector(張偉)/ 郵 箱( E-mail ): ourys/ 支 持( Support ): / 備 注( Remarks ): /*/#ifndef _BITREE_H#define _BITREE_H#include "Stack.h"template <class DataType>class BiTree; /友元類引用申明/*- 樹的節(jié)點(diǎn)定義，將BiTree定義為友元類，便于對(duì)其操作 -*/template <class Data

16、Type>class TreeNodeTreeNode():lchild(NULL),rchild(NULL)friend class BiTree<DataType>private:DataType data;TreeNode *lchild,*rchild;/bool tag; /后序遍歷時(shí)用的標(biāo)志域;/*- 二叉樹樹開始 -*/template <class DataType>class BiTreepublic:void CreateBiTree(); /創(chuàng)建根節(jié)點(diǎn)-主過(guò)程void CreateBiTree(TreeNode<DataType>

17、* &p); /創(chuàng)建節(jié)點(diǎn)函數(shù)-子過(guò)程void PosROrderTraverse(); /遞歸-后序遍歷二叉樹-主過(guò)程void PosROrderTraverse(TreeNode<DataType>* p); /遞歸-后序遍歷二叉樹-子過(guò)程void PosOrderTraverse(); /非遞歸-后序遍歷二叉樹private:TreeNode<DataType>* root; /樹根DataType temp; /代表元素為空的符號(hào);/*- 創(chuàng)建根節(jié)點(diǎn)-主過(guò)程-*/template <class DataType>void BiTree<D

18、ataType>:CreateBiTree()cout<<"請(qǐng)輸入代表元素為空的符號(hào):"cin>>temp; if(!(root=(TreeNode<DataType>*)malloc(sizeof(TreeNode<DataType>) exit(1);cout<<"請(qǐng)輸入數(shù)據(jù):"<<endl;CreateBiTree(root);/*-創(chuàng)建節(jié)點(diǎn)函數(shù)-子過(guò)程-*/template <class DataType>void BiTree<DataType>

19、;:CreateBiTree(TreeNode<DataType>* &p)TreeNode<DataType>* px;if(!(px=(TreeNode<DataType>*)malloc(sizeof(TreeNode<DataType>) exit(1);cin>>px->data;if(px->data=temp) p=NULL;free(px);elsep=px;CreateBiTree(px->lchild);CreateBiTree(px->rchild);/*- 遞歸-先序遍歷二叉樹-

20、主過(guò)程 -*/template <class DataType>void BiTree<DataType>:PreROrderTraverse()PreROrderTraverse(root);/*- 遞歸-后序遍歷二叉樹-主過(guò)程 -*/template <class DataType>void BiTree<DataType>:PosROrderTraverse()PosROrderTraverse(root);/*- 遞歸-后序遍歷二叉樹-子過(guò)程 -*/template <class DataType>void BiTree<

21、;DataType>:PosROrderTraverse(TreeNode<DataType>* p)if(p) PosROrderTraverse(p->lchild); PosROrderTraverse(p->rchild); cout<<p->data<<" "/*-非遞歸-后序遍歷二叉樹（沒(méi)有使用標(biāo)志域）-*/template <class DataType>void BiTree<DataType>:PosOrderTraverse()Stack<TreeNode<D

22、ataType>*> S;TreeNode<DataType>* p;TreeNode<DataType>* r; /使用r節(jié)點(diǎn)表示訪問(wèn)了右子樹替代標(biāo)志域p=root;while(p|!S.StackEmpty()if(p)S.Push(p);p=p->lchild;elseS.GetTop(p);if(p->rchild&&p->rchild!=r)p=p->rchild;S.Push(p);p=p->lchild;elseS.Pop(p);cout<<p->data<<" "r=p;p=NULL;S.DestroyStack();/*- 基本測(cè)試文件 - Author:Hector -*/#include<iostrea