數(shù)據(jù)結(jié)構(gòu)實驗報告6-二叉樹與哈夫曼樹

數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導V2016數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導V2016常熟理工學院計算機科學與工程學院#實驗六二叉樹實驗目的】1、掌握二叉樹的基本存儲表示。2、掌握二叉樹的遍歷操作實現(xiàn)方法(遞歸和非遞歸方法)3、理解并實現(xiàn)二叉樹的其他基本操作。4、掌握二叉樹的重要應用哈夫曼編碼的實現(xiàn)。實驗學時】4-6學時實驗預習】回答以下問題：1、二叉樹的二叉鏈表存儲表示。typedefstructBiTNode{//結(jié)點結(jié)構(gòu)ElemTypedata；//數(shù)據(jù)域structBiTNode*Lchild；//左孩子指針structBiTNode*Rchild；〃右孩子指針}BiTNode，*BiTree；voidCreate(BiTree&T){//輸入擴展二叉樹的先序序列，構(gòu)建二叉鏈表scanf(&ch);//輸入一個元素if(ch=='#')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode))；//申請根結(jié)點T->data=ch;//給根結(jié)點數(shù)據(jù)域賦值Create(T->Lchild);〃建左子樹Create(T->Rchild);〃建右子樹}}//Create2、二叉樹的三種基本遍歷方式。前序遍歷(DLR),首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。簡記根-左-右。中序遍歷(LDR)，首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。簡記左-根-右。后序遍歷(LRD)，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。簡記左-右-根。

