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

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

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

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

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

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