《二叉树基本操作以与哈夫曼编码译码系统》由会员分享，可在线阅读，更多相关《二叉树基本操作以与哈夫曼编码译码系统（28页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告（2015 / 2016 学年 第 二 学期）课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间 2016年4月14日指导单位南京邮电大学指导教师骆健学生姓名吴佳瑶班级学号B14111708学院(系) 管理学院专 业信息管理与信息系统二叉树的基本运算：1、 问题描述1. 设计递归算法，实现二叉树的运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树，交换一棵二叉树的左右子树2. 设计算法，自上而下，自左向右即按层次遍历一棵二叉树3. 设计main函数，测试上述每个运算二、系统分析和概要设计首先用maketree构造一棵二叉树，然后遍
2、历二叉树，然后交换每个结点的左右子树，接着算出输得高度和叶子节点，最后删除。三、详细设计T1. 类和类的层次结构BinaryTree#BTNode * root-static int number+BinaryTree()+BinaryTree()+void Copy(BinaryTree &r) const+bool IsEmpty()const+void Clear()+void Exchange()+bool Root(T& x)const;+int GetHeight()+voidMakeTree(const T& x,BinaryTree& left,BinaryTree& righ
3、t)+void BreakTree(T&x,BinaryTree& left,BinaryTree& right)+void PreOrder(void (*Visit)(T &x)+void LevelOrder(void (*Visit)(T& x)+int Size()+BinaryTree(BinaryTree &t)+BTNode* Copy(BTNode* t)-void Clear(BTNode* &t)-void Exchange(BTNode* t)-int GetHeight(BTNode* t)-int Size(BTNode* t)-void PreOrder(void
4、 (*Visit)(T &x),BTNode* t)-void LevelOrder(void (*Visit)(T& x),BTNode* t) 2. 核心算法建立二叉树的void MakeTree(const T& x,BinaryTree& left,BinaryTree& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树等都是用递归的方法实现。四、 程序代码建立二叉树树用maketree构造一棵二叉树递归遍历二叉树根据二叉树的定义和遍历算法的定义，和很容易实现层次遍历二叉树节点数量用队列实现，将
5、跟结点入队。一：出队并输出节点的值。二： 若存在左右孩子，则将其入队。循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和跟结点左右交换本质就是交换每个结点的左右子树树的高度左右子树高度之和进行比较，谁大谁就是树的高度删除二叉树先删除左子树，再删除右子树，最后删除根节点，再释放结点空间一先序遍历：template void BinaryTree:PreOrder(void (*Visit)(T& x)PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void (*Visit)(T& x),BTNode* t)if(t)
6、Visit(t-element);PreOrder(Visit,t-lChild)；PreOrder(Visit,t-rChild);二中序遍历：template void BinaryTree:InOrder(void (*Visit)(T& x)InOrder(Visit,root);templatevoid BinaryTree:InOrder(void (*Visit)(T& x),BTNode* t)if(t)InOrder(Visit,t-lChild);Visit(t-element);InOrder(Visit,t-rChild);三后序遍历：template void Bin
7、aryTree: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(Visit,root);template void
8、BinaryTree:;FloorOrder(void(*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); 五求二叉树的结点数：template int BinaryTree:Size()return Si
9、ze(root);template int BinaryTree:Size(BTNode* t)if(!t)return 0;elsereturn 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)
10、;Exchange(t-rChild);七求二叉树的深度：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+)return templ;elsereturn tempr;五、测试用例和运行结果测试用例结果如下图所示。哈夫曼编码和译码系统：一、问题描述1.所设计的系统重复显示以下菜单B-建树：读入字符集和各字符频度T-遍历：先序和中序遍历二叉树E-生成代码：
11、根据已经简称的哈夫曼数生成代码，产生各字符的哈夫曼树C-编码：输入由字符集中字符组成的任意字符串，利用已经生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中D-译码：读入codefile.txt，利用已经建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txtP-打印：屏幕显示文件textfile.txt 、codefile.txt、 resultfile.txtX-退出二、系统分析和概要设计主要包括实现主菜单以及菜单里每个函数的功能（创建函数实现接收字符，接收权值，构建哈夫曼树并保存文件，编码
12、函数实现对用户输入的秘文进行哈夫曼编码，即对每个字符翻译出其密文代码并保存文件，译码函数实现译码即输出密文的源码）。三、详细设计T1. 类和类的层次结构BinaryTree#BTNode * root-static int number+BinaryTree()+BinaryTree()+bool IsEmpty()const+void Clear()+bool Root(T& x)const;+voidMakeTree(const T& x,BinaryTree& left,BinaryTree& right)+void BreakTree(T&x,BinaryTree& left,BinaryTree& right)+void PreOrder()+void inOrder() +void leaf()+void visit(T& x) +-void postOrder() -void Clear(BTNode* &t)-void PreOrder(,BTNode* t)-void prePrint(BTNode* t)-void inOrder(BTNode* t)-void postOrder(BTNode* t)PrioQueue-T* q;-int n,maxSize;+PrioQueue(int mSize=20
