1、安徽工程大學數 據 結 構課 程 設 計 說 明 書   學生姓名: 劉超學 號：3120702109 學 院:計算機與信息學院專 業:信息與計算科學題 目:二叉樹的創建和遍歷指導教師潘海玉    2014年8月25日目錄1. 需求分析-12. 概要設計-13. 詳細設計-34. 調試分析-95. 課程總結-106. 附錄 -121. 需求分析問題描述：根據運行時輸入的先序序列，創建一棵二叉樹，分別對其 進行先序、中序、后序、層序遍歷，并顯示遍歷結果。void CreateBTree(BTree &

2、;T) /按先序次序輸入，構造二叉樹void PreOrder(BTree T) /遞歸先序遍歷void InOrder(BTree T) /遞歸中序遍歷void PostOrder(BTree T) /遞歸后序遍歷void LevelOrder(BTree T) /層序遍歷void NRPreOrder(BTree bt) /非遞歸先序遍歷void NRInOrder(BTree bt) /非遞歸中序遍歷void NRPostOrder(BTree bt) /非遞歸后序遍歷void main() /二叉樹的建立與遍歷實現2.概要設計此次課程設計遍歷算法的框架圖層序遍歷遍歷算法遞歸遍歷非遞歸遍

3、歷先序遍歷中序遍歷后序遍歷先序遍歷中序遍歷后序遍歷 此次課程設計所用的三組二叉樹 AACBCB DFEEFDGHABFGCDEH本設計所使用的存儲結構：typedef char ElemType;/定義二叉樹結點值的類型為字符型typedef struct bnode/二叉鏈表結構定義ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;typedef struct BTree ptr; int tag;stacknode;3.詳細設計void CreateBTree(BTree &T)/按先序次序輸入，構造二叉鏈表表示的二叉

4、樹T，#表示空樹char ch;ch=getchar(); if(ch='#') T=NULL;/讀入#時，將相應節點指針置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf("創建失敗!");/生成結點空間T->data=ch;CreateBTree(T->lchild);/構造二叉樹的左子樹CreateBTree(T->rchild);/構造二叉樹的右子樹void PreOrder(BTree T)/遞歸先序遍歷if(T)printf("%c ",T->data);

5、PreOrder(T->lchild);PreOrder(T->rchild);void InOrder(BTree T)/遞歸中序遍歷if(T)InOrder(T->lchild);printf("%c ",T->data);InOrder(T->rchild);void PostOrder(BTree T)/遞歸后序遍歷if(T)PostOrder(T->lchild);PostOrder(T->rchild);printf("%c ",T->data);void LevelOrder(BTree T)

6、/層序遍歷BTree QMAX;int front=0,rear=0;BTree p;if(T) /根結點入隊Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /隊頭元素出隊front=(front+1)%MAX; printf("%c ",p->data);if(p->lchild) /左孩子不為空，入隊Qrear=p->lchild;rear=(rear+1)%MAX;if(p->rchild) /右孩子不為空，入隊Qrear=p->rchild;rear=(rear+1)%MAX

7、;void NRPreOrder(BTree bt)/非遞歸先序遍歷BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0) while(p!=NULL) printf("%c",p->data);stacktop=p;/預留p指針在數組中top+;p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild;/*左子樹為空，進右子樹*/void NRInOrder(BTree bt)/非遞歸中序遍歷BTree sta

8、ckMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0)while(p!=NULL) stacktop=p; /預留p指針在數組中top+;p=p->lchild; if (top>0)top-; p=stacktop;printf("%c",p->data); p=p->rchild;/*左子樹為空，進右子樹*/void NRPostOrder(BTree bt)/非遞歸后序遍歷 stacknode sMAX,x; BTree p=bt;int top;if(bt!=NULL)

9、top=0;p=bt;dowhile (p!=NULL) /遍歷左子樹stop.ptr = p; stop.tag = 1; /標記為左子樹top+;p=p->lchild;while (top>0 && stop-1.tag=2)x = s-top;p = x.ptr;printf("%c",p->data); /tag為R，表示右子樹訪問完畢，故訪問根結點 if (top>0)stop-1.tag =2; /遍歷右子樹p=stop-1.ptr->rchild; while (top>0);4.調試分析 一組測試樹 運行

