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

實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱二叉樹實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)實(shí)驗(yàn)地點(diǎn)計(jì)304機(jī)房實(shí)驗(yàn)日期指導(dǎo)教師魏海平專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)計(jì)算機(jī)1002學(xué)號(hào)20姓名張森遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告評(píng)分表項(xiàng)目要求分?jǐn)?shù)有無(wú)項(xiàng)目（√）得分預(yù)習(xí)報(bào)告（30分）實(shí)驗(yàn)?zāi)康拿鞔_5實(shí)驗(yàn)內(nèi)容理解透徹5實(shí)驗(yàn)方案設(shè)計(jì)完整合理程序總體框架設(shè)計(jì)完整10完成相關(guān)輔助代碼5測(cè)試方案合理5實(shí)驗(yàn)過(guò)程（30分）發(fā)現(xiàn)問(wèn)題5問(wèn)題的分析15問(wèn)題的解決方法10實(shí)驗(yàn)報(bào)告（20分）內(nèi)容翔實(shí)無(wú)缺漏5如實(shí)記錄實(shí)驗(yàn)過(guò)程10撰寫規(guī)整5實(shí)驗(yàn)總結(jié)（10分）實(shí)驗(yàn)結(jié)果的分析5按照結(jié)果對(duì)原實(shí)驗(yàn)方案的改進(jìn)意見(jiàn)5實(shí)驗(yàn)體會(huì)（10分）實(shí)驗(yàn)的收獲5實(shí)驗(yàn)內(nèi)容的發(fā)散考慮5總分一．實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)創(chuàng)建和遍歷二叉樹的基本操作二．實(shí)驗(yàn)?zāi)康模海?）掌握二叉樹的定義和存儲(chǔ)表示，學(xué)會(huì)建立一棵特定二叉樹的方法；（2）掌握二叉樹的遍歷算法（先序、中序、后序遍歷算法）的思想，并學(xué)會(huì)遍歷算法的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)。三．問(wèn)題描述：（1）編程實(shí)現(xiàn)構(gòu)造一棵二叉樹的算法，適合任意合法輸入的二叉樹的建立，并進(jìn)行相應(yīng)異常處理。（2）編程實(shí)現(xiàn)在二叉鏈表這種存儲(chǔ)方式下，實(shí)現(xiàn)二叉的遍歷，可采用遞歸或者非遞歸實(shí)現(xiàn)，遍歷算法可在先序、中序和后序遍歷算法中任選其一。四．問(wèn)題的實(shí)現(xiàn)詳細(xì)設(shè)計(jì)確定存儲(chǔ)結(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;}測(cè)試結(jié)果列出典型輸入及對(duì)應(yīng)的輸出結(jié)果。輸入：ABC..DE.G..F...（其中.表示空格字符）輸出結(jié)果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA總結(jié)1．基本上沒(méi)有什么太大的問(wèn)題，在調(diào)用select（）這個(gè)函數(shù)時(shí)，想把權(quán)值最小的兩個(gè)結(jié)點(diǎn)的序號(hào)帶回HuffmanCoding()，所以把那2個(gè)序號(hào)設(shè)置成了引用