北理工數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三學(xué)院： 班級(jí)： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?1. 通過(guò)實(shí)驗(yàn)實(shí)踐、鞏固二叉樹(shù)和隊(duì)列的相關(guān)操作；2. 熟悉VC環(huán)境，加強(qiáng)編程、調(diào)試的練習(xí)；3. 用C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)和隊(duì)列的抽象數(shù)據(jù)類(lèi)型；4. 用C語(yǔ)言編寫(xiě)遞歸函數(shù)，實(shí)現(xiàn)生成二叉樹(shù)和遍歷二叉樹(shù)；5. 用隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層次遍歷；6. 理論知識(shí)與實(shí)際問(wèn)題相結(jié)合，利用上述基本操作用多種方式遍歷二叉樹(shù)。二、實(shí)驗(yàn)內(nèi)容 1、遍歷二叉樹(shù)。請(qǐng)輸入一棵二叉樹(shù)的擴(kuò)展的前序序列，經(jīng)過(guò)處理后生成一棵二叉樹(shù)，然后對(duì)于該二叉樹(shù)輸出前序、中序和后序遍歷序列。2、選做：按層次遍歷二叉樹(shù)。三、程序設(shè)計(jì) 1、概要設(shè)計(jì)為實(shí)現(xiàn)上述

2、程序功能，需要建立抽象數(shù)據(jù)類(lèi)型：二叉樹(shù)和隊(duì)列。（1） 、定義抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義為：ADT BinaryTree 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=，則R=，稱(chēng)BinaryTree為空二叉樹(shù)； 若D，則R=H，H是如下二元關(guān)系； （1）在D中存在惟一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)； （2）若D-root，則存在D-root=D1,Dr，且D1Dr =； （3）若D1，則D1中存在惟一的元素x1，<root,x1>H，且存在D1上的關(guān)系H1 H；若Dr，則Dr中存在惟一的元素xr，<root,xr>H，且存在上

3、的關(guān)系Hr H；H=<root,x1>,<root,xr>,H1,Hr； （4）(D1,H1)是一棵符合本定義的二叉樹(shù)，稱(chēng)為根的左子樹(shù)；(Dr,Hr)是一棵符合本定義的二叉樹(shù)，稱(chēng)為根的右子樹(shù)。基本操作：CreatBiTree(BiTree &T)操作結(jié)果：按先序次序建立二叉鏈表表示的二叉樹(shù)TPreOrderTraverse(BiTree T)初始條件：二叉樹(shù)T已經(jīng)存在 操作結(jié)果：先序遍歷二叉樹(shù)T ，對(duì)每個(gè)結(jié)點(diǎn)輸出其數(shù)據(jù)元素InOrderTraverse(BiTree T)初始條件：二叉樹(shù)T已經(jīng)存在 操作結(jié)果：中序遍歷二叉樹(shù)T ，對(duì)每個(gè)結(jié)點(diǎn)輸出其數(shù)據(jù)元素PostO

4、rderTraverse(BiTree T)初始條件：二叉樹(shù)T已經(jīng)存在 操作結(jié)果：后序遍歷二叉樹(shù)T ，對(duì)每個(gè)結(jié)點(diǎn)輸出其數(shù)據(jù)元素LevelOrderTraverse(BiTree T)初始條件：二叉樹(shù)T已經(jīng)存在 操作結(jié)果：層次遍歷二叉樹(shù)T ，對(duì)每個(gè)結(jié)點(diǎn)輸出其數(shù)據(jù)元素 ADT BinaryTree隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義為：ADT Stack 數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,3,n,n0數(shù)據(jù)關(guān)系：R1= <ai-1,ai>|aiD,i=1,2,n 約定其中a1端為隊(duì)列頭，an端為隊(duì)列尾基本操作：InitQueue(&Q) 功能：構(gòu)造一個(gè)空隊(duì)列Q。EnQueue

5、(&Q, e ) 功能：將元素e插入Q的隊(duì)尾。DeQueue(&Q,&e) 功能：刪除Q的隊(duì)頭元素。ADT Stack主程序流程主程序先調(diào)用CreatBiTree(BiTree &T)函數(shù)，根據(jù)輸入的先序序列構(gòu)造出一棵二叉樹(shù)，再依次調(diào)用PreOrderTraverse(BiTree T)，InOrderTraverse(BiTree T)，PostOrderTraverse(BiTree T)，LevelOrderTraverse(BiTree T)函數(shù)對(duì)該二叉樹(shù)進(jìn)行先序、中序、后序、層次遍歷并輸出結(jié)果。模塊調(diào)用關(guān)系由主函數(shù)調(diào)用生成二叉樹(shù)模塊，調(diào)用先序、中序、后