10、時界面 5.課程總結這個程序的代碼較為簡單，可以實現了二叉樹的三種遞歸遍歷算法和三種非遞歸遍歷算法還有層序遍歷算法，想要改進的話可以在選擇功能上下手，建立的時候提示更人性化，對輸入的數據進行有效性驗證，也可以改進為對遍歷算法進行選擇等等。二叉樹這個數據結構幾乎在每一本的數據結構的書都作為重點內容講述，足見其在算法和程序設計界的重要地位。但是，到目前為止，自己還沒有真正體驗到它的威力，可能是學習的還不夠深刻。像二叉樹遍歷的算法，用遞歸的算法只是簡單的幾行代碼，然后就可以實現輸出遍歷次序。對于非遞歸的思想，要用到棧這個數據結構，但是對于二叉樹遍歷問題來說非遞歸要較遞歸復雜。程序一開始總是出現語法錯

11、誤，改了很多次也上網查了相關資料，才最后改為現在可以成功運行的程序。在這個過程中，我體會到開發工程師的感覺了，就是要用挑剔的眼光想問題并且不斷地改進自己的程序。通過這次課程設計逐漸提高了自己的程序設計和調試能力，通過上機實習，嚴整自己設計算法的正確性，學會了有效利用基本調試方法，查找出代碼中的錯誤并且修改。我會繼續我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進步和提高。6.附錄#include <stdlib.h>#include <stdio.h>#include<iostream.h>#define MAX 10 /結點個數不超過10個typ

12、edef char ElemType;/定義二叉樹結點值的類型為字符型typedef struct bnode/二叉鏈表結構定義ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;void CreateBTree(BTree &T)/按先序次序輸入，構造二叉鏈表表示的二叉樹T，#表示空樹char ch;ch=getchar(); if(ch='#') T=NULL;/讀入#時，將相應節點指針置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf("創建失敗

13、!");/生成結點空間T->data=ch;CreateBTree(T->lchild);/構造二叉樹的左子樹CreateBTree(T->rchild);/構造二叉樹的右子樹void PreOrder(BTree T)/遞歸先序遍歷if(T)printf("%c ",T->data);PreOrder(T->lchild);PreOrder(T->rchild);void InOrder(BTree T)/遞歸中序遍歷if(T)InOrder(T->lchild);printf("%c ",T->

14、;data);InOrder(T->rchild);void PostOrder(BTree T)/遞歸后序遍歷if(T)PostOrder(T->lchild);PostOrder(T->rchild);printf("%c ",T->data);void LevelOrder(BTree T)/層序遍歷BTree QMAX;int front=0,rear=0;BTree p;if(T) /根結點入隊Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /隊頭元素出隊front=(front

15、+1)%MAX; printf("%c ",p->data);if(p->lchild) /左孩子不為空，入隊Qrear=p->lchild;rear=(rear+1)%MAX;if(p->rchild) /右孩子不為空，入隊Qrear=p->rchild;rear=(rear+1)%MAX;void NRPreOrder(BTree bt)/非遞歸先序遍歷BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0) while(p!=NULL) printf(

16、"%c",p->data);stacktop=p;/預留p指針在數組中top+;p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild;/*左子樹為空，進右子樹*/void NRInOrder(BTree bt)/非遞歸中序遍歷BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0)while(p!=NULL) stacktop=p; /預留p指針在數組中top+;p=p->lchild; if (top&

17、gt;0)top-; p=stacktop;printf("%c",p->data); p=p->rchild;/*左子樹為空，進右子樹*/typedef struct BTree ptr; int tag;stacknode;void NRPostOrder(BTree bt)/非遞歸后序遍歷 stacknode sMAX,x; BTree p=bt;int top;if(bt!=NULL) top=0;p=bt;dowhile (p!=NULL) /遍歷左子樹stop.ptr = p; stop.tag = 1; /標記為左子樹top+;p=p->lc

18、hild;while (top>0 && stop-1.tag=2)x = s-top;p = x.ptr;printf("%c",p->data); /tag為R，表示右子樹訪問完畢，故訪問根結點 if (top>0)stop-1.tag =2; /遍歷右子樹p=stop-1.ptr->rchild; while (top>0);void main()/主函數BTree T;T=NULL;int select;while(1)printf("nnn請選擇要執行的操作:n");printf("1.創建二叉樹n");printf("2.二叉樹的遞歸遍歷算法（前、中、后）n");printf("3.二叉樹的層次遍歷算法n");printf("4.二叉樹的非遞歸遍歷算法（前、中、后）n"); printf("0.退出n");printf("輸入："); cin>>select;switch(