3、解釋哈夫曼樹和帶權(quán)路徑長度WPL。哈夫曼樹：它是最優(yōu)二叉樹。定義：給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若樹的帶權(quán)路徑長度達到最小，則這棵樹被稱為哈夫曼樹。路徑和路徑長度定義：在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1,則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。結(jié)點的權(quán)及帶權(quán)路徑長度定義：若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。樹的帶權(quán)路徑長度定義：樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL。實驗內(nèi)容和要求】1、編寫程序exp6_l.c，實現(xiàn)二叉樹的鏈式存儲及基本操作。以下圖所示的二叉樹實現(xiàn)二叉樹的二叉鏈表存儲及基本操作，回答下列問題，補充完整程序，并調(diào)試運行驗證結(jié)果。ABXACADAABXACADAEAFAAGA（1）按照先序序列建立該二叉樹。讀入的字符序列應為：ABCDEFG（*表示空指針）（2）該二叉樹的三種遍歷序列：TOC\o"1-5"\h\z先序序列：__ABCDEFG;中序序列：__CBEGDFA;后序序列：__CGEFDBA;（3）按層次遍歷該二叉樹，得到的序列為：ABCDEFG。（4）該二叉樹的深度為：__4。（5）該二叉樹的葉子結(jié)點數(shù)為：3。（6）交換該二叉樹所有結(jié)點的左右次序得到的新二叉樹為：（畫出新二叉樹的圖）（7）新二叉樹的三種遍歷序列分別為：先序序列：ABDFEGC中序序列：AFDGEBC后序序列：FGEDCBAexp6_1.c參考程序如下：#include<stdio.h>#include<malloc.h>#defineMAX20/*二叉樹的二叉鏈表存儲表示*/typedefstructBTNode{chardata;/*結(jié)點數(shù)據(jù)*/structBTNode*lchild;/*左孩子指針*/structBTNode*rchild;/*右孩子指針*/}*BiTree;/*非遞歸遍歷輔助隊列*/typedefstruct{BiTreedata[MAX];intfront,rear;/*先序遍歷創(chuàng)建二叉樹*//*先序遍歷創(chuàng)建二叉樹*//*先序遍歷二叉樹*//*中序遍歷二叉樹*//*后序遍歷二叉樹*//*先序遍歷的非遞歸算法*//*中序遍歷的非遞歸算法*//*后序遍歷的非遞歸算法*/voidcreateBiTree(BiTree*t);voidPreOrder(BiTreep);voidInOrder(BiTreep);voidPostOrder(BiTreep);voidRPreorder(BiTreep);voidRInorder(BiTreep);voidRPostorder(BiTreep);/*以后序遍歷的方式復制二叉樹/*以后序遍歷的方式復制二叉樹*//*交換二叉樹的結(jié)點的左右孩子*//*利用循環(huán)隊列實現(xiàn)層次遍歷*//*統(tǒng)計二叉樹葉子結(jié)點（遞歸）*//*釋放二叉樹*//*扔掉存在鍵盤緩沖區(qū)的輸入結(jié)束回車符*//*子樹為空則返回*/intdepth(BiTreet);/*求二叉樹的深度算法*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr);/*后序復制二叉樹-建立結(jié)點*/BiTreecopytree(BiTreet);BiTreeswap(BiTreeb);voidccOrder(BiTreet);intLeaves(BiTreet);voidrelease(BiTreet);/*先序遍歷創(chuàng)建二叉樹*/voidcreateBiTree(BiTree*t){chars;BiTreeq;s=getchar();getchar();if(s=='#'){*t=NULL;return;}q=(BiTree)malloc(sizeof(structBTNode));if(q==NULL){exit(0);}q->data=s;*t=q;createBiTree(&q->lchild);/*遞歸建立左子樹*/createBiTree(&q->rchild);/*遞歸建立右子樹*/}/*createBiTree*//*先序遍歷二叉樹，補充遞歸算法*/voidPreOrder(BiTreep){if(p!=NULL){PreOrder(p->lchild);PreOrder(p->rchild);}}/*PreOrder*//*中序遍歷二叉樹，補充遞歸算法*/voidInOrder(BiTreep){if(p!=NULL){InOrder(p->lchild);InOrder(p->rchild);}}/*InOrder*//*后序遍歷二叉樹，補充遞歸算法*/voidPostOrder(BiTreep){if(p!=NULL){PostOrder(p->lchild):PostOrder(p->rchild);}}/*PostOrder*//*先序遍歷的非遞歸算法*/voidRPreorder(BiTreep){BiTreestack[MAX],q;inttop=0,i;for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化樹結(jié)點*/q=p;while(q!=NULL){if(q->rchild!=NULL)stack[top++]=q->rchild;/*右指針進棧*/if(q->lchild!=NULL)q=q->lchild;/*順著左指針繼續(xù)向下*/elseif(top>0)q=stack[--top];/*左子樹訪問完，出棧繼續(xù)訪問右子樹結(jié)點*/elseq=NULL;}}/*RPreorder*//*中序遍歷的非遞歸算法*/voidRInorder(BiTreep){BiTreestack[MAX],q;inttop=0,i;for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化樹結(jié)點*/q=p;while(q!=NULL){if(q->rchild!=NULL)stack[top++]=q->rchild;/*右指針進棧*/if(q->lchild==NULL)elsestack[top++]=q->lchild;/*左指針進棧*/q=q->lchild;/*順著左指針繼續(xù)向下*/elseif(top>0)q=stack[--top];/*左子樹訪問完，出棧繼續(xù)訪問右子樹結(jié)點*/elseq=NULL;}}/*RInorder*//*后序遍歷的非遞歸算法*/voidRPostorder(BiTreep){BiTreestack[MAX],q;inti,top=0,flag[MAX];for(i=0;i<MAX;i++)/*初始化棧*/{stack[i]=NULL;flag[i]=0;}q=p;while(q!=NULL||top!=0){if(q!=NULL)/*當前結(jié)點進棧，先遍歷其左子樹*/{stack[top]=q;flag[top]=0;top++;q=q->lchild;}else{while(top){if(flag[top-1]==0)/*遍歷結(jié)點的右子樹*/{q=stack[top-1];q=q->rchild;flag[top-1]=1;break;}else{q=stack[--top];遍歷結(jié)點*/}}}if(top==0)break;}}/*RPostorder*//*求二叉樹的深度算法，補充遞歸算法*/intdepth(BiTreet){intrd,ld;if(!t)return0;else{rd=depth(B->lchild);ld=depth(B->rchild);if(rd>ld)returnld+1;elsereturnrd+1;}}/*depth*//*建立結(jié)點*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr){BiTreet;t=(BiTree)malloc(sizeof(structBTNode));t->data=x;t->lchild=lptr;t->rchild=rptr;return(t);}/*gettreenode*//*以后序遍歷的方式遞歸復制二叉樹*/BiTreecopytree(BiTreet){BiTreenewlptr,newrptr,newnode;if(t==NULL)returnNULL;if(t->lchild!=NULL)newlptr=copytree(t->lchild);elsenewlptr=NULL;if(t->rchild!=NULL)newrptr=copytree(t->rchild);elsenewrptr=NULL;newnode=gettreenode(t->data,newlptr,newrptr);return(newnode);}/*copytree*//*交換二叉樹的結(jié)點的左右孩子*/BiTreeswap(BiTreeb){BiTreet,t1,t2;if(b==NULL)t=NULL;else{t=(BiTree)malloc(sizeof(structBTNode));t->data=b->data;t1=swap(b->lchild);/*遞歸交換左子樹上的結(jié)點*/t2=swap(b->rchild);/*遞歸交換右子樹上的結(jié)點*/t->lchild=t2;/*交換根t的左右子樹*/t->rchild=t1;}return(t);}/*swap*//*利用循環(huán)隊列實現(xiàn)層次遍歷*/voidccOrder(BiTreet){}/*ccOrder*///定義隊列typedefstructqueue{BT*base;intfront;intrear;}queue;//隊列實現(xiàn)voidQueueStart(queue&Q)//隊列的初始化{Q.base=(BT*)malloc(size*sizeof(BT));if(!Q.base)exit(0);Q.front=0;Q.rear=0;}voidQueueInt(queue&Q,BT&p)//入隊{if((Q.rear+1)%size==Q.front)return;Q.base[Q.rear]=p;Q.rear=(Q.rear+1)%size;}voidQueueOut(queue&Q,BT&p)//出隊{if(Q.rear==Q.front)return;p=Q.base[Q.front];Q.front=(Q.front+1)%size;}/*統(tǒng)計二叉樹葉子結(jié)點，補充遞歸算法*/intLeaves(BiTreet,intsum){if(t){if(t->lchild==NULL&&t->rchild==NULL){sum++;}sum=Leaves(t->lchild,sum);sum=Leaves(t->rchild,sum);}return(sum);}/*Leaves*//*釋放二叉樹*/voidrelease(BiTreet){if(t!=NULL){release(t->lchild);release(t->rchild);free(t);}}/*release*/intmain(){BiTreet=NULL,copyt=NULL;intselect;do{按先序序列建立二叉樹遍歷二叉樹(三種遞歸方法)遍歷二叉樹(三種非遞歸方法)層次遍歷二叉樹輸出二叉樹的深度統(tǒng)計二叉樹的葉子結(jié)點數(shù)(遞歸)后序遍歷方式復制一棵二叉樹交換二叉樹所有結(jié)點的左右孩子getchar();switch(select){case1:按先序序列建立二叉樹請依次輸入結(jié)點序列：createBiTree(&t);if(t!=NULL)二叉樹創(chuàng)建成功！else二叉樹未創(chuàng)建成功！break;case2:遍歷二叉樹(三種遞歸方法)先序遍歷序列PreOrder(t);中序遍歷序列InOrder(t);后序遍歷序列PostOrder(t);break;case3:遍歷二叉樹(三種非遞歸方法)先序遍歷的非遞歸RPreorder(t);中序遍歷的非遞歸RInorder(t);后序遍歷的非遞歸RPostorder(t);break;case4:層次遍歷二叉樹按層次遍歷ccOrder(t);break;case5:輸出二叉樹的深度二叉樹的深度break;case6:統(tǒng)計二叉樹的葉子結(jié)點數(shù)(遞歸)葉子結(jié)點數(shù)為：break;case7:后序遍歷方式復制一棵二叉樹copyt=copytree(t);if(copyt!=NULL){先序遞歸遍歷復制的二叉樹PreOrder(copyt);}else復制失??！break;case8:交換二叉樹所有結(jié)點的左右孩子先序遞歸遍歷交換后的二叉樹PreOrder(swap(t));break;case0:release(t);/*釋放二叉樹*/break;default:break;}}while(select);return0;}2、編寫程序exp6_2.c，實現(xiàn)哈夫曼樹的建立和哈夫曼編碼。若有一組字符序列{a,c,e,i,s,t,w},對應的出現(xiàn)頻率為{10,1,15,12,3,4,13}。以此序列創(chuàng)建哈夫曼樹和哈夫曼編碼?；卮鹣铝袉栴}，補充完整程序，并調(diào)試運行驗證結(jié)果。構(gòu)造該序列的哈夫曼樹，畫出哈夫曼樹的形態(tài)。(以結(jié)點值左小右大的原則)寫出對應的哈夫曼編碼。a(111)c(11010)e(10)i(00)s(11011)t(1100)w(01)計算編碼的WPL。WPL=(1+3)*5+4*4+10*3+(12+13+15)*2=146exp6_2.c程序代碼參考如下：#include<stdio.h>#defineMAXVALUE10000/*定義最大權(quán)值*/#defineMAXLEAF30/*定義哈夫曼樹中葉子結(jié)點個數(shù)*/#defineMAXNODEMAXLEAF*2-1#defineMAXBIT10/*定義哈夫曼編碼的最大長度*/

typedefstruct/*哈夫曼編碼結(jié)構(gòu)*/{intbit[MAXBIT];intstart;}/*哈夫曼樹結(jié)點結(jié)構(gòu)/*哈夫曼樹結(jié)點結(jié)構(gòu)*/typedefstruct{chardata;intweight;intparent;intlchild;intrchild;}HNodeType;voidHuffmanTree(HNodeTypeHuffNode[],int*hn);voidHuffmanCode(HNodeTypeHuffNode[],HCodeTypeHuffCode[],intn);voidHuffmanTree(HNodeTypeHuffNode[],int*hn)/*哈夫曼樹的構(gòu)造算法*/{inti,j,m1,m2,x1,x2,n;getchar();/*輸入葉子結(jié)點個數(shù)*/for(i=0;iv2*n-l;i++)/*數(shù)組HuffNode[]初始化*/{HuffNode[i].data=O;HuffNode[i].weight=O;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;}for(i=0;i<n;i++){/*輸入n個葉子結(jié)點的權(quán)值*/getchar();}for(i=0;i<n-1;i++)/*構(gòu)造哈夫曼樹*/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j++){if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1){m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}}/*將找出的兩棵子樹合并為一棵子樹*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[xl].weight+Hu