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

PAGEPAGE8《數(shù)據(jù)結(jié)構(gòu)與算法統(tǒng)計》實驗報告——實驗三學(xué)院：班級：學(xué)號：姓名：一、實驗?zāi)康?熟悉VC環(huán)境，學(xué)會使用C++解決關(guān)于二叉樹的問題。2在上機、調(diào)試的過程中，加強對二叉樹的理解和運用。3鍛煉動手編程和獨立思考的能力。二、實驗內(nèi)容遍歷二叉樹。請輸入一棵二叉樹的擴展的前序序列，經(jīng)過處理后生成一棵二叉樹，然后對于該二叉樹輸出前序、中序和后序遍歷序列。三、程序設(shè)計1、概要設(shè)計為實現(xiàn)上述程序功能，首先需要二叉樹的抽象數(shù)據(jù)結(jié)構(gòu)。⑴二叉樹的抽象數(shù)據(jù)類型定義為：ADTBinaryTree{ 數(shù)據(jù)對象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是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：先序遍歷二叉樹T，對每個結(jié)點調(diào)用visit函數(shù)僅一次；一旦visit（）失敗，則操作失敗。 InOrderTraverse(BiTreeT,int(*visit)(chare)) 初始條件：二叉樹T已經(jīng)存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：中序遍歷二叉樹T，對每個結(jié)點調(diào)用visit函數(shù)僅一次；一旦visit（）失敗，則操作失敗。PostOrderTraverse(BiTreeT,int(*visit)(chare)) 初始條件：二叉樹T已經(jīng)存在，visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：后序遍歷二叉樹T，對每個結(jié)點調(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ù)，對該二叉樹進行先序、中序、后序遍歷并輸出結(jié)果。⑶模塊調(diào)用關(guān)系 由主函數(shù)調(diào)用創(chuàng)建模塊，再調(diào)用計算模塊，由計算模塊將結(jié)果輸出。⑷流程圖按照先按照先序序列構(gòu)造出一棵二叉樹先序遍歷并輸出中序遍歷并輸出后序遍歷并輸出開始結(jié)束2、詳細設(shè)計⑴數(shù)據(jù)類型設(shè)計typedefstructBiTNode//二叉樹結(jié)構(gòu)類型{ chardata;//建立數(shù)據(jù)域 structBiTNode*lchild,*rchild;//建立左指針和右指針}BiTNode,*BiTree;⑵操作算法設(shè)計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)//對數(shù)據(jù)進行輸出{ 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è)計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)試時，輸入時有時候有輸出有時候沒輸。向老師請教，老師說是比如abc，則b下的兩個孩子是空的也應(yīng)該打出空格，后來試了一下，果然是這樣，也就是說應(yīng)該要輸入一個完整的樹。⑵進行先序遍歷時，訪問左子樹后程序即結(jié)束，不訪問根結(jié)點和右子樹。后來發(fā)現(xiàn)是“return0;”還是“return1;”的問題。遞歸時，“return0；”代表程序結(jié)束，“return1；”代表回到原位置繼續(xù)執(zhí)行。以后應(yīng)加強對于基礎(chǔ)知識的理解。五、程序運行結(jié)果測試一：ABCDEGFPreOrderTraverse:ABCDEGFInOrderTraverse:CBEGDFAPostOrderTraverse:CGEFDBA測試二：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);//對數(shù)據(jù)進行輸出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)//對數(shù)據(jù)進行輸出{ 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