數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告之二叉樹(shù)(終極版本)

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告姓名系別班級(jí)學(xué)號(hào)實(shí)驗(yàn)日期指導(dǎo)教師實(shí)驗(yàn)成績(jī)周娟信息學(xué)院電子2班102002072012-4-26王政霞實(shí)驗(yàn)三二叉樹(shù)需求分析一、實(shí)驗(yàn)?zāi)康?、掌握二叉樹(shù)的基本運(yùn)算和遍歷算法的實(shí)現(xiàn)2、掌握樹(shù)形結(jié)構(gòu)的特點(diǎn)，二叉樹(shù)的存儲(chǔ)方式以及相應(yīng)操作二、實(shí)驗(yàn)內(nèi)容按先序遍歷序列建立二叉樹(shù)的二叉鏈表，已知先序序列為(F表示空格)：ABCFFDEFGFFFFFF。并寫(xiě)一個(gè)函數(shù)treenodes()統(tǒng)計(jì)該二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。如果有可能，寫(xiě)一個(gè)輸出函數(shù)treeprint()用樹(shù)形結(jié)構(gòu)打印出該二叉樹(shù)。概要設(shè)計(jì)1>抽象數(shù)據(jù)結(jié)構(gòu)類型二叉樹(shù)的定義:ADTBinaryTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=Φ，則R=Φ,稱BinaryTree為空二叉樹(shù)；若D≠Φ，則R={H},H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2）若D-{root}≠Φ，則存在D-{root}={D1，Dr}，且D1∩Dr=Φ；（3）若D1≠Φ，則D1中存在唯一的元素X1，<root，X1>屬于H，且存在Dr上的關(guān)系Hr屬于H；H={<root，X1>，<root，Xr>,H1,Hr};(4)(D，{H1}）是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，(Dr,{Hr}）是一棵符合本定義的二叉樹(shù)，稱為根的右子數(shù)?；静僮鳎篒nitBiTree(&T)操作結(jié)果：構(gòu)造空二叉樹(shù)T。DestroyBiTree(&T)初始條件：二叉樹(shù)T已存在。操作結(jié)果：銷毀二叉樹(shù)T。GreateBiTree(&T,definition)初始條件：definition給出二叉樹(shù)T的定義。操作結(jié)果：按definition構(gòu)造二叉樹(shù)T。ClearBiTree{&T};初始條件：二叉樹(shù)T存在。操作結(jié)果：將二叉樹(shù)t清空。BiTreeEmpty(T)初始條件：二叉樹(shù)T存在。操作結(jié)果：若T為空二叉樹(shù)，則返回TRUE,否則返回FALSE.BiTreeDepth(T)初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的深度。Root(T)初始條件：二叉樹(shù)T已存在。操作結(jié)果：返回T的根。LeftBiTree&（T，e)初始條件：二叉樹(shù)T存在，e是T中某個(gè)節(jié)點(diǎn)。操作結(jié)果：返回e的左孩子。若e無(wú)左孩子，則返回“空”。RightBiTree(T，e)初始條件：二叉樹(shù)T已存在，e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的右孩子。若e無(wú)右孩子，則返回“空”。PreOrderTraverse（T,Visit（））初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：先序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。InOrderTraverse（T,Visit（））初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：中序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。PostOrderTraverse（T,Visit（））初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：后序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。LevelOrderTraverse（T,Visit（））初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：層序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。}ADTBinaryTree2>各程序模塊之間的層次關(guān)系圖：主程序模塊主程序模塊從鍵盤輸入二叉樹(shù)的先序序列從鍵盤輸入二叉樹(shù)的先序序列 調(diào)用遞歸先序遍歷調(diào)用遞歸先序遍歷函數(shù)模塊實(shí)現(xiàn)先序遍歷調(diào)用遞歸中序遍歷函數(shù)模塊實(shí)現(xiàn)中序遍歷調(diào)用遞歸中序遍歷函數(shù)模塊實(shí)現(xiàn)中序遍歷調(diào)用遞歸后序遍歷函數(shù)模塊實(shí)現(xiàn)后序遍歷調(diào)用遞歸后序遍歷函數(shù)模塊實(shí)現(xiàn)后序遍歷調(diào)用層次遍歷函數(shù)判斷結(jié)點(diǎn)數(shù)調(diào)用層次遍歷函數(shù)判斷結(jié)點(diǎn)數(shù)詳細(xì)設(shè)計(jì)#include"stdio.h"#include"stdlib.h"#include"malloc.h"1、二叉樹(shù)的定義typedefcharTElemType;typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode;2、隊(duì)列的定義typedefstructQNode{ BiTNodedata; structQNode*next;}Queue;typedefstruct//隊(duì)列的頭指針和尾指針{Queue*front; Queue*rear;}LinkQueue;intJT=0;3、先序建立二叉樹(shù)BiTNode*CreateBiTree(){TElemTypech; BiTNode*T; scanf("%c",&ch); if(ch=='') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(0); T->data=ch; JT++; T->lchild=CreateBiTree();//建立左子樹(shù) T->rchild=CreateBiTree();//建立右子樹(shù) } returnT;}4、初始化隊(duì)列intInitQueue(LinkQueue*Q){ Q->front=Q->rear=(Queue*)malloc(sizeof(Queue)); if(!Q->front) exit(0); Q->front->next=NULL; return1;}intEnQueue(LinkQueue*Q,BiTNodee)//向隊(duì)列中插入元素{ Queue*p; p=(Queue*)malloc(sizeof(Queue)); if(!p) exit(0); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return1;//插入成功返回1}5、出隊(duì)intDeQueue(LinkQueue*Q,BiTNode*e){ Queue*p; if(Q->front==Q->rear)//隊(duì)列為空 return0; p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; free(p); return1;}6、判斷隊(duì)列是否為空隊(duì)列intEmptyQueue(LinkQueue*Q){ if(Q->rear==Q->front) return1; else return0;}7、隊(duì)列的層次遍歷voidLevelTraverse(BiTNode*T){ LinkQueueQ; BiTNode*p; InitQueue(&Q); EnQueue(&Q,*T); p=T; while(!EmptyQueue(&Q)) {DeQueue(&Q,p); printf("%c",p->data); if(p->lchild) EnQueue(&Q,*p->lchild); if(p->rchild) EnQueue(&Q,*p->rchild); }}8、遞歸先序遍歷voidPreOrderTraverse(BiTNode*btn){if(btn!=NULL){printf("%c",btn->data);PreOrderTraverse(btn->lchild);PreOrderTraverse(btn->rchild);}}9、遞歸中序遍歷voidInOrderTraverse(BiTNode*btn){if(btn!=NULL){InOrderTraverse(btn->lchild);printf("%c",btn->data);InOrderTraverse(btn->rchild);}} 10、遞歸后序遍歷voidPostOrderTraverse(BiTNode*btn){if(btn!=NULL){PostOrderTraverse(btn->lchild);PostOrderTraverse(btn->rchild);printf("%c",btn->data);}}11、主函數(shù)main(){ BiTNode*btn; printf("\n輸入二叉樹(shù)空節(jié)點(diǎn)輸“”：\n"); btn=CreateBiTree(); printf("\n遞歸先序遍歷二叉樹(shù)的結(jié)果:\n"); PreOrderTraverse(btn);//遞歸先序遍歷建立的二叉樹(shù)printf("\n遞歸中序遍歷二叉樹(shù)的結(jié)果:\n");InOrderTraverse(btn);printf("\n遞歸后序遍歷二叉樹(shù)的結(jié)果:\n");PostOrderTraverse(btn); printf("\n二叉樹(shù)的結(jié)點(diǎn)數(shù)為:%d\n",JT);//二叉樹(shù)結(jié)點(diǎn)的數(shù)目 printf("\n層次遍歷二叉樹(shù)的結(jié)果:\n"); LevelTraverse(btn); printf("\n");}調(diào)試分析：由于開(kāi)始對(duì)二叉樹(shù)存儲(chǔ)的知識(shí)還不熟識(shí)，在建立二叉鏈表和二叉樹(shù)的遍歷出現(xiàn)了很多問(wèn)題。3、在使用二叉樹(shù)的遍歷時(shí)，有時(shí)因?yàn)樽约旱拇中模阎羔樀奈恢门e(cuò)了。4、做本程序用到了指針的知識(shí)，有時(shí)一有不懂的東西又只能打開(kāi)書(shū)來(lái)看。5、開(kāi)始時(shí)沒(méi)有把二叉樹(shù)的左右子樹(shù)情況考慮全面，導(dǎo)致咋遍歷的時(shí)候出現(xiàn)了一些錯(cuò)誤。用戶使用說(shuō)明本程序的運(yùn)行環(huán)境為MicrosofeV