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

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

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

3、：需要用到队列的有关操作。清除一棵二叉树，并释放结点空间构造一棵二叉树 BT撤销一棵二叉树BT先序遍历二叉树 BT中序遍历二叉树 BT后序遍历二叉树 BT层次遍历二叉树 BT/求二叉树BT的结点数量把二叉树BT的左右子树进行交换求二叉树BT的高度说明：二叉树的基本操作可包括：(1) void Clear(BTreeNode *BT)(2) void MakeTree(BTreeNode *BT)(3) void BreakTree(BTreeNode *BT)(4) void PreOrder (BTreeNode *BT)(5) void InOrder(BTreeNode *BT)(6)

4、void PostOrder(BTreeNode *BT)(7) void FloorOrder(BTreeNode *BT)(8) int Size(BTreeNode *BT)(9) void Excha nge(BTreeNode *BT)(10 ) int GetHeight(BTreeNode *BT)(一)概要设计1.流程图及设计思想2. 本程序包含的模块(1) 主程序模块Void main ()初始化；构造一棵二叉树；各种遍历二叉树；对二叉树进行各种常见运算； 删除二叉树；(2) 二叉树模块一一实现二叉树的抽象数据类型和基本操作(3) 队列模块一一实现队列的抽象数据类(4 )二叉

