南邮数据结构上机实验二二叉树的基本操作及哈夫曼编码译码系统的实现

1、（2015 / 2016学年第二学期）课程名称实验名称实验时间指导单位指导教师学生姓名 学院（系）数据结构a二叉树的基本操作及哈夫曼编码译码系统的实现2016年 4 月 14 曰计算机科学与技术系班级学号管理学院专 业信息管理与信息系统骆健实习题名:二叉树的基本操作班级_姓名学号円期2016.04. 14一、问题描述设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求 一棵二叉树屮叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。设汁算法, 按白上到下，从左到右的顺序，按层次遍历一棵二叉树。设计main函数，测试上述每 个运算。二、概要设计文件tree, cpp屮在该文

2、件屮定义二义树的链式存储结构，川队列实现二义树的层 次遍历，并且编写实现二叉树的各种基本楝作函数。其中乜括结点类btnode,循环队 列类seqqueue,二叉树类binarytree、主函数main的代码如图所示。三、详细设计1. 类和类的层次设计程序定义/循环队列seqqueue炎和二义树binar*ytree炎。seqqueue炎主要是用队列 实现，层次遍历。运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算 树的高度，最后删除二叉树。seqqueue-int front, rear;-int maxsize;-btnode<t> *q;+seqqueue(in

3、t msize);+seqqueue() delete q;+bool isemptyo const return front 二二 rear;+bool isfull() const return (rear + 1) % maxsize =front;+bool front(btnode<t> *&x)const;+bool enqueue(btnode<t> *x);+bool dcqucuc();+vnid clearfv front = rear = (v 1(a)循环队列类tbinarytree+binarytree():s(l(x)root = n

4、ull;)+-binarytree()delete root;+bool clear();+void maketree(constt&x,binarytree<t>&left,binarytree<t>& right);+int high(btnode<t>*p);+int node_num(btnode<t>*p);+btnode<t>*copy (btnode<t>*t);+void exchange( btnode<t> *&t);十void level_traversal

5、(void( *visit)(t&x);#seqqueue<t> s;-void clear(btnode<t>* &t);-void level_traversal(void(*visit)(t&x),btnode<t>*t);(b)二叉树类2. 核心算法程序利川循环队列seqqueue类通过不断出队#输出节点的值，将左右孩子入队直到队 列为空实现二义树的层次遍历。并运用后序遍历思想，将二义树树分解为左右子树和根结点, 利用(p -ichild)和(p -rchild)计算结点数鬥，并通过交换结点的左右子树实现左右交 换，计算树的高

6、度，最后删除二叉树。核心算法主要是二叉树binarytree炎中的high, node num，exchange, level traversal网个函数，其设计流程图如下：p=nullnexchange ()btnode t-level_traversal0四、程序代码template<class t>int binarytree<t>:node_num(btnode<t>*p)/叶子结点if(p)if(p -> ichild = null && p-> rchild = null) return 1;elsereturn no

7、de_num(p -> ichild) + node一num(p -rchild);elsereturn 0; tcmplatc<class t>void binarytree<t>:exchange(btnode<t>*&t)/左右子树交换if(t)btnode<t>*q = t -> ichild; t -> ichild = t->rchild; t -> rchild = q;exchange(t -> ichild);exchange(t -> rchild); template<

8、class t>void binarytree<t>:level_traversal(void(*visit)(t&x)/层次遍历lcvcl_travcr$al(visit, root); cout« endl;/s次遍历template<class t>void binarytree<t>:level_traversal(void(*visit)(t&x),btnode<t>*t) btnode<t> *a;visit(t -element); if(t > ichild)s.enqucuc(t

9、 -> ichild); if(t -> rchild)s.enqueue(t rchild); while(s.front(a) = true)if(a -ichild)$.enqucuc(a -> ichild);if(a -> rchild)s.enqueue(a -> rchild);visit(a -> element); s.dequeue();五、测试和调试1. 测试用例和结來测试结果如下图2. 结果分析1）程序能够正确的实现二叉树的基木的逑立、删除、复制、遍历以及结点计算等 基本操作。2）山测试结果来希，可以在输出数据吋以二义树阉形的形式输出

10、，更简单直观， 因此程序还有待改进。实习题名：哈夫曼编码和译码系统班级_姓名学号日期2016.04. 14一、问题描述所没计的系统重s显示以卜菜单项.b建树：读入字符集和各字符频度，建立哈夫曼树。t遍历：先序和屮序遍历二叉树。e生成编码：根据已建成的哈夫玆树，产生各字符的哈夫曼编码。c编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，敁示编码结果，并将输入的字符中及其编码结果分别保存在磁盘文件 textfile. txt 和 codefile, txt 中。d译码：读入codehle. txt,利用已建成的哈夫曼树进行译码，卯将揮码结架存入磁盘文件result, txt

11、中。p打印:屏幕显示文件 textfile. txt、codefile, txt 和 result, txt。x退岀。二、概要设计文件huffman, cpp中定义了四个类,分别足优先权队列类prioqueue和结点类 btnode、二叉树炎binarytree以及哈大曼树炎hfmtree，其中卩合夫曼树炎hfmtree 继承了二叉树炎binarytree。主函数mian的代码如图所示：三、详细设计1.类和类的m次结构程序定义了优先权队列类prioqueue存储元素，为便于实哈夫曼树的建树运算，定 义了哈夫曼树类hfmtree是二叉树类binarytree的派生类，新增私有的数据成员 weig

12、ht保存二义树根的权值。成员函数getw和putw川于存取该值。prioqueue-t*q-int n，maxsize +prioqueue(int msize = 20);+prioqueue() delete q; +bool isemptyo const return n = 0; +bool isfull() const) return n = maxsize;) +void appcnd(const t&x);+void serve(t&x);-void adjustdown(int r, int j);void adjustup(int j);binarytree-

13、int i;+binarytree()root = null; i = - i；+binarytree()+void maketree(const t&x，const char &y，binarytree<t&left， binarytree<t>& right);十void preorder(void (*visit)(t&x);+void inorder(void (*visio(t&x);+void create一code();+void create_code_out();+void code();十void compi

14、le();+void print();-void preorder(void (*visit)(t&x), btnode<t>*t);-void inorder(void (*visit)(t&x), btnode<t>*t);-void create_code(btnode<t>*t);-void create_code_out(btnode<t>*t);-void code(btnode<t>*t);-void make(btnode<t*t，char a);-void compile(btnode<t

15、>*t);thfmtree-t weight+operatort() const return weight; +t getw() return weight; +void putw(const t&x) weight = x; +void setnull() root = null; 2.核心算法定义了类之后，通过函数make_ht建树，将相应的字符和权值录入。通过遍历 哈夫曼树，产生毎个叶子节点的哈夫曼编码，当遍历访问某个叶节点是，从该结点 到根的路径讨以确定该叶结点所代表的字符的编码。实现译码时，首先将字符读入 一维数组，根裾0或1向左走向右走直到叶了结点，并将结果写入文件

16、中。其中关 键函数編码code和译码compile以及打印print的流程图如下。code()下接下一页btnode<t-*c;t=t->lckild:t=t->rchild;t1n3-*+.ofstreatnouts(* result t.cout«hcaimot open t.return;cout <c-: ch、 cout <endl;compilecharshcout«*cksot openrreturn:cout«*cksot openrreturn:cout«*cksot openrreturn:cout -

17、textfile txtprino四、程序代码hfmtree<int> ht;int num;void make_ht()char str 100;int weight100;cout« "请输入字符个数："cin » num;/建树cout«"诺输入权值 for(int i = 0; i < num; i+)cin » weightuj; cout« n请输入相应字符集cin » str;ht = crcatchfmtrcc(weight, str，num); void travers

18、al_ht()ht.prcordcr(visit);ht.inorder(visit); template<class t>void binarytrcc<t>:crcatc_codc() create_code(root);tempi ate<c lass t>void binarytree<t>:create_code(btnode<t>*t)if(t)if(t -> parent)for(intj = 0; j <= i;j+)t -> zj = t -> parent -zfjl; /餐制双亲的編码域i

19、+;t -> zi = t-> val; /在编码域屮加入a己的编码create_code(t -> ichild);/递归，先左孩子，再右孩子create_code(t -> rchild); i-;template<class t>void binarytree<t>:create_code_out()/生成编码并输岀create_code_out(root);tcmplatc<class t>void binarytree<t>:create_code_out(btnode<t>*t)ifif(t -&g

20、t; ichild = t -> rchild)/叶子结点cout«t -> ch «/输出叶子结点中的字符int i = 0;while(t -> zfi != -1)cout « t -> zlij;/输出编码域i+;cout« endl;create_code_out(t->lchild);create_code_out(t->rch ild);template<class t>void binarytree<t>:code()code(root);template<class t&

21、gt;void binarytree<t>:code(btnode<t>*t)/编码ofstrcam outf("tcxtfilc.txth); if(!outf)cout « "cannot open the filcnh; return;ofstream outs(ncodefile.txt"，ios:trunc); if(!outs)cout « "cannot open the filcnh; return;outs.close(); char str2 10()1;cout« "谘

22、输入由字符集屮字符组成的任意字符中："cin » str2;outf « str2;outf.close();int 1 = strlen(str2);cout« "编码为： << endl; for(int i = 0; i < 1; i+)make(root, str2i); cout« endl;tempi ate<c lass t>void binarytree<t>:make(btnode<t> *t,char a)int i = 0; ifif(t -> ch =

23、 a)/找到相应字符ofstream outs("codefile.txtn，ios:app); while(t -> zfi != -1)cout « t -> zlij;/输出编码域outs « t -> zij; /将编码写入文件 i+;outs.closc();return;make(t -> ichild, a);make(t -> rchild, a);/译码tcmplatc<class t>void b inarytree<t>: compile()compile(root);tempi ate&

24、lt;c lass t>void binarytree<t>:compile(btnode<t> *t) ifstream inf("codefile.txt"); if(!inf)cout« "cannot open the filen" return;ofstream outs(result.txt"，ios:trunc); if(!outs)cout« "cannot open the filen" return;outs.closc(); char *re; char

25、 tmp; int n = 0;while(inf.get(tmp) != v)1)n+；/确定字符数量inf.closeo;re = new charfn+1;int n2 = 0;ifstream in("codefile.txt"); if(!in)cout«cannot open the filen”； return;)while(in.get(tmp) != 0)rcn2 = tmp;/将字符懊入一位数组n2+;btnode<t> *c;cout« "译码为：" int n3 = 0; while(n3 <

26、 n)while(t)c = t;if(reln3j = *0*)/左0右1根据0或1向左走向右走直到叶子结点t = t -> ichild;elset = t -> rchild; n3+;ofstream outs(uresult.txtn,ios:app); if( louts)cout « "cannot open the filcn" return;cout « c -> ch;/输出字符outs « c -> ch;/将结果写进文件outs.close();t = root; n3-;cout« e

27、ndl;void print()char str;ifstream a(textfile.txt"); ifstream b(ncodefile.txt"); ifstream c(mresult.txt"); if(!a)cout « "cannot open the filen.； return;if(!b)cout « "cannot open the filcnh; return;cout« cannot open the filen" return;cout« "textfi

28、le.txt 内的内容为：" while(a.get(str) != '0')cout« str; cout« endl;cout« "codefile.txt 内的内容为："； while(b.get(str) != '0')cout« str; cout« endl;cout« "result.txt 内的内容为 while(c.get(str) != '0')cout« str; cout« cndl;a. close()

29、;b. close();c. close();五、测试和调试1. 测试用例和结果1)输入b选择建树操作d:vc+debugcpp1 .exe"输入字符个数：2）分别输入a, b, c, d以及权值2, 4, 1, 1,建树d:vc+debugcpp1 .exe"输入t得到该树的遍历"d:vc+debugcpp1 .exe*l-xitl3)b i e c d p x作项1112 2 12 4- 4 2 .为益意先中ii!r d:vc+debugc pp1 .exe*4) 输入e生成编码输入操作顶網为：:0：10：110i：lll雑任惹键继续5) 输入c编硏,输入字符

30、屮aabdcbdacbdadcdb编d:vc* *debugcpp1 .exe*l 系拜 9 i i i i i i输入由字符集中字符组成的任意字符串：aabdcbdacbdadcdb砑为：101001111100111101100111101111101110 舌技任意键继续 6）输入i）选择译码7）输入p选择打印文件内容d:vc* +debugcpp1.exe*绘夫曼编碑和译码糸羡 rr列序号递行运m:卜蝴 mmmmmt* e-至成编碑* c薄码*d-译码*p_打印*»*"*<x-追出*mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

31、mmmmmmmmmej输入操作顶-extf ile txt 内的内容为:aabdcbdacbdadcdb 一odcfilc.txt内的内脊为 s10100111110011110110w111101111101110 pesult.txt内的内容为:aabdcbdacbdadcdb请按任意键纟.8）最后输入x退出2.结來分析1）程序能够完全实现题n的要求，建树，遍历生成编码，编码以及译码打印都能 成功完成2）不足之处在于译码方面，不能够实现tl己输入一串编码來实现译码，下一步的 目标是解决这个问题实习小结通过这次课程设计，使我对二义树的相关知识有了更深的理解，我们要根裾不同的需求, 采用不m的

32、数据存储方式，不一定耍用栈，二叉树等高级类型，有时用基本的一维数组，只 要运用彳y当，也能达到相同的效果，甚:辛:更好。同样的，这次在在程序的运行与调试过程中 也出现了很多错误，通过反复地阅读课木上的知识，丼且又对哈夫曼树的构造以及哈夫曼编 码译码有了更深的理解。在完成实验的过程中，不倥地修改与调试，在凋试过程中，我也汄识到了自己更多的不 足以及在细节上的把握不够，如对队列的知识不够熟悉，在使用过程中出现了很多问题。在 以p的学习中我要集中精力、端正态度，争取把知识学得更扎实、更全而。附录，1.二叉树的基本操作#includeiostream #includestring using name

33、space std;template<class t>struct btnode /结点类btnode()lchild = rchild = null;btnode(const t& x)element = x;ichild = rchild = null;btnode(const t&x, btnode<t>*l, btnode<t>*r) element = x;ichild = 1; rchild = r;t element;btnode<t> *lchild, *rchild;template<class t>

34、/循环队列类class seqqueuepublic:seqqueue(int msize);seqqueue()delete q;jbool isemptyo const return front = rear;bool isfull() const return (rear + 1) % maxsize = front;)bool front(btnode<t> *&x)const;bool enqueue(btnode<t> *x);bool dequeue();void clear() front = rear = 0;private:int front

35、, rear; int maxsize;btnode<t> *q;template<class t>seqqueue<t>:seqqueue(int msize) /构造函数 maxsize = msize; q = new btnode<t>*maxsize; front = rear = 0;)template<class t>/取队头元索/在队尾插入xbool seqqueue<t>:front(btnode<t> *&x)const if(isempty() return false;x = q

36、(front+l) % maxsize; return true; template<class t>bool seqqueue<t>:enqueue(btnode<t> *x) if(isfull()cout« "full" « endl; return false;qrear = (rear+1) % maxsize = x; return true;) template<class t>bool seqqueue<t>:dequeue()/删除队ik*元素if(isempty()cout

37、« ”underflow” << endl; return false;front = (front+1) % maxsize; return true;)template<class t> /visit 函数void visit(t&x)cout« x «template<class t>/二叉树炎class binarytreepublic:binarytree():s( 100) root = null;)binarytree()delete root; bool clear();void maketree(con

38、st t&x,binarytree<t>&left,biniirytree<t>& right);int high(btnode<t>*p);int nodenum(btnode<t*p);btnode<t>*copy (btnode<t*l); void exchangc(btnodc<t> *&t); void level_traversal(void(*visit)(t&x);btnode<t>*root;protected:seqqueue<t> s;

39、private:void clear(btnode<t>* &t);void level_traversal(void(*visit)(t&x)5btnode<t>*t);/建树template<class t>void biniirytree<t>:maketree(const t&x，binarytree<t&left,binarytree<t>& right) if(root | &left = &right) return;root = new btnode<

40、t(x，left.root，right.root);left.root = right.root = null;template<class t>bool binarytree<t>:clear()/删除clear(root); if(root = null) return true; elsereturn false;template<class t>void binarytree<t>:clear(btnode<t>*& tmp) /删除clear(tmp -> ichild); clear(tmp -rchild)

41、; delete tmp; tmp = null; template<class t>int binarytree<t>:high(btnode<t>*p) /高度if(p = null) return 0;else if(p -> ichild = null && p -> rchild = null) return 1;elsereturn (high(p -> ichild) > high(p -> rchild) ? high(p -> ichild) + 1 : high(p -> rchi

42、ld) +1);template<class t>int binarytree<t>:node_num(btnode<t>*p)/叶子结点if(p)1if(p -> ichild = null && p-> rchild = null) return 1; elsereturn node_num(p -> ichild) + node_num(p -> rchild);elsereturn 0;) template<class t>btnode<t>*b i naryt ree<t>

43、:copy(btnode<t>*t)/s 制if(!t) return null;btnode<t>*q = new btnode<t(t -element); q -> ichild = copy(t > ichild); q -> rchild = copy(t rchild); return q;)template<class t>void binarytree<t>:exchange(btnode<t>*&t)/zt右子树交换if(t)btnode<t>*q = t -> ic

44、hild; t > ichild = t->rchild; t -> rchild = q;exchange(t -> ichild); exchange(t -> rchild); tcmplatc<class t>void binarytree<t>:level_traversal(void(*visit)(t&x)/层次遍历leve匕traversai(visit，root); cout« endl;)/z次遍历template<class t>void binarytree<t:leveltrav

45、ersal(void(*visit)(t&x)，btnode<t*t) btnode<t> *a;visit(t -> element); if(t -> ichild) s.enqueue(t -> ichild); if(t -> rchild) s.enqueue(t -> rchild); while(s.front(a) = true)1if(a > ichild)s.enqueue(a -> ichild); if(a rchild) s.enqueue(a -> rchild);visit(a ->

46、element); s.dequeue();)int main()binarytree<chart100，a，b，temp; int num = 0, high = 0; t7.maketree(h，a，b); tl8j.maketree(t, a, b); t3.maketree(fd； t7，t8);t4.maketreefe'，a，b);tl5j.maketree('f a, b);t6.maketree(<t, a, b);tl.maketree(b，t3，t4);t2.maketree(c，t5，t6);to.maketree('a，tl，t2);

47、cout« "二义树z的层次遍历结果:n"toj .level_traversal( visit);temp.root = temp.copy(t()l.root);cout«"巾二叉树z s制的二叉树temp的层次遍历结果:nn;temp.level_traversal(visit);t0 .exchange(to .root);cout«n交视左右子树后的二叉树z的层次遍历to.level_traversal( visit);nurn = t0.node_num(t0.root);cout«”二叉树z的叶子结点数为:n&

48、quot;« num « ”n"high = t 0. high(t 0 .root);cout«"二叉树 z 的高度为:n" « high « °n"cout«"删除二叉树z:成功输出1，失败输出0n" « t0.clear()« "n" return 0;2. 哈夫曼编码和译码系统#include <iostream>#include <fstream>#includestring/优先权队列类#i

49、nclude <cstring> using namespace std; template<class t> class prioqueue public:prioqueue(int msize = 20);prioqueue() delete q;( bool isemptyo const return n = 0; bool isfulio const return n = maxsize; void append(const t&x); void serve(t&x);private:void adjustdown(int r，int j); v

50、oid adjustup(int j);t *q;int n，maxsize;template<class t>prioqueue<t>:prioqueue(int msize) maxsize = msize; n 二 0;q = newtmaxsize;template<class t>void prioqueue<t>:adjustup(int j)int i = j;t temp = qi;while (i > 0 && temp < q(i- 1)/2) qi=q(i-l)/2; i = (i-l)/2;qi

51、 = temp;template<class t>void prioqueue<t>: append(const t&x)/插入新元索if(isfull()cout « "overflow" « endl; return;)qfn+l = x;adjustup(n-l);template<class t>void prioqueue<t>:serve(t&x)if(isempty()cout « "underflow" « endl; return;)

52、x = q0; q0 = q-n;adjustdown(0, n-1);/删除堆顶元素template<class t>void prioqueue<t>:adjustdown(int r,int j)/向上调整int child = 2 * r + 1;t temp = qr; while(child <= j)if(child < j) && (qchild > qchild+l) child+;if(temp <= qchild) break;q(child - 1) / 2 = qchild; child = 2 * ch

53、ild + 1;q(child - 1) / 2 = temp;template<class t> struct btnode/结点类btnode()lchild = rchild = null;) btnode(const t&x, const char &y)element = x; ch = y;ichild = rchild = parent = null; memset(z，-1，sizeof(z);btnode(const t&x, const char &y，btnode<t*l，btnode<t>*r) elemen

54、t = x; ch = y;ichild = 1; rchild = r; parent = null; memset(z，-1，sizeof(z);t element;btnode<t> *lchild, *rchild, parent; char ch; int val; int z100;teniplate<class t>/二叉树类class binarytreepublic:binarytree()root = null; i = -1;binarytree()void maketree(const t&x, const char &y, bi

55、narytree<t>&left, binarytree<t>& right); void preorder(void (*visit)(t&x); void inorder(void (*visit)(t&x); void create_code();void create_code_out(); void code(); void compile(); void print();btnode<t>*root;private: int i;void preorder(void (*visit)(t&x), btnod

56、e<t>*t); void inorder(void (*visit)(t&x), btnode<t>*t); void create_code(btnode<t>*t);void create_code_out(btnode<t>*t); void code(btnode<t>*t); void make(btnode<t*t,char a); void compile(btnode<t>*t);template<class t>void binarytree<t:maketree(con

57、st t&x, const char &y，binarytree<t>&left, b i narytree<t>& right)/建树if(root | &left = &right)return;root = new btnode<t(x，y，left.root，right.root); if(left.root != right.root)left.root -parent = root; right.root -> parent = root; left.root -> val = 0; righ

58、t.root -> val = 1;)left.root = right.root = null;)template<class t>/visit 闲数void visit(t&x)cout « x « m m:template<class t>void binarytree<t>:preorder(void (*visit)(t&x)/先序遍历cout« "先序遍历为:"preorder(visit, root); cout« endl;template<class t>void binarytree<t>:preorder(void (*visit)(t&x)，btnode<t>*t)if(t)visit(t -> element); preorder(visit, t -> ichild); p