实验报告2-二叉树及哈夫曼编码

1、挣卫推遂薯实验报告（2013/2014学年第二学期）课程名称数据结构A实验名称实验二二叉树的基本操作及哈夫曼编码译码系统泌、的实现实验时间2014年4月8日指导单位计算机学院计算机软件教学中心指导教师朱立华学生姓名高怡馨班级学号B12140113学院（系）教育科学与技专业教育技术学术学院实验名称实验二二叉树的基本操作及哈夫曼编码译码系统的实现指导教师朱立华实验类型设计实验学时2实验时间2014.4.8一、实验目的和要求（1）掌握二叉链表上实现二叉树基本去处的方法。（2）学会设计基于遍历的求解二叉树应用问题的递归算法。（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。二、实验环境（实验

2、设备）硬件：微型计算机软件：MicrosoftVisualC+6.0三、实验原理及内容实验题一：在一叉链表上实现一叉树运算（1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、父换一棵二叉树的左右子树。（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。（3）设计main函数，测试上述每个运算。内容：1、建立头文件BTree.H,在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。冋时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。实验

3、报告实验报告 inttempi;inttempr;if(!t)return0;templ=GetHeight(t-lChild);tempr=GetHeight(t-rChild);if(templ+tempr+)returntempi;elsereturntempr;Test.Cpp：#includeBTree.hintmain()BinaryTreevchara,b,x,y,z;y.MakeTree(E,a,b);z.MakeTree(F,a,b);MakeTree(C,y,z);y.MakeTree(D,a,b);z.MakeTree(B,y,x);coutvv前序遍历vvendl;z.

4、PreOrder(Visit);coutvvendl;coutvv中序遍历vvendl;z.InOrder(Visit);coutvvendl;coutvv后序遍历vvendl;乙PostOrder(Visit);coutvvendl;coutvv层次遍历vvendl;z.LevelOrder(Visit);coutvvendl;coutvv结点数量:；coutvvz.Size()vvendl;z.Exchange();coutvv左右交换后的前序遍历vvendl;实验题二：哈夫曼编码和译码系统(1)所设计的系统重复显示以下菜单项：B建树：读入字符集和各字符频度，建立哈夫曼树。T遍历：先序和中

5、序遍历二叉树。E生成编码：根据已建成的哈夫曼树，产生各字符的哈夫曼编码。C编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。D译码：读入codefile.txt,利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt中。P打印：屏幕显示文件textfile.txt、codefile.txt和result.txt。X退出。源代码#includeviostream#include#include#includevqueue#includeus

6、ingnamespacestd;int*weightArray;strings;string*codeArray;templatestructBTNodeTelement;BTNode*lChild,*rChild;BTNode()lChild=rChild=NULL;BTNode(constT&x)element=x;lChild=rChild=NULL;BTNode(constT&x,BTNode*l,BTNode*r)element=x;lChild=l;rChild=r;templatevclassTclassBinaryTreepublic:BinaryTree()root=NULL

7、;BinaryTree()boolisEmpty()constreturnroot=NULL;voidclear()postClear(root);boolretRoot(T&x)const;voidmakeTree(const&x,BinaryTreevT&left,BinaryTreevT&right);voidbreakTree(T&x,BinaryTreevT&left,BinaryTreevT&right);voidpreOrder()preOrder(root);voidinOrder()inOrder(root);voidpostOrder()postOrder(root);BT

8、NodevT*copy(BTNode*t);intsize()returnsize(root);voidchange。change(root);voidbreathFirst()breathFirst(root);intheight()returnheight(root);voidleaf()prePrint(root);protected:BTNodevT*root;private:voidclear(BTNodevT*t);voidchange(BTNodevT*t);voidpostClear(BTNodevT*t);voidprePrint(BTNodevT*t);intsize(BT

9、NodevT*t);intheight(BTNode*t);voidpreOrder(BTNodevT*t);voidinOrder(BTNodevT*t);voidpostOrder(BTNodevT*t);voidbreathFirst(BTNodevT*t);voidvisit(T&x)coutx;templateboolBinaryTreevT:retRoot(T&x)constif(root)x=root-element;returntrue;elsereturnfalse;templatevoidBinaryTreevT:makeTree(const&x,BinaryTreevT&

10、left,BinaryTreevT&right)if(rootII&left=&right)return;root=newBTNode(x,left.root,right.root);left.root=right.root=NULL;templatevoidBinaryTree:breakTree(T&x,BinaryTreevT&left,BinaryTreevT&right)if(!rootII&left=&rightIIleft.rootIIright.root)return;x=root-element;left.root=root-lChild;right.root=root-rC

11、hild;deleteroot;root=NULL;templatevclassTvoidBinaryTreevT:preOrder(BTNodevT*t)if(t)visit(t-element);preOrder(t-IChild);preOrder(t-rChild);templatevoidBinaryTreevT:inOrder(BTNodevT*t)if(t)inOrder(t-lChild);visit(t-element);inOrder(t-rChild);templatevoidBinaryTreevT:postOrder(BTNodevT*t)if(t)postOrder

12、(t-lChild);postOrder(t-rChild);visit(t-element);templatevoidBinaryTreevT:clear(BTNodevT*t)deletet;t=NULL;templatevoidBinaryTreevT:postClear(BTNodevT*t)if(t)postClear(t-lChild);postClear(t-rChild);deletet;templatevclassTBTNodevT*BinaryTreevT:copy(BTNodevT*t)if(!t)returnNULL;BTNodevT*q=newBTNode(t-ele

13、ment);q-IChild=copy(t-IChild);q-rChild=copy(t-rChild);returnq;templateintBinaryTreevT:size(BTNodevT*t)if(!t)return0;elsereturnsize(t-lChild)+size(t-rChild);templatevoidBinaryTree:change(BTNode*t)if(!t)return;BTNode*q=copy(t-rChild);clear(t-rChild);t-rChild=t-lChild;t-lChild=q;change(t-lChild);change

