2023年樹的實驗報告

２023-２023學年第一學期數(shù)據(jù)結構課內(nèi)實驗報告學院：計算機學院專業(yè)：計算機科學與技術姓名:學號:指導老師:實驗題目實驗目的1．掌握二叉樹的建立,遞歸遍歷（先序，中序,后序），打印樹狀二叉樹，計算葉子節(jié)點的個數(shù)。２.二叉樹的非遞歸遍歷3.掌握哈夫曼樹的基本算法。實驗內(nèi)容1.樹的遞歸與非遞歸遍歷（1)從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結構,建立二叉樹(以先序來建立）,(2)將此二叉樹按照“樹狀形式”打印輸出,(3)對其進行遍歷(先序、中序和后序)，(4)最后將遍歷結果打印輸出在遍歷算法中（5)規(guī)定至少有一種遍歷采用非遞歸方法2.哈夫曼基本規(guī)定:(１)從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹；(２)打印每一個字符相應的哈夫曼編碼。(3)對從終端讀入的字符串進行編碼，并顯示編碼結果。四:模塊化分各個模塊具體的功能描述。ｖｏｉdPrｅＯrｄer(BTreeｒoot)；先序遍歷ｖoｉdＩnＯrｄer（BTreeｒooｔ)；中序遍歷vｏidPostOrder（BTreerｏot);后序遍歷voidPｒeleaf(BTreｅｒoot);先序求葉子節(jié)點個數(shù)ｖoidPrinｔfTreｅ(BTｒｅeroot，iｎth）;打印二叉樹intPoｓtHeｉgｈt(ＢＴreeｒoot）);后序求樹的深度voiｄIｎitTree（BiTｒee*bｔ）;初始化樹intＩniｔＳtaｃｋ(Sｔack*ｔｏp)；初始化棧BiＴｎoｄｅ*Creａt(yī)e();//擴展結點創(chuàng)建二叉樹intPush（Sｔacｋ＊top,BiTｒeep);入棧intPoｐ(Sｔaｃk＊tｏp,BｉTree*p);出棧iｎtＧetＴｏp(Stacktoｐ,BiTrｅep);取棧頂元素vｏｉdPrｅＳtａck(BTreｅrｏot);//非遞歸先序遍歷ｖoidSｅleｃt(HＴreeht,intpos/＊尋找的范圍＊/，inｔ*s1,int*ｓ２)／/查找最小的兩個節(jié)點的下標voidCｒeatHuｆfmａｎTree（ＨTｒｅｅhｔ，intｗ[],iｎｔn）/／創(chuàng)建哈夫曼樹vｏiOutpｕｔ(ＨＴreeht，intｎ)/／輸出哈夫曼樹ｖoidＣodeHuffmanＴreｅ(HTｒeeht,HCｏdｅhc,ｉntn）／/編碼vｏｉdOutpuｔCode（HCodｅｈc,intｗ[]，ｉnｔｎ)//輸出編碼具體設計及運營結果voｉdprｅＯrder(BiTreｅbt）?//先序遍歷。{?iｆ（bt!=ＮULＬ) ｛??priｎtf("％c＂，bｔ->data）;??prｅＯｒder(bｔ->LChｉld); ?pｒeOrder（bt->RＣhiｌd）; ｝｝voiｄIｎOrder(BiTreｅｂt） //中序遍歷。{?if(ｂt！=NUＬL) ｛? InOrｄｅｒ（bt->ＬChild); ?ｐｒinｔf（＂％ｃ",bt->dａｔa); ?ＩnOｒｄｅr(bt->RChild)；?｝}voidPoｓtOｒder(BiＴrｅebt) /／后序遍歷。{ ｉf（ｂt!=NULL）?{ ?PostOrdeｒ(ｂｔ->LＣhｉld); ?PostOrder(bt－>RChilｄ）; ?printf("%c＂,bt->data);?}}voidTｒavｅr(BiTreebt)｛ }iｎtPoｓtTreｅＤeptｈ(ＢｉTｒeｅbt)｛?inｔhl，ｈr,ｍax; if(bt！=ＮULL) { ?hl=PoｓtTreeDepｔｈ(ｂt->LＣｈild); ?hr=PostTrｅeDeｐth(bt-＞RCｈｉld); ?max=hｌ>hｒ?hl:hｒ; ｒｅtｕrn(mａx+1); ｝?ｅlse??ｒｅｔurn0;｝voidPrｅStack(ＢｉTreｅbt) //非遞歸遍歷｛ BiTrｅep; LinkStａcks; InitSｔａck(&s);?/／p=bt; PushStaｃｋ(ｓ,ｂt); wｈｉlｅ(！Iseｍpty(s)) ｛??PoｐSｔacｋ（s,&ｐ）；?? priｎtｆ("％c",p->daｔa); if(p-＞ＲChild!=NUＬL) PuｓhＳtack(s,p->RChｉld);???if(p－＞LChilｄ!=ＮULL)?? ?PｕshStaｃk(s，ｐ->LChilｄ); ?｝}/＊voidPreStａｃｋ(BｉＴreebt) //非遞歸先序遍歷｛?BｉＴｒｅep; ＬinｋStａcks; IｎitStacｋ(＆s);?ｐ=ｂt；?ｗhile(ｐ|｜！Isempty(s）） ｛ ｉｆ(ｐ）? {? prinｔｆ（"%ｃ＂,p-＞ｄata）; ?ＰusｈＳｔack(s，p);? ｐ=p-＞ＬChild； }? else { ?ＰopStaｃk（s,&p)；?? ｐ=p->ＲCｈild; ?}?}}*/voidPrｉntＴree(BiＴreebｔ,ｉntnLaｙer）｛ ｉnti; if（bt==NＵLL） ?returｎ;?PrinｔTｒee(ｂt-＞RChiｌd,nLayer＋1）；?for(ｉ=0;i<ｎLayer;i++）??prinｔf(＂＂）；?pｒｉntf(＂%ｃ\n",bt-＞dａt(yī)a); PｒintＴrｅe(ｂt－＞LＣhild,nLayer+１);}voｉdLｅａfＴree(BｉTreｅbt)?／／樹的葉子結點遍歷｛ ｉｆ（bt!=NUＬL)?{ if(bt-＞ＬChild==NＵＬL&＆ｂt－>RChｉlｄ＝＝NＵＬＬ) ?pｒintf("%c"，bt->dａt(yī)a);? LeafTree(ｂｔ->LChｉld);? LeａfＴrｅe(bt->RChild);?}}voiｄＴrａvｅｌ(ＢiTreｅbt)? ?／/樹的按層遍歷{ BiTrｅep; LinｋＱuｅｕeQ; IｎiｔQueuｅ(＆Q); iｆ(ｂｔ＝＝NULＬ) ?return;?p=bt; EnterQueｕe(&Ｑ,ｐ）; while(Q.front!=Q.rｅar)?｛ ?DeｌｅteQuｅue(&Ｑ,＆p);??prinｔｆ（"%c＂,p->ｄａt(yī)a);? if(p－>ＬChild） ?EnterQuｅuｅ(&Q,p－>LChｉld);? if(p-＞ＲChild)?? EnｔerQueｕe(&Ｑ,p->RCｈild）;?}｝2:哈弗曼voidＣｒｅat(HｕｆfmanTreｅｈt，intｗ[],chaｒp[]，intn)/／構造哈弗曼樹。{?ints1,s2,i; fｏr（i=1;i<=n;ｉ＋+）／／前n個葉子結點的初始化 ｛??ht［i].weigｈt=ｗ[i]； ?hｔ[i].ｐaｒent=0； hｔ[i].LChild＝0;? ht［i］.RChild＝０; ｝?for(i=n+1；i<=2*ｎ-1;i＋+)/／權值的初始化。?｛? select(ht，i-1,＆s１，&ｓ2）；??hｔ［i].weｉghｔ=ht[ｓ１].weigｈｔ+ht[s2］.ｗeigｈt;??ht[i］.pａｒeｎｔ=0；??ｈｔ[s１].parenｔ=i;??ｈｔ[s2］.pａreｎt=i; ht［i].LＣｈild＝s1; ｈt[i］.RChild=ｓ2;?}}//生成哈弗曼樹的函數(shù)編碼。voiｄOｒdeｒHuffmaｎ(HuｆｆｍanTreｅｈt,Ｈuffｍａncodehc,chａｒｓtｒ[]，iｎtm)//根據(jù)哈弗曼樹構成哈弗曼編碼表ｈｃ。{?iｎtq[N]；?chａｒ*cd；/／臨時存放編碼串。?inｔc,p，i;//ｃ,ｐ分別為孩子和雙親。 iｎtstaｒt;//制定編碼cd的起始位置。?cd=(cｈaｒ*)mａlloc（m*sizeof(chａr）);?cd[ｍ-1]＝'\0';／/最后一位置放上字符串的結束標志。 ｉ＝0；?ｗｈile（i<m) {??sｗitcｈ(str［i]）??{ ｃａｓe's＇:q[i］=3;break; ?case＇ｔ'：q[i]=4;ｂreak;??case'a＇:q[i］=2;break;??cａｓe'e'：q［i]=6；brｅak; deｆａult：ｂｒeak;? ｝ start＝m-１;? c=q[i];? p=ht[q[ｉ]].ｐａｒent; ?while（p!＝０)? { ??--stａrｔ; ?iｆ（ｈt[ｐ].ＬＣhild==c)? ?ｃd[ｓｔart]=＇0';//左孩子生成0 ?eｌsｅ?? ?//右孩子生成1? ? cd[sｔarｔ］='１'; ?c=p; ?p=ht［p］.pａｒent; } hｃ[i]=(char*)malｌoc((ｍ－staｒt)*sizｅof（chaｒ)); strcpｙ(hc[ｉ],＆cd[stａrｔ]）；? prｉｎtf("%s",hc[i])； i＋＋；?｝??ｆｒee(cd);｝ｖoidpｒｉnt（HｕffmanTreeht，ｉｎtｎ){ intｉ; ｆoｒ(i=１;i<=2*n-1；i++) ?pｒinｔf（"％４d％4d％4d\n"，ht［i].weｉght，ｈt［i]．LChild,ht[i]．RＣhｉld）；}調(diào)試情況，設計技巧及體會1.對自己的設計進行評價,指出合理和局限性之處，提出改善方案；打印樹狀二叉樹的模塊沒有能按照自然數(shù)的形式打印，有待改善。２．對設計及調(diào)試過程的心得體會。源程序清單（電子版)／*建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷(先序、中序和后序）,打印輸出遍歷結果。1:從鍵盤接受輸入先序序列,以二叉鏈表作為存儲結構,建立二叉樹（以先序來建立)，2:將此二叉樹按照“樹狀形式”打印輸出,3：對其進行遍歷(先序、中序和后序)，4:最后將遍歷結果打印輸出在遍歷算法中５:規(guī)定至少有一種遍歷采用非遞歸方法。*／#iｎclude<ｓtdｉo．h＞#includｅ＜ｓtrｉng.h>＃ｉncludｅ<stdlｉb．h>#deｆｉｎeFAＬSE0#defｉnｅTRＵＥ1ｔyｐｅdｅfstruｃtＮoｄｅ{?ｃhａrｄaｔa; strucｔNodｅ*ＬChild; sｔrｕctNode*RChild;}BitNoｄｅ，*BｉTree;ｔｙpｅdefstruｃtｎod{ BiTreｅelem;?ｓtructnod*ｎｅxｔ;}SeqStacｋ,*LｉnｋStａck;voiｄIｎitStａcｋ(LinkＳｔaｃk*top）{ (*ｔｏｐ)=(LｉｎkStaｃｋ）malloc(sizeof(ＳeqStack)); (*top)－>nｅxt=NULＬ;}ｉntIsempty(LiｎkStａｃｋｔop)｛?iｆ(tｏp-＞neｘt＝=NULL) rｅturnTRUE； reｔurnFALSE;}intＰｕshSｔａck（LinkStａcktｏp,BiTreex){ LｉｎkStａｃktemp； temp＝(SeqStacｋ＊)ｍalｌoc（sizｅｏf(SeqＳtack)); iｆ(teｍp=＝ＮULL)??returnFＡLSE; teｍp->elｅm=x; temp->next=top->nｅxｔ;?top－>nｅxt=teｍp;?rｅturnＴＲUE;}intPｏpStack(LｉnkＳtacktop，BiTree＊x）{ LinkSｔackteｍp;?temp=ｔｏp－>nｅxt;?ｉｆ(temｐ＝＝NULL)??retuｒnFALSＥ; *x＝temp-＞ｅｌeｍ;?tｏp->ｎexｔ=ｔeｍp－>ｎeｘt; ｆrｅｅ(temｐ)；??returｎTRUE;}ｉntCreatBiＴrｅe（BiTreｅ＊bｔ)//樹的先序建立｛ charch; ｃh=getｃhaｒ(); iｆ(ch=='#')? ＊ｂｔ＝NULL; elsｅ ｛? *bt=(BｉｔNｏde*）ｍａlｌｏc(sｉzeｏf(ＢｉtNｏde)）; ?if(*bt==NULＬ) ??retuｒn0; ?（*bt)->dａｔa=ｃh; ＣreatBｉＴrｅe(&（(*bt)->LChｉｌd)）; ?Ｃreａt(yī)BｉＴree(&((*bｔ)->RChｉld)); }?return１;}tyｐedefsｔｒｕｃtnode｛?ＢｉTreew； sｔructnode*ｎｅxt;}LinkNode;ｔyｐedefstｒucｔ{?LinkNode*front;?ＬinkＮodｅ*rｅar;｝LｉnkQｕeue;ｉｎtＩnitＱuｅue(LｉｎkQuｅｕｅ＊Ｑ）｛ Ｑ->fronｔ=(LinｋNode*)maｌloc(siｚeof(LｉｎkNode)）; if(Q-＞froｎt!＝NＵLＬ) { ?Q->rear=Q－>fｒoｎt;??Q->ｆｒoｎｔ->ｎext=NULL;? reｔuｒnＴRＵE; ｝?else??reｔurnFALSＥ;}intＥntｅrQueｕe(LiｎkQueｕe*Q,BiTreex){?LinkNodｅ*ＮeｗNoｄe;?NeｗNｏdｅ＝(LinkNode*)malloc(sizeof(LiｎｋＱueue)); if(NewＮode!=NULL) { ?NｅwNｏde-＞ｗ＝x; ?NｅwＮode->next＝NＵＬL;??Q-＞reａｒ->nexｔ=NｅwＮｏｄe;? Ｑ->rear＝NｅwNｏｄe; ｒeturnTRUＥ;?}?elｓｅ? ｒetｕrnFＡＬSE;}intＤelｅteQuｅｕe（LinｋQｕeue*Q，ＢiTreｅ*x){?LｉnkNoｄe*ｐ; if(Q->ｆrｏnt==Q->reaｒ） returnＦALSE；?p=Q-＞froｎt-＞next; Q->front->nexｔ=ｐ-＞ｎｅxt;?if(Q－>ｒｅar==p) ?Q-＞rear=Q-＞froｎｔ;?*ｘ=p->w；?freｅ(p）；?returnTＲUＥ;｝voｉｄpreOrdeｒ（BiTreeｂｔ)?/／先序遍歷。{?iｆ（bt！=NULL) { prｉｎｔｆ("%c＂,bt->ｄata)；??ｐrｅOrder(bt-＞ＬＣhild);? pｒｅＯrder(bt->RＣｈilｄ）； }}voidInＯrdｅr(ＢｉTｒeebt)?//中序遍歷。｛ if（ｂｔ！＝NULＬ) { ?InＯrder（ｂt->LChｉld); ｐrintf(＂%ｃ",bt->daｔa)； InOrｄer(ｂt->RChild);?}}voiｄPoｓtOrder(BiTｒeeｂt）?／/后序遍歷。｛?if(bt!＝NULL） { PostOｒdeｒ(ｂt->ＬChiｌd); PosｔOrdeｒ（bt-＞RChild）;? prinｔf("%ｃ"，ｂｔ-＞daｔa);?}}voidTｒaver(ＢｉTｒeebt)｛?}iｎtＰｏstTreeDepth(BiTｒeｅbt)｛?ｉnthｌ,hｒ,ｍａx；?ｉｆ（bｔ!=ＮULL) ｛ hｌ＝PosｔTreeＤｅｐth(bt->ＬChｉld);??hr=ＰoｓtTreeDeptｈ(bt->RCｈｉlｄ);? max＝hl>hr？ｈl:ｈr;??ｒetuｒｎ(mａx+1）；?}?ｅｌse??rｅturn0；}ｖoidPｒeSｔacｋ(BiTrｅebt） //非遞歸遍歷｛?BiＴreep； ＬinkSｔacks;?InitStack(&s)； //p＝bt；?PuｓhStack（ｓ，bt);?whｉle(!Iｓｅmpty(s))?{ PｏpStack(ｓ,&p）;???prｉnｔf（"%c＂，ｐ－>dａt(yī)a)；? ?if(p->ＲChiｌd!=NUＬL)? ??PｕsｈStack(ｓ,p->RChilｄ)； ｉf(ｐ->LChild!=NＵLＬ)????PusｈSｔack(s，p->LCｈilｄ)； ?}}/*vｏidPreStack(ＢiTreebt）?/／非遞歸先序遍歷｛?ＢiTreep;?LinkStackｓ; InitStaｃk(&s）;?ｐ＝ｂt;?wｈilｅ(p||！Isempｔy(s))?{ ?ｉf（p） {? ｐｒintｆ(＂%c",p->ｄata）;? PushSｔack(s，ｐ）;???ｐ=p->LＣhiｌｄ； } ｅlse ?{?? PｏpStacｋ(s,&p）; ??p=p->ＲＣｈild; } }}*／voidPrintＴｒee（BiＴreeｂt，intｎＬayer){?ｉnti；?ｉf(ｂt=＝NULL） ?retuｒn;?ＰｒintTreｅ(ｂt->RChild,nLayｅr＋1); foｒ(ｉ＝0;ｉ<nＬａyer;i+＋）??printf("＂);?pｒintf("%c\n",bt->datａ); ＰｒｉntTreｅ（bt－>ＬChｉlｄ，nLayer＋1);}vｏidLｅaｆTrｅe(BiTreebt) //樹的葉子結點遍歷{ if(bt!=ＮＵLL）?{ ?ｉf(bt－＞ＬChilｄ=＝NULL＆&bt－＞RＣｈild＝=NULＬ）?? ｐrintf(＂％c＂,bt－>ｄａt(yī)a)； LeafTrｅe(bt->ＬChild); ＬｅafTrｅｅ(bt->ＲChｉｌd）； }｝ｖoidTraｖel(BiTｒeｅｂt) ??//樹的按層遍歷{ ＢiTreep；?LinkQｕｅｕeQ;?InitQueue(&Q); if（ｂｔ＝=NULL)? retｕｒn;?p=bt; EnteｒQueuｅ(&Q,p)； while(Q．froｎt！=Ｑ.reａr) { DｅｌeteQueue（&Ｑ,&p);??ｐrintｆ("%c",p->data）;? if(p->LChiｌd) ? EｎｔerＱueue（&Q,p->LCｈild);??iｆ(ｐ-＞ＲCｈｉｌd) ?EｎｔeｒQｕeue（&Q,p-＞RChild); ｝｝vｏｉdmａin()｛ BiTreｅｂt； inｔnLayer; CreatＢｉTree(&bt);?ｎＬayer=PｏstTreeDepth(bt); prｉntf("樹的深度：%d\n"，nLａyｅr); printf（"樹的樹狀打?。海躰"); ＰrintTree(bt，nＬayer);?pｒｉntf("前序訪問：\n");?prｅＯrｄer(bt); ｐrinｔｆ("\n");?printｆ（"中序訪問:\ｎ"）; InＯrdeｒ(bt);?printf("＼n"）；?printf("后序訪問：＼n");?PoｓtOｒder（bｔ); pｒiｎｔf(＂\n＂)； ｐｒintf("非遞歸訪問：\n")； PreStack(bt);?priｎtf(＂＼ｎ"）; prinｔf(＂樹的葉子結點有:＼n")；?LeafTｒee(bｔ）； ｐrintｆ（"\n＂）;?ｐriｎtf(＂樹的按層遍歷:\ｎ");?Ｔravel(bt);?prinｔf("\n"）；}2：//huｆfman#iｎｃｌｕde<stｄio.ｈ＞#ｉｎcｌude＜sｔdlib.h＞#ｉnｃluｄｅ<strinｇ.h>#deｆｉnｅN20#definｅM2＊N－1ｔｙpｅdefchaｒ＊Huffｍaｎcoｄe[N+１];ｔｙpedefｓtｒucｔ{?inｔwｅight; intparent; iｎtLChiｌd;?ｉntRChiｌd;｝HTNodｅ,ＨuｆfmanTreｅ[M+1];/／建立哈弗曼樹的幾個函數(shù)。voｉｄｓelect(HufｆｍanＴrｅｅht,iｎtpos,int*s1，int*s2)／/尋找最小孩子形成最優(yōu)二叉樹。{?inｔm1,m2; iｎｔi； m1＝m2=32７６7;?for（i=1;ｉ<＝poｓ;i＋+)?{??if(hｔ[ｉ].ｐarent==0&＆ht[i].ｗeighｔ<m1）? { ? ｍ2=m1; ?m1=ht［i］.weｉght; *s2=*s1; ? ＊s1＝i;??} ?ｅｌseiｆ（hｔ[i]．ｐａｒｅｎt==0&＆ht[i]．weiｇht<m2)? { ? m2＝hｔ[i]．weight;? *s2=i;? } } if（*s1>*s2)?{ i＝*s1; *ｓ1=*s2; ＊s2=i;?｝}voｉdＣreat（HuffmaｎTrｅｅｈt,intｗ[]，ｃｈarp[],intn)//構造哈弗曼樹。{?ｉｎts1,s２,ｉ;?for(i＝1;ｉ<=n;i++)//前n個葉子結點的初始化 ｛ hｔ[ｉ].weight=w[i］; ?ht[ｉ].ｐａreｎt=0； ?ｈt[ｉ].LChild=0; ?ht[i].RChilｄ=0；?｝ foｒ(i＝n+1;i＜=２*n-1;ｉ++）／/權值的初始化。?{ ?sｅlect(hｔ,ｉ－1，&s1,＆s2);??ht[i]．weighｔ=ht［s1]．weight+hｔ[ｓ２].weighｔ; ht[ｉ］.parｅnt=０; ?hｔ[s1].pａreｎt=i;? hｔ[s２].ｐaｒeｎt=i; ?ht[i].LＣｈｉld=ｓ1; ?hｔ［i].RChild＝ｓ２；?}}／/生成哈弗曼樹的函數(shù)編碼。voidOｒｄｅrHｕffman(HuffmanTreeｈt,Hｕffmancodehｃ,cｈarsｔr［]，iｎtm)//根據(jù)哈弗曼樹構成哈弗曼編碼表ｈｃ。{?intｑ[N］; char*cd;//臨時存放編碼串。?intc，p，i;//c，p分別為孩子和雙親。?iｎtstart;//制定編碼cｄ的起始位置。 cｄ=(ｃhar*）malｌoｃ(m*sizeoｆ(chaｒ）)；?cd［ｍ-１]=＇\0';//最后一位置放上字符串的結束標志。?i=０;?whｉle（ｉ<m)?｛ sｗitcｈ（sｔr[i])