二叉樹實驗報告-5

實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)實驗名稱二叉樹實驗類型驗證性實驗實驗地點計304機房實驗日期指導(dǎo)教師魏海平專業(yè)計算機科學(xué)與技術(shù)班級計算機1002學(xué)號20姓名張森遼寧石油化工大學(xué)計算機與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗報告評分表項目要求分?jǐn)?shù)有無項目（√）得分預(yù)習(xí)報告（30分）實驗?zāi)康拿鞔_5實驗內(nèi)容理解透徹5實驗方案設(shè)計完整合理程序總體框架設(shè)計完整10完成相關(guān)輔助代碼5測試方案合理5實驗過程（30分）發(fā)現(xiàn)問題5問題的分析15問題的解決方法10實驗報告（20分）內(nèi)容翔實無缺漏5如實記錄實驗過程10撰寫規(guī)整5實驗總結(jié)（10分）實驗結(jié)果的分析5按照結(jié)果對原實驗方案的改進(jìn)意見5實驗體會（10分）實驗的收獲5實驗內(nèi)容的發(fā)散考慮5總分一．實驗內(nèi)容：實現(xiàn)創(chuàng)建和遍歷二叉樹的基本操作二．實驗?zāi)康模海?）掌握二叉樹的定義和存儲表示，學(xué)會建立一棵特定二叉樹的方法；（2）掌握二叉樹的遍歷算法（先序、中序、后序遍歷算法）的思想，并學(xué)會遍歷算法的遞歸實現(xiàn)和非遞歸實現(xiàn)。三．問題描述：（1）編程實現(xiàn)構(gòu)造一棵二叉樹的算法，適合任意合法輸入的二叉樹的建立，并進(jìn)行相應(yīng)異常處理。（2）編程實現(xiàn)在二叉鏈表這種存儲方式下，實現(xiàn)二叉的遍歷，可采用遞歸或者非遞歸實現(xiàn)，遍歷算法可在先序、中序和后序遍歷算法中任選其一。四．問題的實現(xiàn)詳細(xì)設(shè)計確定存儲結(jié)構(gòu)，并給出所用抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)定義#include<stdio.h>#include<malloc.h>typedefcharDataType;typedefstructNode{DataTypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;voidPreOrder(BiTreeroot){//root為根if(root!=NULL){printf("%c",root->data);//所有的VISIT用PRINTF代替PreOrder(root->LChild);PreOrder(root->RChild);}}voidRecurrentInOrder(BiTreeroot)//遞歸中序{//root為根if(root!=NULL){RecurrentInOrder(root->LChild);printf("%c",root->data);RecurrentInOrder(root->RChild);}}voidPostOrder(BiTreeroot){//root為根if(root!=NULL){PostOrder(root->LChild);PostOrder(root->RChild);printf("%c",root->data);}}voidCreatBiTree(BiTree*bt)//創(chuàng)建二叉樹{charch;ch=getchar();if(ch=='.')*bt=NULL;//輸入.就結(jié)束輸入else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));}}voidInOrder(BiTreeroot)//直接非遞歸算法{inttop=0;BiTreep=root,s[100];while(p!=NULL||top!=0){while(p!=NULL){top++;s[top]=p;p=p->LChild;}if(top!=0){p=s[top];top--;printf("%c",p->data);p=p->RChild;}}}voidPrintTree(BiTreebt,intnLayer){if(bt==NULL)return;PrintTree(bt->RChild,nLayer+1);for(inti=0;i<nLayer;i++)printf("");printf("%c\n",bt->data);PrintTree(bt->LChild,nLayer+1);}intmain(){BiTreeR;CreatBiTree(&R);printf("DoPreOrder(Recurrent)：\n");//遞歸先序PreOrder(R);printf("\n\n");PrintTree(R,1);printf("DoInOrder(Recurrent)：\n");//遞歸中序RecurrentInOrder(R);printf("\n\n");printf("DoPostOrder(Recurrent)：\n");//遞歸后序PostOrder(R);printf("\n\n");printf("DoInOrder(NOTRecurrent)：\n");//非遞歸中序InOrder(R);printf("\n\n");return0;}測試結(jié)果列出典型輸入及對應(yīng)的輸出結(jié)果。輸入：ABC..DE.G..F...（其中.表示空格字符）輸出結(jié)果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA總結(jié)1．基本上沒有什么太大的問題，在調(diào)用select（）這個函數(shù)時，想把權(quán)值最小的兩個結(jié)點的序號帶回HuffmanCoding()，所以把那2個序號設(shè)置成了引用