14、(t-rChild);templatevoidBinaryTreevT:breathFirst(BTNodevT*t)if(!t)return;queuevBTNodevT*ql;ql.push(t);BTNode*node;while(!q1.empty()node=q1.front();visit(node-element);q1.pop();if(node-lChild)q1.push(node-lChild);if(node-rChild)q1.push(node-rChild);templateintBinaryTree:height(BTNode*t)if(t=NULL)retur

15、n0;elseintm=height(t-lChild);intn=height(t-rChild);return(mn)?(m+1):(n+1);templatevclassTvoidBinaryTreevT:prePrint(BTNodevT*t)if(t)if(t-lChild=NULL)&(t-rChild=NULL)visit(t-element);return;prePrint(t-lChild);prePrint(t-rChild);templatevclassTclassPrioQueuepublic:PrioQueue(intmSize=20);PrioQueue()dele

16、teq;boolIsEmpty()constreturnn=0;boolIsFull()constreturnn=maxSize;voidAppend(constT&x);voidServe(T&x);private:voidAdjustDown(intr,intj);voidAdjustUp(intj);T*q;intn,maxSize;templatePrioQueue:PrioQueue(intmSize)maxSize=mSize;n=0;q=newTmaxSize;templatevclassTvoidPrioQueuevT:AdjustUp(intj)inti=j;Ttemp=qi

17、;while(i0&tempvq(i-l)qi=q(i-l)/2;i=(i-1)/2;qi=temp;templatevoidPrioQueuevT:Append(constT&x)if(IsFull()coutvvOverflow;return;qn+=x;AdjustUp(n-1);templatevoidPrioQueuevT:Serve(T&x)if(IsEmpty()coutvvUnderflow;return;x=q0;q0=q-n;AdjustDown(0,n-1);templatevclassTvoidPrioQueuevT:AdjustDown(intr,intj)intch

18、ild=2*r+1;Ttemp=qr;while(childv=j)if(childvj)&(qchildqchild+1)child+;if(tempv=qchild)break;q(child-1)/2=qchild;child=2*child+1;q(child-1)/2=temp;templatevclassTclassHfmTree:publicBinaryTreevTpublic:operatorT()constreturnweight;TgetW()returnweight;voidputW(constT&x)weight=x;voidSetNull()root=NULL;voi

19、dcode(string&c)code(root,c);voiddecode(strings);private:Tweight;voidcode(BTNode*t,string&c);templatevoidHfmTree:decode(stringdecodeString)if(codeArray=NULL)cout尚未编码！endl;return;BTNode*searchNode=root;for(inti=0;idecodeString.length();i+)if(decodeStringi!=0&decodeStringi!=1)cout所给码格式不正确！lChild=NULL&s

20、earchNode-rChild=NULL)Tvalue=searchNode-element;for(intj=0;js.length();j+)if(value=weightArrayj)coutlChild;if(decodeStringi=T)searchNode=searchNode-rChild;if(searchNode-lChild=NULL&searchNode-rChild=NULL)Tvalue=searchNode-element;for(intj=0;js.length();j+)if(value=weightArrayj)coutsj;break;coutendl;

21、templatevoidHfmTreevT:code(BTNodevT*t,string&c)if(t)if(t-lChild=NULL&t-rChild=NULL)for(inti=0;ielement=weightArrayi)codeArrayi=c;哈弗曼编码是/coutNOi;哈弗曼编码是cout字符vvsi的权重是”weightArrayi,lChild!=NULL)stringls;ls.assign(c);ls.append(O);code(t-lChild,ls);if(t-rChild!=NULL)stringrs;rs.assign(c);rs.append(l);cod

22、e(t-rChild,rs);templateHfmTreevTCreateHfmTree(T*w,intn)PrioQueuepq(n);/空优先权队列HfmTreevTx,y,z;/空哈夫曼树for(inti=0;ivn;i+)构造n棵只有一个结点的哈夫曼树乙makeTree(wi,x,y);z.putW(wi);pq.Append(z);z.SetNull();for(i=1;i&p)couts;weightArray=newints.length();codeArray=newstrings.length();for(inti=0;is.length();i+)cout请输入第(i+1

23、)个字符的权值：”weightArrayi;p=CreateHfmTree(weightArray,s.length();p.postOrder();voidcreateCode(HfmTreevint&p)if(codeArray=NULL)coutencodeString;coutvvn经过编码的码值为：;for(inti=0;ivencodeString.length();i+)for(intj=0;jvs.length();j+)if(sj=encodeStringj)coutvvcodeArrayj;break;coutvvendl;voidmain()boolflag=true;H

24、fmTreevintp;stringdecodeString;while(flag)coutvvB建树vv”T遍历vv”E生成编码vvendl;coutvvC编码vv”D译码vv”X退出vvendl;coutvv请输入指令：;charc;cinc;coutvvendl;switch(c)caseB:input(p);break;caseT:if(p!=NULL)cout前序遍历：p.preOrder();coutendl;coutp.inOrder();coutendl;cout后序遍历：;p.postOrder();coutendl;cout广度优先遍历：;p.breathFirst();coutendl;elsecoutdecodeString;p.decode(decodeString);break;caseX: