二叉樹實(shí)驗(yàn)報(bào)告-16

二叉樹題目:二叉樹遍歷問題班級(jí)：2011級(jí)軟件一班姓名：寧雪鋒學(xué)號(hào)：1125115017完成日期：2012/11/25需求分析1)程序流程:定義一個(gè)二叉樹，分別以btreenode*left，btreenode*right代表二叉樹中的左右子樹。從鍵盤讀入一個(gè)字符串（廣義二叉樹）到數(shù)組中，并以該數(shù)組來建立二叉樹首先判斷二叉樹非空，如果非空，則進(jìn)行以下操作：先序遞歸與非遞歸遍歷二叉樹，輸出訪問到的元素中序遞歸與非遞歸遍歷二叉樹，輸出訪問到的元素后序遞歸與非遞歸遍歷二叉樹，輸出訪問到的元素按層遍歷二叉樹，輸出訪問到的元素清空二叉樹，回收內(nèi)存2)程序?qū)崿F(xiàn)的功能通過遞歸與非遞歸的先中后三種遍歷和一種層遍歷來實(shí)現(xiàn)對(duì)輸入的廣義表的遍歷輸出，輸出的形式為字符，和輸入的形式相同3）測(cè)試數(shù)據(jù)：二．概要設(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，且存在Dr上的關(guān)系Hr∈H；H={<root，x1>，<root，xr>，H1,Hr}基本操作:初始化置空二叉樹initbtree(btreenode*&bt)通過輸入的字符串（廣義表）建立二叉樹createbtree(btreenode*&bt,char*a)判斷二叉樹是否為空，輸入類型為bool型emptybtree(btreenode*bt)遞歸先序遍歷preorder(btreenode*bt)遞歸中序遍歷inorder(btreenode*bt)遞歸后序遍歷posorder(btreenode*bt)非遞歸先序遍歷FxianBianli(btreenode*bt)非遞歸中序遍歷FzhongBianli(btreenode*bt)非遞歸后序遍歷FhouxuBianli(btreenode*bt)三、詳細(xì)設(shè)計(jì)創(chuàng)建二叉樹通過讀取輸入的字符串廣義表，然后進(jìn)行判斷處理while(a[i]) { switch(a[i]){ case'': break;//空格不作任何處理 case'(': if(top==maxsize-1){ cout<<"?？臻g太小，請(qǐng)?jiān)黾觤axsize的值！"<<endl; exit(1); } top++;s[top]=p;k=1; break; case')': if(top==-1){ cout<<"二叉樹管廣義表字符串錯(cuò)!"<<endl;exit(1); } top--; break; case',': k=2;break; default: p=newbtreenode; p->data=a[i]; p->left=p->right=NULL; if(bt==NULL)bt=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; }遞歸先序遍歷如果二叉樹非空if(bt!=NULL){ cout<<bt->data<<''; preorder(bt->left); preorder(bt->right); }遞歸后序遍歷和中序遍歷與遞歸先序遍歷相似，在此不作詳細(xì)說明非遞歸先序遍歷使用棧的先進(jìn)后出特性實(shí)現(xiàn) do { while(p) { cout<<p->data<<""; if(p->right!=NULL) Stack[top++]=p->right; p=p->left; } if(top>=0) p=Stack[--top]; } while(top>=0);非遞歸中序遍歷與先序遍歷大同小異非遞歸后序遍歷使用時(shí)得先定義需要的結(jié)構(gòu)structTreeStack{ btreenode*link; intF;};這個(gè)較為復(fù)雜，參考于數(shù)據(jù)類叢書do { while(p) { stack[top++].link=p; stack[top].F=0; p=p->left; } if(top>0) { sign=stack[top].F; p=stack[--top].link; if(sign==0) { stack[++top].link=p; stack[top].F=1; p=p->right; } else { cout<<p->data<<""; p=NULL; } } } while(top>0);四、調(diào)試分析1.在調(diào)試過程中，個(gè)人推薦還是程序編寫一個(gè)調(diào)試一個(gè)為好，方便找出錯(cuò)誤2.對(duì)于inti；i<n；i++這種的變量，一定得細(xì)心編寫，減少在這方面出錯(cuò)的概率，而且這地方出錯(cuò)有點(diǎn)讓人忽略，浪費(fèi)過多調(diào)試的時(shí)間3.對(duì)于非遞歸后序遍歷，需要多編程加以熟悉，個(gè)人感覺比較難，像叢書給出的那樣，心思一定要縝密才能寫出那樣的程序五、用戶使用說明輸入一個(gè)字符串，即廣義表，例如a(b(,c),d(e,f))程序執(zhí)行即可輸出各種遍歷的順序輸出六、測(cè)試結(jié)果輸入：a(b(,c),d(e,f))輸出：七、附錄具體代碼如下所示：#include<iostream>usingnamespacestd;typedefcharelemtype;structbtreenode{ elemtypedata; btreenode*left; btreenode*right;};voidinitbtree(btreenode*&bt){ bt=NULL;}voidcreatebtree(btreenode*&bt,char*a){ constintmaxsize=20; btreenode*s[maxsize]; inttop=-1; bt=NULL; btreenode*p; intk,i=0;//用k作為處理節(jié)點(diǎn)的左子樹和右子樹的標(biāo)記 //k=1處理左子樹，k=2處理右子樹 while(a[i]) { switch(a[i]){ case'': break;//空格不作任何處理 case'(': if(top==maxsize-1){ cout<<"?？臻g太小，請(qǐng)?jiān)黾觤axsize的值！"<<endl; exit(1); } top++;s[top]=p;k=1; break; case')': if(top==-1){ cout<<"二叉樹管廣義表字符串錯(cuò)!"<<endl;exit(1); } top--; break; case',': k=2;break; default: p=newbtreenode; p->data=a[i]; p->left=p->right=NULL; if(bt==NULL)bt=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; }}boolemptybtree(btreenode*bt){ returnbt==NULL;}//遍歷算法voidpreorder(btreenode*bt){ if(bt!=NULL){ cout<<bt->data<<''; preorder(bt->left); preorder(bt->right); }}voidinorder(btreenode*bt){ if(bt!=NULL){ inorder(bt->left); cout<<bt->data<<''; inorder(bt->right); }}voidposorder(btreenode*bt){ if(bt!=NULL){ posorder(bt->left); posorder(bt->right); cout<<bt->data<<''; }}//非遞歸先序遍歷voidFxianBianli(btreenode*bt){ inttop=0; btreenode*Stack[100],*p; p=bt; do { while(p) { cout<<p->data<<""; if(p->right!=NULL) Stack[top++]=p->right; p=p->left; } if(top>=0) p=Stack[--top]; } while(top>=0);}//非遞歸中序遍歷voidFzhongBianli(btreenode*bt){ inttop=0; btreenode*Stack[100],*p; p=bt; do { while(p) { Stack[top++]=p; p=p->left; } if(top>0) { p=Stack[--top]; cout<<p->data<<""; p=p->right; } } while(top>0||top==0&&p);}//定義后序遍歷所需結(jié)構(gòu)structTreeStack{ btreenode*link; intF;};//非遞歸后續(xù)遍歷voidFhouxuBianli(btreenode*bt){ inttop=0,sign; btreenode*p; TreeStackstack[100]; p=bt; do { while(p) { stack[top++].link=p; stack[top].F=0; p=p->left; } if(top>0) { sign=stack[top].F; p=stack[--top].link; if(sign==0) { stack[++top].link=p; stack[top].F=1; p=p->right; } else { cout<<p->data<<""; p=NULL; } } } while(top>0);}voidlevelorder(btreenode*bt){ constintmaxsize=30; //定義隊(duì)列 btreenode*q[maxsize]; intfront=0,rear=0; btreenode*p; if(bt!=NULL){ rear=(rear+1)%maxsize; q[rear]=bt; } while(front!=rear){ front=(front+1)%maxsize; p=q[front]; cout<<p->data<<''; if(p->left!=NULL){ rear=(rear+1)%maxsize; q[rear]=p->left; } if(p->right!=NULL){ rear=(rear+1)%maxsize; q[rear]=p->right; } }} voidprintbtree(btreenode*bt){ if(bt!=NULL){ cout<<bt->data; if(bt->left!=NULL||bt->right!=NULL){ cout<<'('; printbtree(bt->left); if(bt->right!=NULL) cout<<","; printbtree(bt->right); cout<<")"; } }}voidclearbtree(btreenode*&bt){ if(bt!=NULL){ clearbtree(bt->left); clearbtree(bt->right); deletebt; bt=NULL; }}voidmain(){ btreenode*bt; initbtree(bt); charb[50];//存放二叉樹廣義表的字符數(shù)組 cout<<"輸入二叉樹用廣義表表示的字符串："<<endl; cin.getline(b,sizeof(b));//從鍵盤輸入字符串存放到數(shù)組b中 createbtree(bt,b); printbtree(bt);cout<<endl; cout<<"遍歷輸出如下所示\n"<<endl; cout<<"前序：";preorder(bt);cout<<end