北京理工大學數(shù)據(jù)結(jié)構(gòu)實驗報告3

1、數(shù)據(jù)結(jié)構(gòu)與算法統(tǒng)計實驗報告實驗三一、實驗目的熟悉VC環(huán)境，學會使用C+解決關(guān)于二叉樹的問題。在上機、調(diào)試的過程中，加強對二叉樹的理解和運用。二、實驗內(nèi)容遍歷二叉樹。請輸入一棵二叉樹的擴展的前序序列，經(jīng)過處理后生成一棵二叉樹，然后對于該二叉樹輸出前序、中序和后序遍歷序列。三、程序設(shè)計1、概要設(shè)計為實現(xiàn)上述程序功能，首先需要二叉樹的抽象數(shù)據(jù)結(jié)構(gòu)。二叉樹的抽象數(shù)據(jù)類型定義為：ADT BinaryTree 數(shù)據(jù)對象D：D 數(shù)據(jù)關(guān)系R：D= ，則R= ，稱BinaryTreeD ，則R=H，H在Droot，它在關(guān)系H若D-root，則存在D-root=D1,DrD1Dr =；D1D1D1H1HDrDrx

2、r，H，且存在上的關(guān)系HrH；H=,H1,Hr；（4）(D1,H1)是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,Hr)是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鳎篊reatBiTree(BiTree &T)操作結(jié)果：按先序次序建立二叉鏈表表示的二叉樹T PreOrderTraverse(BiTree T,int (*visit)(char e)初始條件：二叉樹T 已經(jīng)存在，visit 是對結(jié)點操作的應用函數(shù)操作結(jié)果：先序遍歷二叉樹T ，對每個結(jié)點調(diào)用visit visit（）失敗，則操作失敗。InOrderTraverse(BiTree T,int (*visit)(char e

3、)初始條件：二叉樹T 已經(jīng)存在，visit 是對結(jié)點操作的應用函數(shù)操作結(jié)果：中序遍歷二叉樹T ，對每個結(jié)點調(diào)用visit visit（）失敗，則操作失敗。PostOrderTraverse(BiTree T,int (*visit)(char e)初始條件：二叉樹T 已經(jīng)存在，visit 是對結(jié)點操作的應用函數(shù)操作結(jié)果：后序遍歷二叉樹T ，對每個結(jié)點調(diào)用visit visit（）失敗，則操作失敗。 ADT BinaryTree2主程序流程主程序先調(diào)用 CreatBiTree(BiTree &T)函數(shù)，根據(jù)輸入的先序序列構(gòu)造出一棵二叉樹，再依次調(diào)用PreOrderTraverse(BiTree

4、T,int (*visit)(char e)，InOrderTraverse(BiTree T,int (*visit)(char e)，PostOrderTraverse(BiTree T,int (*visit)(char 函數(shù)，對該二叉樹進行先序、中序、后序遍歷并輸出結(jié)果。模塊調(diào)用關(guān)系由主函數(shù)調(diào)用創(chuàng)建模塊，再調(diào)用計算模塊，由計算模塊將結(jié)果輸出。流程圖開始開始按照先序序列構(gòu)造出一棵二叉樹先序遍歷并輸出中序遍歷并輸出后序遍歷并輸出結(jié)束2、詳細設(shè)計數(shù)據(jù)類型設(shè)計typedef struct BiTNode/二叉樹結(jié)構(gòu)類型char data;/建立數(shù)據(jù)域struct BiTNode *lchild

5、,*rchild;/建立左指針和右指針BiTNode,*BiTree;操作算法設(shè)計int CreatBiTree(BiTree &T)/按先序次序建立二叉鏈表表示的二叉樹Tchar ch; scanf(%c,&ch); if(ch= )3elseT=NULL;T=(BiTNode *)malloc(sizeof(BiTNode); if(!T)exit (OVERFLOW);T-data=ch; CreatBiTree(T-lchild); CreatBiTree(T-rchild);return 1;int visit(char e)/對數(shù)據(jù)進行輸出printf(%c,e); return

6、1;int PreOrderTraverse(BiTree T,int (*visit)(char e)/先序遍歷二叉樹T 的遞歸算法if(T)elseif(visit(T-data)if(PreOrderTraverse(T-lchild,visit) if(PreOrderTraverse(T-rchild,visit) return 1;return 0;return 1;int InOrderTraverse(BiTree T,int (*visit)(char e)/中序遍歷二叉樹T 的遞歸算法if(T)if(InOrderTraverse(T-lchild,visit) if(vi

7、sit(T-data)4elsereturn 1;if(InOrderTraverse(T-rchild,visit) return 1;return 0;int PostOrderTraverse(BiTree T,int (*visit)(char e)/后序遍歷二叉樹T 的遞歸算法if(T)elseif(PostOrderTraverse(T-lchild,visit) if(PostOrderTraverse(T-rchild,visit)if(visit(T-data) return 1;return 0;return 1;主函數(shù)設(shè)計void main()/主函數(shù)BiTree T;C

8、reatBiTree(T); 按先序次序建立二叉鏈表表示的二叉樹printf(PreOrderTraverse:n);PreOrderTraverse(T,visit); printf(n);printf(InOrderTraverse:n); InOrderTraverse(T,visit); printf(n);printf(PostOrderTraverse:n); PostOrderTraverse(T,visit); printf(n);四、程序調(diào)試分析調(diào)試時，輸入時有時候有輸出有時候沒輸。向老師請教，老師說是比如abc，則b 下完整的樹。進行先序遍歷時，訪問左子樹后程序即結(jié)束，不訪

9、問根結(jié)點和右子樹。后來發(fā)現(xiàn)是return 0return 1的問題。遞歸時return return 5到原位置繼續(xù)執(zhí)行。以后應加強對于基礎(chǔ)知識的理解。五、程序運行結(jié)果測試一：ABCDE GFPreOrderTraverse: ABCDEGFInOrderTraverse: CBEGDFAPostOrderTraverse: CGEFDBA測試二：12345 76PreOrderTraverse: InOrderTraverse: PostOrderTraverse:六 、 程 序 清 單 #include #include #include #define OVERFLOWtypedef s

10、truct BiTNode/二叉樹結(jié)構(gòu)類型char data;/建立數(shù)據(jù)域struct BiTNode *lchild,*rchild;/建立左指針和右指針BiTNode,*BiTree;int CreatBiTree(BiTree &T);/按先序次序建立二叉鏈表表示的二叉樹T int visit(char e);/對數(shù)據(jù)進行輸出int PreOrderTraverse(BiTree T,int (*visit)(char e);/ int InOrderTraverse(BiTree T,int (*visit)(char e);/ /序遍歷二叉樹T 序遍歷二叉樹T 的遞歸算法int Po

11、stOrderTraverse(BiTree T,int (*visit)(char e);/ /序遍歷二叉樹T 的遞歸算法void main()/主函數(shù)BiTree T;CreatBiTree(T); 按先序次序建立二叉鏈表表示的二叉樹printf(PreOrderTraverse:n);6PreOrderTraverse(T,visit); printf(n);printf(InOrderTraverse:n); InOrderTraverse(T,visit); printf(n);printf(PostOrderTraverse:n); PostOrderTraverse(T,visi

12、t); printf(n);int CreatBiTree(BiTree &T)/按先序次序建立二叉鏈表表示的二叉樹Tchar ch; scanf(%c,&ch); if(ch= )elseT=NULL;T=(BiTNode *)malloc(sizeof(BiTNode); if(!T)exit (OVERFLOW);T-data=ch; CreatBiTree(T-lchild); CreatBiTree(T-rchild);return 1;int visit(char e)/對數(shù)據(jù)進行輸出printf(%c,e); return 1;int PreOrderTraverse(BiTre

13、e T,int (*visit)(char e)/ /序遍歷二叉樹T 的遞歸算法if(T)if(visit(T-data)if(PreOrderTraverse(T-lchild,visit)7elsereturn 1;if(PreOrderTraverse(T-rchild,visit) return 1;return 0;int InOrderTraverse(BiTree T,int (*visit)(char e)/ /序遍歷二叉樹T 的遞歸算法if(T)elseif(InOrderTraverse(T-lchild,visit) if(visit(T-data)if(InOrderTraverse(T-rchild,visit) return 1;retur