北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告3

PAGEPAGE8《數(shù)據(jù)結(jié)構(gòu)與算法統(tǒng)計(jì)》實(shí)驗(yàn)報(bào)告——實(shí)驗(yàn)三學(xué)院：班級(jí)：學(xué)號(hào)：姓名：一、實(shí)驗(yàn)?zāi)康?熟悉VC環(huán)境，學(xué)會(huì)使用C++解決關(guān)于二叉樹的問題。2在上機(jī)、調(diào)試的過程中，加強(qiáng)對(duì)二叉樹的理解和運(yùn)用。3鍛煉動(dòng)手編程和獨(dú)立思考的能力。二、實(shí)驗(yàn)內(nèi)容遍歷二叉樹。請(qǐng)輸入一棵二叉樹的擴(kuò)展的前序序列，經(jīng)過處理后生成一棵二叉樹，然后對(duì)于該二叉樹輸出前序、中序和后序遍歷序列。三、程序設(shè)計(jì)1、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，首先需要二叉樹的抽象數(shù)據(jù)結(jié)構(gòu)。⑴二叉樹的抽象數(shù)據(jù)類型定義為：ADTBinaryTree{ 數(shù)據(jù)對(duì)象D： D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D=Φ，則R=Φ，稱BinaryTree為空二叉樹；

若D≠Φ，則R={H}，H是如下二元關(guān)系；（1）在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

（2）若D-{root}≠Φ，則存在D-{root}={D1,Dr}，且D1∩Dr=Φ；

（3）若D1≠Φ，則D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的關(guān)系H1?H；若Dr≠Φ，則Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的關(guān)系Hr?H；H={<root,x1>,<root,xr>,H1,Hr}；

（4）(D1,{H1})是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,{Hr})是一棵符合本定義的二叉樹，稱為根的右子樹。 基本操作：CreatBiTree(BiTree&T) 操作結(jié)果：按先序次序建立二叉鏈表表示的二叉樹T PreOrderTraverse(BiTreeT,int(*visit)(chare)) 初始條件：二叉樹T已經(jīng)存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：先序遍歷二叉樹T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù)僅一次；一旦visit（）失敗，則操作失敗。 InOrderTraverse(BiTreeT,int(*visit)(chare)) 初始條件：二叉樹T已經(jīng)存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：中序遍歷二叉樹T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù)僅一次；一旦visit（）失敗，則操作失敗。PostOrderTraverse(BiTreeT,int(*visit)(chare)) 初始條件：二叉樹T已經(jīng)存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：后序遍歷二叉樹T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù)僅一次；一旦visit（）失敗，則操作失敗。}ADTBinaryTree⑵主程序流程主程序先調(diào)用CreatBiTree(BiTree&T)函數(shù)，根據(jù)輸入的先序序列構(gòu)造出一棵二叉樹，再依次調(diào)用PreOrderTraverse(BiTreeT,int(*visit)(chare))，InOrderTraverse(BiTreeT,int(*visit)(chare))，PostOrderTraverse(BiTreeT,int(*visit)(chare))函數(shù)，對(duì)該二叉樹進(jìn)行先序、中序、后序遍歷并輸出結(jié)果。⑶模塊調(diào)用關(guān)系 由主函數(shù)調(diào)用創(chuàng)建模塊，再調(diào)用計(jì)算模塊，由計(jì)算模塊將結(jié)果輸出。⑷流程圖按照先按照先序序列構(gòu)造出一棵二叉樹先序遍歷并輸出中序遍歷并輸出后序遍歷并輸出開始結(jié)束2、詳細(xì)設(shè)計(jì)⑴數(shù)據(jù)類型設(shè)計(jì)typedefstructBiTNode//二叉樹結(jié)構(gòu)類型{ chardata;//建立數(shù)據(jù)域 structBiTNode*lchild,*rchild;//建立左指針和右指針}BiTNode,*BiTree;⑵操作算法設(shè)計(jì)intCreatBiTree(BiTree&T)//按先序次序建立二叉鏈表表示的二叉樹T{ charch; scanf("%c",&ch); if(ch=='') { T=NULL; } else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) { exit(OVERFLOW); } T->data=ch; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } return1;}intvisit(chare)//對(duì)數(shù)據(jù)進(jìn)行輸出{ printf("%c",e); return1;}intPreOrderTraverse(BiTreeT,int(*visit)(chare))//先序遍歷二叉樹T的遞歸算法{ if(T) { if(visit(T->data)) if(PreOrderTraverse(T->lchild,visit)) if(PreOrderTraverse(T->rchild,visit))return1; return0; } else return1;}intInOrderTraverse(BiTreeT,int(*visit)(chare))//中序遍歷二叉樹T的遞歸算法{ if(T) { if(InOrderTraverse(T->lchild,visit)) if(visit(T->data)) if(InOrderTraverse(T->rchild,visit))return1; return0; } else return1;}intPostOrderTraverse(BiTreeT,int(*visit)(chare))//后序遍歷二叉樹T的遞歸算法{ if(T) { if(PostOrderTraverse(T->lchild,visit)) if(PostOrderTraverse(T->rchild,visit)) if(visit(T->data))return1; return0; } else return1;}⑶主函數(shù)設(shè)計(jì)voidmain()//主函數(shù){ BiTreeT; CreatBiTree(T);//按先序次序建立二叉鏈表表示的二叉樹T printf("PreOrderTraverse:\n"); PreOrderTraverse(T,visit);;//先序遍歷二叉樹T printf("\n"); printf("InOrderTraverse:\n"); InOrderTraverse(T,visit);//中序遍歷二叉樹T printf("\n"); printf("PostOrderTraverse:\n"); PostOrderTraverse(T,visit);//后序遍歷二叉樹T printf("\n");}四、程序調(diào)試分析⑴調(diào)試時(shí)，輸入時(shí)有時(shí)候有輸出有時(shí)候沒輸。向老師請(qǐng)教，老師說是比如abc，則b下的兩個(gè)孩子是空的也應(yīng)該打出空格，后來試了一下，果然是這樣，也就是說應(yīng)該要輸入一個(gè)完整的樹。⑵進(jìn)行先序遍歷時(shí)，訪問左子樹后程序即結(jié)束，不訪問根結(jié)點(diǎn)和右子樹。后來發(fā)現(xiàn)是“return0;”還是“return1;”的問題。遞歸時(shí)，“return0；”代表程序結(jié)束，“return1；”代表回到原位置繼續(xù)執(zhí)行。以后應(yīng)加強(qiáng)對(duì)于基礎(chǔ)知識(shí)的理解。五、程序運(yùn)行結(jié)果測(cè)試一：ABCDEGFPreOrderTraverse:ABCDEGFInOrderTraverse:CBEGDFAPostOrderTraverse:CGEFDBA測(cè)試二：1234576PreOrderTraverse:InOrderTraverse:PostOrderTraverse:六、程序清單#include<iostream>#include<stdio.h>#include<stdlib.h>#defineOVERFLOW0typedefstructBiTNode//二叉樹結(jié)構(gòu)類型{ chardata;//建立數(shù)據(jù)域 structBiTNode*lchild,*rchild;//建立左指針和右指針}BiTNode,*BiTree;intCreatBiTree(BiTree&T);//按先序次序建立二叉鏈表表示的二叉樹Tintvisit(chare);//對(duì)數(shù)據(jù)進(jìn)行輸出intPreOrderTraverse(BiTreeT,int(*visit)(chare));//先序遍歷二叉樹T的遞歸算法intInOrderTraverse(BiTreeT,int(*visit)(chare));//中序遍歷二叉樹T的遞歸算法intPostOrderTraverse(BiTreeT,int(*visit)(chare));//后序遍歷二叉樹T的遞歸算法voidmain()//主函數(shù){ BiTreeT; CreatBiTree(T);//按先序次序建立二叉鏈表表示的二叉樹T printf("PreOrderTraverse:\n"); PreOrderTraverse(T,visit);;//先序遍歷二叉樹T printf("\n"); printf("InOrderTraverse:\n"); InOrderTraverse(T,visit);//中序遍歷二叉樹T printf("\n"); printf("PostOrderTraverse:\n"); PostOrderTraverse(T,visit);//后序遍歷二叉樹T printf("\n");}intCreatBiTree(BiTree&T)//按先序次序建立二叉鏈表表示的二叉樹T{ charch; scanf("%c",&ch); if(ch=='') { T=NULL; } else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) { exit(OVERFLOW); } T->data=ch; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } return1;}intvisit(chare)//對(duì)數(shù)據(jù)進(jìn)行輸出{ printf("%c",e); return1;}intPreOrderTraverse(BiTreeT,int(*visit)(chare))//先序遍歷二叉樹T的遞歸算法{ if(T) { if(visit(T->data)) if(PreOrderTraverse(T->lchild,visit)) if(PreOrderTraverse(T->rchild,visit))return1; return0; } else return1;}intInOrderTraverse(BiTreeT,int(*visit)(chare))//中序遍歷二叉樹T的遞歸算法{ if(T) { if(InOrderTraverse(T->lchild,visit)) if(visit(T->data)) if(InOrderTraverse(T->rchild,visit))return1; retu