6、序遍歷模塊依次輸出，調(diào)用層次遍歷模塊，調(diào)用隊(duì)列的建立、插入、刪除等模塊，完成層次遍歷并輸出。流程圖生成二叉樹(shù)CreatBiTree生成二叉樹(shù)CreatBiTree開(kāi)始生成二叉樹(shù)CreatBiTree先序遍歷并輸出PreOrderTraverse中序遍歷并輸出InOrderTraverse后序遍歷并輸出PostOrderTraverse層次遍歷并輸出LevelOrderTraverse結(jié)束 2、詳細(xì)設(shè)計(jì) (1)、宏定義#define MAXSIZE 100 /最大隊(duì)列長(zhǎng)度#define OK 1 /操作無(wú)誤#define ERROR 0 /操作有誤#define OVERFLOW -2 /溢出（

7、2）、抽象數(shù)據(jù)類(lèi)型定義typedef int Status; /函數(shù)類(lèi)型typedef char ElemType; /二叉樹(shù)的元素類(lèi)型typedef struct BiTNode/定義二叉樹(shù)ElemType data; struct BiTNode * lchild, * rchild; /左孩子和右孩子的指針BiTNode, * BiTree;typedef BiTree QElemType; /隊(duì)列的元素類(lèi)型typedef struct/定義隊(duì)列QElemType * base; /初始化時(shí)分配存儲(chǔ)空間的基址int front; /隊(duì)頭指針，指向隊(duì)頭元素int rear; /隊(duì)尾指針，指

8、向隊(duì)尾元素的下一個(gè)位置SqQueue;（3）、操作算法程序?qū)崿F(xiàn)：Status InitQueue(SqQueue &Q ) /構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType * )malloc (MAXSIZE * sizeof (QElemType);if ( !Q.base ) exit (OVERFLOW); /存儲(chǔ)分配失敗Q.front = Q.rear = 0;return OK;/InitQueueStatus EnQueue( SqQueue &Q, QElemType e )/將元素e插入隊(duì)尾if ( (Q.rear+1)%MAXSIZE=Q.front )

9、 return ERROR ; /隊(duì)滿Q.baseQ.rear = e ; /將元素e插入隊(duì)尾Q.rear = (Q.rear+1)%MAXSIZE; /修改隊(duì)尾指針return OK;/EnQueueStatus DeQueue( SqQueue &Q, QElemType &e ) /刪除隊(duì)頭元素，用e返回其值，并返回OK；否則返回ERRORif ( Q.rear=Q.front ) return ERROR ; /隊(duì)空e = Q.baseQ.front ; / 取隊(duì)頭元素 eQ.front = (Q.front+1)%MAXSIZE; /修改隊(duì)頭指針return OK;/

10、EnQueueint CreateBiTree(BiTree &T)/按先序次序建立二叉鏈表表示的二叉樹(shù)TElemType ch;scanf ("%c",&ch);if ( ch =' ') T=NULL; / 若ch=' ' 則表示空子樹(shù) else if ( ! (T=( BiTNode * ) malloc( sizeof( BiTNode ) ) ) )exit(OVERFLOW);T->data = ch; / 建立（根）結(jié)點(diǎn) CreateBiTree(T->lchild); / 遞歸構(gòu)造左子樹(shù)鏈表Crea

11、teBiTree(T->rchild); / 遞歸構(gòu)造右子樹(shù)鏈表 return OK;/CreateBiTreevoid PreOrderTraverse( BiTree T) /先序遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)if (T) /若二叉樹(shù)不為空 printf("%c",T->data); /訪問(wèn)根結(jié)點(diǎn) PreOrderTraverse(T->lchild); /先序遍歷T的左子樹(shù) PreOrderTraverse(T->rchild); /先序遍歷T的右子樹(shù) /PreOrderTraversevoid InOrderTraverse( BiTree T

12、) /中序遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)if (T) /若二叉樹(shù)不為空 InOrderTraverse(T->lchild); /中序遍歷T的左子樹(shù) printf("%c",T->data); /訪問(wèn)根結(jié)點(diǎn) InOrderTraverse(T->rchild); /中序遍歷T的右子樹(shù) /InOrderTraversevoid PostOrderTraverse( BiTree T) /后序遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)if (T) /若二叉樹(shù)不為空 PostOrderTraverse(T->lchild); /后序遍歷T的左子樹(shù) PostOrderTra

