數(shù)據(jù)結(jié)構(gòu)上機實驗四

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗四實驗目的： 熟悉二叉樹結(jié)點的結(jié)構(gòu)和對二叉樹的基本操作； 掌握對二叉樹每一種操作的具體實現(xiàn)； 學會利用遞歸方法編寫對二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進行處理的算法。實驗內(nèi)容：定義二叉樹的類型#defineMaxsize100#defineMaxwidth40typedefcharelemtype;typedefstructnode{elemtypedata;structnode*left,*right;}BTree;2、中序遍歷的（非）遞歸算法voidInOrderTraverse(BiTreeT){ InitStack(S);p=T; q=newBiTree;while(p||StackEmpty(S){ If(p){Push(S,p);P=p->lchild;}Else{ Pop(S,q);cout<<q->data;p=q->rchild;}}}求二叉樹的深度intDepth(BiTreeT){ If(T==NULL) Return0;Else{M=Depth(T->lchild);N=Depth(T->rchild);If(M>N)Return(M+1);elsereturn(N+1);}}哈夫曼樹和哈夫曼編碼：從終端輸入若干個字符，統(tǒng)計字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為節(jié)點的權(quán)值，建立哈夫曼樹，然后對各字符進行哈夫曼編碼，最后打印哈夫曼樹和對應的哈夫曼編碼。#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<string.h>#include<stdio.h>#definemaxsize100structfrequence{ chara; intn;};typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidFrequent(){ frequencech[27]; inti=0; for(;i<=26;i++) { ch[i].n=0; } cout<<"請輸入各個字符（輸入#鍵結(jié)束輸入）："; charc; cin>>c; boolflag; while(c!='#') { i=1; flag=false; for(;i<=ch[0].n;i++) { if(c==ch[i].a) { flag=true; break; } } if(flag) { ch[i].n++; } else { ch[0].n++; ch[ch[0].n].n++; ch[ch[0].n].a=c; } cin>>c; } for(intj=1;j<=ch[0].n;j++) { cout<<ch[j].a<<""<<ch[j].n<<endl; }}voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){ intj,k=1; while(HT[k].parent!=0) k++; s1=k; for(j=1;j<=i;++j) if(HT[j].parent==0&&HT[j].weight<HT[s1].weight) s1=j; k=1; while((HT[k].parent!=0||k==s1)) k++; s2=k; for(j=1;j<=i;++j) if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1) s2=j;}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){ intm,i,s1,s2,start,c,f; HuffmanTreep; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++w) { p->weight=*w; cout<<"輸出各個元素的權(quán)值"<<endl; cout<<"HT["<<i<<"].weight="<<p->weight<<""; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }cout<<endl<<endl<<"建立的哈夫曼樹如下列次序:"; for(i=n+1;i<=m;++i) { Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; cout<<endl<<"HT["<<s1<<"]andHT["<<s2<<"]create"; cout<<"HT["<<i<<"],weight="<<HT[i].weight; } cout<<"\n哈弗曼樹表"<<endl; cout<<"iweightparentlchildrchild"<<endl; for(p=HT+1,i=1;i<=m;i++,p++) cout<<setw(2)<<i<<setw(7)<<p->weight<<setw(6)<<p->parent<<setw(7)<<p->lchild<<setw(8)<<p->rchild<<endl; HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); char*cd; cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; cout<<"哈夫曼編碼如下:"<<endl; for(i=1;i<=n;++i) { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); printf("\nHT[%d]節(jié)點的哈夫曼編碼是:%s",i,HC[i]); } cout<<endl; free(cd);}voidmain(){ HuffmanTreeHT; HuffmanCodeHC; Frequent(); intm,n; int*w,W[maxsize]; cout<<"請輸入哈夫曼樹的元素個數(shù):"; cin>>m; for(n=0;n<m;++n) { cout