數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告9

實(shí)驗(yàn)報(bào)告六課程數(shù)據(jù)結(jié)構(gòu)（II）實(shí)驗(yàn)項(xiàng)目二叉樹(shù)的建立和遍歷成績(jī)專業(yè)年級(jí)指導(dǎo)教師姓名學(xué)號(hào)實(shí)驗(yàn)日期2011-6-7一、實(shí)驗(yàn)?zāi)康模?、掌握二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)的類型定義及實(shí)現(xiàn)2、掌握二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)的各種基本運(yùn)算方法。如二叉樹(shù)的創(chuàng)建、遍歷、查找等運(yùn)算3、掌握二叉樹(shù)用不同方法表示所對(duì)應(yīng)的不同輸入形式4、掌握二叉樹(shù)各種重要性質(zhì)在解決實(shí)際問(wèn)題中的應(yīng)用二、實(shí)驗(yàn)環(huán)境：PC微機(jī)、Windows，DOS，TurburC，或VisualC++三、實(shí)驗(yàn)內(nèi)容：1、建立二叉樹(shù)并實(shí)現(xiàn)各種遍歷（1）問(wèn)題描述對(duì)二叉樹(shù)的各種結(jié)點(diǎn)都訪問(wèn)，而且每個(gè)結(jié)點(diǎn)只訪問(wèn)一次的過(guò)程稱為二叉樹(shù)的遍歷。根據(jù)訪問(wèn)二叉樹(shù)左子樹(shù)、根、右子樹(shù)的不同順序，可先分為先根遍歷、中根遍歷、后根遍歷三中訪問(wèn)方法。另外，由于二叉樹(shù)中所有結(jié)點(diǎn)有相應(yīng)的層次順序，則按照從第一層到最后一層的訪問(wèn)順序，并且每層都從左到右進(jìn)行訪問(wèn)，又可得到層序遍歷的訪問(wèn)方法。試編程完成：用遞歸方法完成二叉樹(shù)的創(chuàng)建、先根遍歷、中根遍歷、后根遍歷。用非遞歸方法完成二叉樹(shù)的創(chuàng)建、按層遍歷、中根遍歷、后根遍歷。（2）基本要求程序運(yùn)行時(shí)，先輸入二叉樹(shù)結(jié)點(diǎn)的值（一個(gè)字符），先建立二叉樹(shù)，然后對(duì)建立的二叉樹(shù)分別進(jìn)行先序、中序、后序遍歷；要求格式化輸出遍歷結(jié)果：每一序列數(shù)據(jù)之間用“—>”分開(kāi)；三種遍歷結(jié)果分行顯示；輸出結(jié)果之前最好給出提示，如：InOrderTraverse:；（3）算法描述在算法實(shí)現(xiàn)上，從算法的效率看，非遞歸方法具有較好時(shí)間效率，遞歸方法書(shū)寫(xiě)形式較為簡(jiǎn)捷，更為直觀，一般具有較好的空間效率。在此選用非遞歸方法。用非遞歸方法對(duì)二叉樹(shù)分別進(jìn)行不同順序的遍歷，比遞歸方法要復(fù)雜得多?？梢哉f(shuō)二叉樹(shù)的先根、中根、后根、按層順序遍歷的四種不同方法，其非遞歸的實(shí)現(xiàn)過(guò)程差別非常大。創(chuàng)建樹(shù)將讀入的字符串轉(zhuǎn)換為二叉樹(shù)用ch掃描采用括號(hào)表示二叉樹(shù)的字符串。分以下幾種情況：a）、ch=’)’則將前面創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧，并置k=1，表示后面創(chuàng)建的結(jié)點(diǎn)作為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)：b）、ch=’(’表示棧中的左右孩子處理完畢，退棧：c）、ch=’,’表示其后面創(chuàng)建的結(jié)點(diǎn)作為這個(gè)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)：d）、其他情況創(chuàng)建結(jié)點(diǎn)，根據(jù)k值建立它與棧中結(jié)點(diǎn)之間的關(guān)系，當(dāng)k=1時(shí)，表示結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn)； 當(dāng)k=2時(shí)，表示結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)如此循環(huán)直到客串處理完畢。算法中使用的棧st保存雙親結(jié)點(diǎn)，top為其棧指針，k為其后處理結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左結(jié)點(diǎn)還是右結(jié)點(diǎn)。先序遍歷訪問(wèn)根結(jié)點(diǎn)；先序遍歷左結(jié)點(diǎn)；后序遍歷右結(jié)點(diǎn)；中序遍歷中序遍歷左結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)；中序遍歷右結(jié)點(diǎn)；后續(xù)遍歷后序遍歷左結(jié)點(diǎn)；后序遍歷右結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)；（4）算法實(shí)現(xiàn)——示例程序#include<cstdlib>#include<iostream>usingnamespacestd;typedefstructtnode{ chardata; structtnode*lchild,*rchild;}BTNode;classTree{public: voidCreateBTree(BTNode*&bt,char*str) { BTNode*st[100],*p=NULL; inttop=-1,k,j=0; charch; bt=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case'(': top++;st[top]=p;k=1; break; case')': top--; break; case',': k=2; break; default: p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL) { cout<<"根節(jié)點(diǎn)："<<p->data<<endl; bt=p; } else { switch(k) { case1: st[top]->lchild=p;cout<<st[top]->data<<"的左孩子："<<p->data<<endl;break; case2: st[top]->rchild=p;cout<<st[top]->data<<"的右孩子："<<p->data<<endl;break; } } } j++; ch=str[j]; } cout<<"二叉樹(shù)構(gòu)建成功!"<<endl; } //先序遍歷 voidPreOrder(BTNode*bt) { if(bt!=NULL) { cout<<"->"<<bt->data; PreOrder(bt->lchild); PreOrder(bt->rchild); } } //中序遍歷 voidInOrder(BTNode*bt) { if(bt!=NULL) { InOrder(bt->lchild); cout<<"->"<<bt->data; InOrder(bt->rchild); }}voidPostOrder(BTNode*bt){ if(bt!=NULL) { PostOrder(bt->lchild);PostOrder(bt->rchild); cout<<"->"<<bt->data; }}voidinput(chartreeList[]){ //chartreeList; cout<<"inputtree:"; cin>>treeList; //returntreeList;}};intmain(intargc,char*argv[]){ BTNode*tree; Treetr; chartreeList[50]; cout<<"讀入二叉樹(shù):"<<endl; tr.input(treeList); cout<<"開(kāi)始構(gòu)建二叉樹(shù)..."<<endl; tr.CreateBTree(tree,treeList); cout<<endl<<"先序遍歷:"; tr.PreOrder(tree); cout<<endl<<"中序遍歷:"; tr.InOrder(tree); cout<<endl<<"后序遍歷:"; tr.PostOrder(tree);