5、树运算模块一一求二叉树的结点，叶子数目(二)详细设计一.先序遍历：A 自然语言描述：1. 判断根节点会否为空，如果为空，返回2. 如果根节点不为空3先输出根节点，再递归调用自身依次输出左孩子和右孩子 B 代码详细分析template void Bin aryTree:PreOrder(void (*Visit)(T & x)PreOrder(Visit,root);templatevoid Bin aryTree:PreOrder(void (*Visit)(T & x),BTNode* t) if(t)Visit(t-eleme nt); PreOrder(Visit,t-IChild)；P

6、reOrder(Visit,t-rChild);二.中序遍历：A 自然语言描述：1. 判断根节点是否为空，如果为空，返回2. 如果根节点不为空3. 递归调用自身输出左孩子，再输出根结点，递归调用输出右孩子 B 代码详细分析：template void Bin aryTree:l nOrder(void (*Visit)(T & x)In Order(Visit,root);templatevoid Bin aryTree:I nOrder(void (*Visit)(T & x),BTNode* t) if(t)InO rder(Visit,t-IChild);Visit(t-eleme nt

7、);InO rder(Visit,t-rChild);三后序遍历：A 自然语言描述：1. 判断根节点是否为空，如果为空，返回2. 如果根节点不为空3. 递归调用自身输出左孩子和右孩子，再输出根结点 B 代码详细分析：template void Bin aryTree:PostOrder(void (*Visit)(T & x)PostOrder(Visit,root);template void Bin aryTree:PostOrder(void (*Visit)(T & x),BTNode* t) if(t)PostOrder(Visit,t-lChild); PostOrder(Visi

8、t,t-rChild);Visit(t-eleme nt);四层次遍历二叉树：A 自然语言描述：1定义头指针和尾指针和空指针p2. 根节点是否为空，如果是，结束3. 如果不是，根节点入队4. 取队首元素，输出队首元素5. 将队首的非空左右结点入队列，删除队首元素6. 循环下去，直到队列为空 B 代码详细分析：template void Bin aryTree:FloorOrder(void (*Visit)(T &x)FloorOrder(Visit,root);template void Bin aryTree:;FloorOrder(void(*Visit)(Visit*x),BTNode

9、*t) SeqQueueBTNode*se(100);se.E nQueue(t); BTNode*temp;while(!se.lsEmpty()se.Fro nt(temp); Visit(temp);se.DeQueue();if(temp-lchild)se.E nQueue(temp-lchild); if(temp-child)se.E nQueue(temp-rchild);五. 求二叉树的结点数：A.自然语言描述：1判断根节点是否为空，如果为空，返回02:如果根节点不为空3:递归调用求二叉树的结点数的函数，参数改为根节点的左孩子4:递归调用求二叉树的结点数的函数，参数改为根节点

10、的右孩子5:返回根节点的左右字数的结点数之和B 代码详细分析：template int Bin aryTree:Size()return Size(root);template int Bin aryTree:Size(BTNode* t)if(!t) return 0;elsereturn Size(t-IChild)+Size(t-rChild)+1;六. 二叉树的左右交换：A 自然语言描述：1. 判断根节点是否为空，如果为空，返回2. 如果不为空，再判断该节点左右孩子是否同时为空,3. 如果是，返回4. 如果不为空，交换左右孩子5. 返回循环，遍历左右子树 B 代码详细分析：templa

11、te void Bin aryTree:Excha nge()Excha nge(root);template void Bin aryTree:Excha nge(BTNode* t) if(!t)return;BTNode* temp; temp=t-lChild;t-IChild=t-rChild; t-rChild=temp;Excha nge(t-IChild);Excha nge(t-rChild);七. 求二叉树的深度：A 自然语言描述：1判断根节点是否为空，如果根节点为空，返回02:如果根节点不为空但是根节点的左右孩子同时为空，返回13:如果以上两个条件都不成立4:递归调用求二

12、叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为15:递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为06:返回4与5步中得出深度较大的那个数作为二叉树的深度数B .代码详细分析：template int Bin aryTree:GetHeight(BTNode* t)int templ;int tempr;if(!t)return 0;templ=GetHeight(t-IChild);tempr=GetHeight(t-rChild);if(templ+tempr+)return templ;elsereturn tempr;测试结果可)C：UqxueerX

13、DeskiopDSA-Exp-2-only_BTeeT前序遍历B D C E F中序遍历D E E C F后序遍历D E F C B姑点戮量疝换后的前庇遍历B C F E D树的髙度日二叉树基本运算源代码：BTree.h:#in elude using n amespace std;template struct BTNodeT eleme nt;BTNode *IChild,*rChild;BTNode()IChild=rChild=NULL;BTNode(co nst T& x)eleme nt=x;IChild=rChild=NULL;BTNode(c onst T& x,BTNode

14、*l,BTNode *r)eleme nt=x;lChild=l;rChild=r;template class Bin aryTreepublic:Bin aryTree()root=NULL;Bin aryTree()Clear(root);bool lsEmpty()c on st;void Clear();bool Root(T &x)co nst;int Size();void MakeTree(c onst T &e,B in aryTree& left,B in aryTree& right);void BreakTree(T & e,B in aryTree& left,B i

15、n aryTree& right);void LevelOrder(void (*Visit(T& x);void PreOrder(void (*Visit)(T & x);void In Order(void (*Visit)(T & x);void PostOrder(void (*Visit)(T & x);void Excha nge();int GetHeight();protected:BTNode* root;private:void Clear(BTNode* t);int Size(BTNode* t);void LevelOrder(void (*Visit)(T & x

16、),BTNode* t);void PreOrder(void (*Visit)(T & x),BTNode* t);void In Order(void (*Visit)(T & x),BTNode* t);void PostOrder(void (*Visit)(T & x),BTNode* t);void Excha nge(BTNode* t);int GetHeight(BTNode* t);template void Bin aryTree:Clear(BTNode* t)if(!t)return;Clear(t-lChild);Clear(t-rChild);delete t;t

17、emplate bool Bin aryTree:Root(T &x)c onstif(root)x=root-eleme nt;return true;elsereturn false;template void Bin aryTree:MakeTree(c onst T &e,B in aryTree& left,B in aryTree& right) if(root|&left=&right)return;root=new BTNode(e,left.root,right.root);left.root=right.root=NULL;template void Bin aryTree

18、:BreakTree(T &x,B in aryTree& left,B in aryTree& right) if(!root| &left=&right|left.root|right.root)return;x=root-eleme nt;left.root=root-lChild;right.root=root-rChild;delete root; root=NULL;template void Visit(T & x)coutx;template void Bin aryTree:PreOrder(void (*Visit)(T & x)PreOrder(Visit,root);t

19、emplatevoid Bin aryTree:PreOrder(void (*Visit)(T & x),BTNode* t)if(t)Visit(t-eleme nt);PreOrder(Visit,t-lChild);PreOrder(Visit,t-rChild);template void Bin aryTree:I nOrder(void (*Visit)(T & x)In Order(Visit,root);emplatevoid Bin aryTree:I nOrder(void (*Visit)(T & x),BTNode* t)if(t)InO rder(Visit,t-I

20、Child);Visit(t-eleme nt);InO rder(Visit,t-rChiId);template void Bin aryTree:PostOrder(void (*Visit)(T & x)PostOrder(Visit,root);template void Bin aryTree:PostOrder(void (*Visit)(T & x),BTNode* t) if(t)PostOrder(Visit,t-lChild);PostOrder(Visit,t-rChild);Visit(t-eleme nt);template void Bin aryTree:Flo

21、orOrder(void (*Visit)(T &x)FloorOrder(Visit,root);template void Bin aryTree:FloorOrder(void(*Visit)(T & x),BTNode*t) SeqQueueBTNode*se(100);se.E nQueue(t);BTNode *tmp;while(!se.lsEmpty()se.Fro nt(tmp);Visit(tmp);se.DeQueue();if(tmp-lChild)se.E nQueue(tmp-rChild);template int Bin aryTree:Size()return

22、 Size(root);template int Bin aryTree:Size(BTNode* t)if(!t)return 0;elsereturn Size(t-IChild)+Size(t-rChild)+1;template void Bin aryTree:Excha nge()Excha nge(root);template void Bin aryTree:Excha nge(BTNode* t)if(!t)return;BTNode* temp; temp=t-lChild; t-IChild=t-rChild; t-rChild=temp; Excha nge(t-ICh

23、ild); Excha nge(t-rChild);template int Bin aryTree:GetHeight()return GetHeight(root);emplate int Bin aryTree:GetHeight(BTNode* t)int tempi;int tempr;if(!t)return 0;templ=GetHeight(t-IChild); tempr=GetHeight(t-rChild); if(templ+tempr+) return templ;elsereturn tempr;Test.Cpp：#i nclude BTree.hint mai n

24、()Bin aryTree a,b,x,y,z;y.MakeTree(E,a,b);z.MakeTree(F,a,b);x. MakeTree(C,y,z);y.MakeTree(D,a,b);z.MakeTree(B,y,x);cout前序遍历endl;z.PreOrder(Visit); coute ndl;cout中序遍历endl;z.I nO rder(Visit); coute ndl;cout后序遍历endl;z.P ostOrder(Visit); coute ndl; cout层次遍历endl; 乙 LevelOrder(Visit); coute ndl;cout结点数量:;

25、coutz.Size()e ndl;z.Excha nge();e ndl;cout左右交换后的前序遍历z. PreOrder(Visit); cout树的高度:; coutz.GetHeight()e ndl; coute ndl;return 0;实验题二：哈夫曼编码和译码系统(1 )所设计的系统重复显示以下菜单项：B建树：读入字符集和各字符频度，建立哈夫曼树。T遍历：先序和中序遍历二叉树。E生成编码：根据已建成的哈夫曼树，产生各字符的哈夫曼编码。C编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件text

26、file.txt 和codefile.txt 中。D译码：读入 codefile.txt ，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件 result.txt 中。P打印：屏幕显示文件textfile.txt 、codefile.txt 和 result.txt 。X退出。源代码#in elude #in elude #in clude #in clude #in clude using n amespace std;int *weightArray;stri ng s;stri ng *codeArray;template struct BTNode T eleme nt;BTNo

27、de *IChild, *rChild;BTNode() lChild = rChild = NULL;BTNode(co nst T& x) eleme nt = x;lChild = rChild = NULL;BTNode(c onst T& x, BTNode* l, BTNode* r) eleme nt = x;lChild = l; rChild = r;template class Bin aryTree public:Bin aryTree() root = NULL;Bin aryTree() bool isEmpty() const return root = NULL;

28、void clear() postClear(root);bool retRoot(T & x) con st;void makeTree(c onst& x, Bi naryTree& left, Bin aryTree& right); void breakTree(T & x, Bin aryTree& left. Bin aryTree& right); void preOrder() preOrder(root);void in Order() in Order(root);void postOrder() postOrder(root);BTNode* copy(BTNode *t

29、);int size() retur n size(root);void cha nge() cha nge(root);void breathFirst() breathFirst(root);int height() return height(root);void leaf() prePri nt(root);protected:BTNode* root;private:void clear(BTNode* t);void cha nge(BTNode* t);void postClear(BTNode* t);void prePri nt(BTNode* t);int size(BTN

30、ode* t);int height(BTNode* t);void preOrder(BTNode* t);void in Order(BTNode* t);void postOrder(BTNode* t);void breathFirst(BTNode* t);void visit(T & x) cout x ;template bool Bin aryTree:retRoot(T& x) const if (root) x = root - eleme nt;return true;else return false;template void Bin aryTree:makeTree

31、(c onst& x, Bi naryTree& left, Bin aryTree& right) if (root | & left = & right) return;root = new BTNode(x, left.root, right.root); left.root = right.root = NULL;template void Bin aryTree:breakTree(T & x, Bin aryTree& left. Bin aryTree& right) if (!root | &left = &right | left.root | right.root) ret

32、urn;x = root - eleme nt;left.root = root - lChild;right.root = root - rChild;delete root;root = NULL;template void Bin aryTree:preOrder(BTNode* t) if (t) visit(t - eleme nt); preOrder(t - lChild); preOrder(t - rChild);template void Bin aryTree:i nO rder(BTNode* t) if (t) in Order(t - lChild); visit(

33、t - eleme nt);in Order(t - rChild);template void Bin aryTree:postOrder(BTNode* t) if (t) postOrder(t - lChild);postOrder(t - rChild); visit(t - eleme nt);template void Bin aryTree:clear(BTNode* t) delete t;t = NULL;template void Bin aryTree:postClear(BTNode* t) if (t) postClear(t - lChild);postClear

34、(t - rChild); delete t;template BTNode* Bin aryTree:copy(BTNode *t) if (!t) return NULL;BTNode* q = new BTNode(t -eleme nt); q - lChild = copy(t - lChild); q - rChild = copy(t - rChild);return q;template int Bin aryTree:size(BTNode* t) if (!t) return 0;else return size(t - lChild) + size(t - rChild)

35、; template void Bin aryTree:cha nge(BTNode* t) if (!t) return;BTNode *q = copy(t - rChild); clear(t - rChild); t - rChild = t - lChild;t - lChild = q;cha nge(t - lChild);cha nge(t - rChild);template void Bin aryTree:breathFirst(BTNode* t) if (!t) return; queueBTNode* q1; q1.push(t);BTNode *n ode;whi

36、le (!q1.empty() node = q1.fr on t(); visit( node - eleme nt); q1.pop();if (node - lChild) q1.push(node - lChild); if (node- rChild) q1.push(node - rChild);template int Bin aryTree:height(BTNode* t)if(t = NULL) retur n 0;elseint m = height( t - IChild );int n = height(t - rChild); return (m n) ? (m +

37、 1) : (n + 1);template void Bin aryTree:prePri nt(BTNode* t) if (t) if (t - lChild = NULL) & (t - rChild = NULL) visit(t - eleme nt);return;prePri nt(t - lChild);prePri nt(t - rChild);templateclass PrioQueue public:PrioQueue(i nt mSize=20);PrioQueue()delete q;bool lsEmpty() con stretur nn=0;bool IsF

38、ull() con stretur nn=maxSize;void Appe nd(c onst T &x);void Serve(T & x);private:void AdjustDow n (int r, int j);void AdjustUp (int j);T* q;int n, maxSize;template PrioQueue:PrioQueue(i nt mSize) maxSize=mSize;n=0;q=new TmaxSize;template void PrioQueue:AdjustUp (int j) int i=j;T temp=qi;while (i0 &

39、tempq(i-1)/2) qi=q(i-1)/2;i=(i-1)/2;qi=temp;template void PrioQueue:Appe nd(c onst T &x)if(lsFull() cout Overflow;return;qn+=x;AdjustUp( n-1);template void PrioQueue:Serve(T & x)if(IsEmpty() cout Un derflow; return;x=q0;q0=q-n;AdjustDow n (0, n-1);template void PrioQueue:AdjustDow n (int r, int j) i

40、n t child = 2 * r + 1;T temp = qr; while (child = j) if (child qchild + 1) child+; if (temp = qchild) break;q(child - 1) / 2 = qchild;child = 2 * child + 1;q(child - 1) / 2 = temp;template class HfmTree: public Bin aryTreepublic:operator T()c onst retur n weight;T getW()return weight;void putW(co ns

41、t T& x) weight=x;void SetNull()root=NULL;void code(stri ng& c) code(root, c);void decode(stri ng s);private:T weight;void code(BTNode* t, string& c);template void HfmTree:decode(stri ng decodeStri ng) if (codeArray = NULL) cout 尚未编码！ endl;return;BTNode* searchNode = root;for (int i = 0; i decodeStri

42、 ng.len gth(); i+) if (decodeStringi != O & decodeStringi != 1) cout 所给码格式不正确！ lChild = NULL & searchNode - rChild = NULL) T value = searchNode - eleme nt;for (i nt j = 0; j sen gth(); j+) if (value = weightArrayj) cout IChild;if (decodeStri ngi = 1) searchNode = searchNode - rChild;if (searchNode -

43、 lChild = NULL & searchNode - rChild = NULL) T value = searchNode - eleme nt; for (i nt j = 0; j sen gth(); j+) if (value = weightArrayj) cout sj;break;cout en dl;template void HfmTree:code(BTNode* t, string& c) if (t) if (t - lChild = NULL & t - rChild = NULL) for (i nt i = 0; i eleme nt = weightAr

44、rayi) codeArrayi = c;/cout NO i ;哈弗曼编码是”cout 字符 si 的权重是 weightArrayi codeArrayi lChild != NULL) string ls;ls.assig n( c);ls.appe nd(0); code(t - lChild, ls);if (t - rChild != NULL) stri ng rs;rs.assig n(c);rs.appe nd(1);code(t - rChild, rs);template HfmTree CreateHfmTree (T *w,i nt n) PrioQueue HfmT

45、ree pq( n); /空优先权队列HfmTree x,y,z;/ 空哈夫曼树for (int i=0;in;i+)/构造n棵只有一个结点的哈夫曼树z. makeTree(wi,x,y);z. putW(wi);pq.Appe nd(z);z. SetNull();for (i=1;i n ;i+)pq.Serve(x); 取出最小权值的哈夫曼树对象xpq.Serve(y);取出最小权值的哈夫曼树对象yz.makeTree(x.getW()+y.getW(),x,y);z. putW(x.getW()+y.getW();pq.Appe nd(z);z. SetNull();pq.Serve(z);return 乙void in put(HfmTree& p) cout s;weightArray = new in ts.le ngth();codeArray = new stri ngs.le ngth();for (int i = 0; i s.len gth(); i+) cout 请输入第 (i + 1) 个字符的权值： weightArrayi;p = CreateHfmTree(weightArray, s.len gth();p.postOrder();void createCode(HfmTree& p) if (c