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

1、实验报告2二叉树及哈夫曼编码(此文档为word格式，下载后您可任意编辑修改！)实 验 报 告（ 2013 2014 学年 第 二 学期）课程名称数据结构A 实验名称实验二 二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2014年4月8日指导单位计算机学院计算机软件教学中心指导教师朱立华学生姓名高怡馨班级学号B学院(系)教育科学与技术学院专 业教育技术学实 验 报 告实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现指导教师朱立华实验类型 设计实验学时 2实验时间2014.4.8一、 实验目的和要求（1）掌握二叉链表上实现二叉树基本去处的方法。（2）学会设计基于遍历的求解二叉树应用

2、问题的递归算法。（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。二、实验环境(实验设备) 硬件: 微型计算机 软件: Microsoft Visual C+6.0三、实验原理及内容 实验题一：在二叉链表上实现二叉树运算（1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。（3）设计main函数，测试上述每个运算。内容：1、建立头文件BTree.H，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一

3、个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。实 验 报 告说明：二叉树的基本操作可包括：(1)void Clear(BTreeNode *BT) 清除一棵二叉树，并释放结点空间（2）void MakeTree(BTreeNode *BT) 构造一棵二叉树BT（3）void BreakTree(BTreeNode *BT) 撤销一棵二叉树BT（4）void PreOrder (BTreeNode *BT) 先序遍历二叉树BT(5）void InOrder(BTreeNode *BT) 中序遍历二叉树BT（6）void PostOrder

4、(BTreeNode *BT) 后序遍历二叉树BT (7) void FloorOrder(BTreeNode *BT) 层次遍历二叉树BT （8）int Size(BTreeNode *BT) 求二叉树BT的结点数量（9）void Exchange(BTreeNode *BT) 把二叉树BT的左右子树进行交换（10）int GetHeight(BTreeNode *BT) 求二叉树BT的高度（一）概要设计1.流程图及设计思想实 验 报 告2.本程序包含的模块（1）主程序模块 Void main（） 初始化； 构造一棵二叉树； 各种遍历二叉树； 对二叉树进行各种常见运算； 删除二叉树； (2)

5、 二叉树模块实现二叉树的抽象数据类型和基本操作(3) 队列模块实现队列的抽象数据类（4）二叉树运算模块求二叉树的结点，叶子数目（二）详细设计 一先序遍历：A自然语言描述:1.判断根节点会否为空，如果为空，返回2.如果根节点不为空3.先输出根节点，再递归调用自身依次输出左孩子和右孩子B代码详细分析template void BinaryTree:PreOrder(void (*Visit)(T& x) PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void (*Visit)(T& x),BTNode* t) if(t) Visit(t

6、-element); PreOrder(Visit,t-lChild)； PreOrder(Visit,t-rChild); 实 验 报 告二中序遍历：A自然语言描述:1.判断根节点是否为空，如果为空，返回2.如果根节点不为空3. 递归调用自身输出左孩子，再输出根结点，递归调用输出右孩子B代码详细分析：template void BinaryTree:InOrder(void (*Visit)(T& x) InOrder(Visit,root);templatevoid BinaryTree:InOrder(void (*Visit)(T& x),BTNode* t) if(t) InOrde

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

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

9、oid(*Visit)(Visit*x),BTNode*t) SeqQueueBTNode*se(100); se.EnQueue(t); BTNode*temp; while(!se.IsEmpty() se.Front(temp); Visit(temp); se.DeQueue(); if(temp-lchild) se.EnQueue(temp-lchild); if(temp-child) se.EnQueue(temp-rchild); 五求二叉树的结点数：A. 自然语言描述：1：判断根节点是否为空，如果为空，返回02：如果根节点不为空 3：递归调用求二叉树的结点数的函数，参数改为

10、根节点的左孩子 4：递归调用求二叉树的结点数的函数，参数改为根节点的右孩子实 验 报 告5：返回根节点的左右字数的结点数之和B代码详细分析:template int BinaryTree:Size() return Size(root);template int BinaryTree:Size(BTNode* t) if(!t) return 0; else return Size(t-lChild)+Size(t-rChild)+1;六二叉树的左右交换:A自然语言描述：1.判断根节点是否为空，如果为空，返回2.如果不为空，再判断该节点左右孩子是否同时为空，3.如果是，返回4.如果不为空，交换

11、左右孩子5.返回循环，遍历左右子树B代码详细分析：template void BinaryTree:Exchange() Exchange(root);template void BinaryTree:Exchange(BTNode* t) if(!t) return; BTNode* temp; temp=t-lChild; t-lChild=t-rChild; t-rChild=temp; Exchange(t-lChild); Exchange(t-rChild);实 验 报 告七求二叉树的深度：A自然语言描述：1：判断根节点是否为空，如果根节点为空，返回0 2：如果根节点不为空但是根节

12、点的左右孩子同时为空，返回1 3：如果以上两个条件都不成立4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为15：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0 6：返回4与5步中得出深度较大的那个数作为二叉树的深度数B 代码详细分析:template int BinaryTree:GetHeight(BTNode* t) int templ; int tempr; if(!t) return 0; templ=GetHeight(t-lChild); tempr=GetHeight(t-rChild); if(templ+tempr+) re

13、turn templ; else return tempr;测试结果实 验 报 告二叉树基本运算源代码：BTree.using namespace std;template struct BTNode T element; BTNode *lChild,*rChild; BTNode() lChild=rChild=NULL; BTNode(const T& x) element=x; lChild=rChild=NULL; BTNode(const T& x,BTNode *l,BTNode *r) element=x; lChild=l; rChild=r; ;template class

14、 BinaryTreepublic: BinaryTree()root=NULL; BinaryTree()Clear(root); bool IsEmpty()const; void Clear(); bool Root(T &x)const; int Size(); void MakeTree(const T &e,BinaryTree& left,BinaryTree& right); void BreakTree(T &e,BinaryTree& left,BinaryTree& right); void LevelOrder(void (*Visit(T& x); void PreO

15、rder(void (*Visit)(T& x); void InOrder(void (*Visit)(T& x); void PostOrder(void (*Visit)(T& x);实 验 报 告void Exchange(); int GetHeight();protected: BTNode* root;private: void Clear(BTNode* t); int Size(BTNode* t); void LevelOrder(void (*Visit)(T& x),BTNode* t); void PreOrder(void (*Visit)(T& x),BTNode

16、* t); void InOrder(void (*Visit)(T& x),BTNode* t); void PostOrder(void (*Visit)(T& x),BTNode* t); void Exchange(BTNode* t); int GetHeight(BTNode* t);template void BinaryTree:Clear(BTNode* t) if(!t) return; Clear(t-lChild); Clear(t-rChild); delete t;template bool BinaryTree:Root(T &x)const if(root) x

17、=root-element; return true; else return false;template void BinaryTree:MakeTree(const T &e,BinaryTree& left,BinaryTree& right) if(root|&left=&right) return; root=new BTNode(e,left.root,right.root); 实 验 报 告left.root=right.root=NULL;template void BinaryTree:BreakTree(T &x,BinaryTree& left,BinaryTree&

18、right) if(!root|&left=&right|left.root|right.root) return; x=root-element; left.root=root-lChild; right.root=root-rChild; delete root; root=NULL;template void Visit(T& x) coutx ;template void BinaryTree:PreOrder(void (*Visit)(T& x) PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void (*Visit)(

19、T& x),BTNode* t) if(t) Visit(t-element); PreOrder(Visit,t-lChild); PreOrder(Visit,t-rChild); template void BinaryTree:InOrder(void (*Visit)(T& x) InOrder(Visit,root);emplatevoid BinaryTree:InOrder(void (*Visit)(T& x),BTNode* t)实 验 报 告 if(t) InOrder(Visit,t-lChild); Visit(t-element); InOrder(Visit,t-

20、rChild); template void BinaryTree:PostOrder(void (*Visit)(T& x) PostOrder(Visit,root);template void BinaryTree:PostOrder(void (*Visit)(T& x),BTNode* t) if(t) PostOrder(Visit,t-lChild); PostOrder(Visit,t-rChild); Visit(t-element); template void BinaryTree:FloorOrder(void (*Visit)(T &x) FloorOrder(Vis

21、it,root);template void BinaryTree:FloorOrder(void(*Visit)(T& x),BTNode*t) SeqQueueBTNode*se(100); se.EnQueue(t); BTNode *tmp; while(!se.IsEmpty() se.Front(tmp); Visit(tmp); se.DeQueue(); if(tmp-lChild)实 验 报 告 se.EnQueue(tmp-rChild); template int BinaryTree:Size() return Size(root);template int Binar

22、yTree:Size(BTNode* t) if(!t) return 0; else return Size(t-lChild)+Size(t-rChild)+1;template void BinaryTree:Exchange() Exchange(root);template void BinaryTree:Exchange(BTNode* t) if(!t) return;BTNode* temp; temp=t-lChild; t-lChild=t-rChild; t-rChild=temp; Exchange(t-lChild); Exchange(t-rChild);templ

23、ate int BinaryTree:GetHeight() return GetHeight(root);emplate int BinaryTree:GetHeight(BTNode* t)实 验 报 告 int templ; int tempr; if(!t) return 0; templ=GetHeight(t-lChild); tempr=GetHeight(t-rChild); if(templ+tempr+) return templ; else return tempr;Test.Cpp：#include BTree.() BinaryTree a,b,x,y,z; y.Ma

24、keTree(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); coutendl; cout中序遍历endl; z.InOrder(Visit); coutendl; cout后序遍历endl;z.PostOrder(Visit); coutendl; cout层次遍历endl; z.LevelOrder(Visit); coutendl;cout结点数量:; coutz.Size()endl; z.Exchan

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

26、e.txt中。D译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt中。P打印：屏幕显示文件textfile.txt、codefile.txt和result.txt。X退出。源代码#include #include #include #include #include using namespace std;int *weightArray;string s;string *codeArray;template struct BTNode T element; BTNode *lChild, *rChild; BTNode() lChild = rChild = NULL; BTNode(const T& x) element = x; lChild = rChild = NULL;