13、verse(T->rchild); /后序遍歷T的右子樹(shù)printf("%c",T->data); /訪問(wèn)根結(jié)點(diǎn) /PostOrderTraversevoid LevelOrderTraverse(BiTree T)/層次遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)SqQueue q;BiTree p;InitQueue(q);if(T) EnQueue(q,T); /隊(duì)頭元素進(jìn)隊(duì)列while(!(q.front=q.rear)DeQueue(q,p); printf("%c",p->data); /輸出隊(duì)頭元素if(p->lchild) EnQ

14、ueue(q,p->lchild); /左子樹(shù)進(jìn)隊(duì)列if(p->rchild) EnQueue(q,p->rchild); /右子樹(shù)進(jìn)隊(duì)列四、程序調(diào)試分析 1. 程序中用到的未定義的字符串要進(jìn)行宏定義；2. 輸入二叉樹(shù)時(shí)要注意用空格代替子樹(shù)為空；3. 二叉樹(shù)的層次遍歷可以借助隊(duì)列來(lái)實(shí)現(xiàn)；4. 先定義二叉樹(shù)，再定義隊(duì)列元素的數(shù)據(jù)結(jié)構(gòu)為二叉樹(shù)類(lèi)型，順序顛倒會(huì)出錯(cuò)。五、 用戶使用說(shuō)明 1. 本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：實(shí)驗(yàn)三.exe，雙擊打開(kāi)文件。2. 進(jìn)入程序后，根據(jù)提示輸入先序遍歷的二叉樹(shù)，按Enter鍵結(jié)束。3. 屏幕輸出以上二叉樹(shù)的先序、中序、后序、層次遍

15、歷結(jié)果，按任意鍵退出程序。六、程序運(yùn)行結(jié)果測(cè)試一： 測(cè)試二：測(cè)試三：七、程序清單#include "stdio.h"#include "stdlib.h"#define MAXSIZE 100 /最大隊(duì)列長(zhǎng)度#define OK 1 /操作無(wú)誤#define ERROR 0 /操作有誤#define OVERFLOW -2 /溢出typedef int Status; /函數(shù)類(lèi)型typedef char ElemType; /二叉樹(shù)的元素類(lèi)型typedef struct BiTNode/定義二叉樹(shù)ElemType data; struct BiTNode

16、 * lchild, * rchild; /左孩子和右孩子的指針BiTNode, * BiTree;typedef BiTree QElemType; /隊(duì)列的元素類(lèi)型typedef struct/定義隊(duì)列QElemType * base; /初始化時(shí)分配存儲(chǔ)空間的基址int front; /隊(duì)頭指針，指向隊(duì)頭元素int rear; /隊(duì)尾指針，指向隊(duì)尾元素的下一個(gè)位置SqQueue;Status InitQueue(SqQueue &Q ) /構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType * )malloc (MAXSIZE * sizeof (QElemType);if (

17、!Q.base ) exit (OVERFLOW); /存儲(chǔ)分配失敗Q.front = Q.rear = 0;return OK;/InitQueueStatus EnQueue( SqQueue &Q, QElemType e )/將元素e插入隊(duì)尾if ( (Q.rear+1)%MAXSIZE=Q.front ) return ERROR ; /隊(duì)滿Q.baseQ.rear = e ; /將元素e插入隊(duì)尾Q.rear = (Q.rear+1)%MAXSIZE; /修改隊(duì)尾指針return OK;/EnQueueStatus DeQueue( SqQueue &Q, QElem

18、Type &e ) /刪除隊(duì)頭元素，用e返回其值，并返回OK；否則返回ERRORif ( Q.rear=Q.front ) return ERROR ; /隊(duì)空e = Q.baseQ.front ; / 取隊(duì)頭元素 eQ.front = (Q.front+1)%MAXSIZE; /修改隊(duì)頭指針return OK;/EnQueueint CreateBiTree(BiTree &T)/按先序次序建立二叉鏈表表示的二叉樹(shù)TElemType ch;scanf ("%c",&ch);if ( ch =' ') T=NULL; / 若ch=&#

19、39; ' 則表示空子樹(shù) else if ( ! (T=( BiTNode * ) malloc( sizeof( BiTNode ) ) ) )exit(OVERFLOW);T->data = ch; / 建立（根）結(jié)點(diǎn) CreateBiTree(T->lchild); / 遞歸構(gòu)造左子樹(shù)鏈表CreateBiTree(T->rchild); / 遞歸構(gòu)造右子樹(shù)鏈表 return OK;/CreateBiTreevoid PreOrderTraverse( BiTree T) /先序遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)if (T) /若二叉樹(shù)不為空 printf("

20、%c",T->data); /訪問(wèn)根結(jié)點(diǎn) PreOrderTraverse(T->lchild); /先序遍歷T的左子樹(shù) PreOrderTraverse(T->rchild); /先序遍歷T的右子樹(shù) /PreOrderTraversevoid InOrderTraverse( BiTree T) /中序遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)if (T) /若二叉樹(shù)不為空 InOrderTraverse(T->lchild); /中序遍歷T的左子樹(shù) printf("%c",T->data); /訪問(wèn)根結(jié)點(diǎn) InOrderTraverse(T->rchild); /中序遍歷T的右子樹(shù) /InOrderTraversevoid PostOrderTraverse( BiTree T) /后序遍歷以T為根結(jié)點(diǎn)指針的二叉樹(shù)if (T) /若二叉樹(shù)不為空 PostOrderTraverse(T->lchild); /后序遍歷T的左子樹(shù) PostOrderTraverse(T->rchild); /后序遍歷T的右子樹(shù)printf("%c",T->data); /訪問(wèn)根結(jié)點(diǎn) /PostO