实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计

数据结构实验报告《五、最优二叉树应用之哈夫曼编译码》数据结构实验报告- - - -最优二叉树运用--哈夫曼编/译码专业班级:电信0903时间:2011年11月27日数据结构实验报告----最优二叉树运用--哈夫曼编/译码【问题描述】例3(实验二方案3):设字符集为26个英文字母，其出现频度如下表所示。

先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。

注:若圆满实现了此方案，平时成绩将以满分计。

字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【基本要求】哈夫曼编/译码的功能是:(1) I:初始化(Initialization)。

从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。

(2) E:编码(Encoding)。

利用已建好的赫夫曼树(如不在内存，则从文件hfmTree中读入)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

(3) D:译码(Decoding)。

利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。

【运用拓展】(1) 编码结果以文本方式存储在文件Codefile中，(2) 仿真友好界面，用户界面可以设计为“菜单”方式，通过人机交互方式使用本程序，从而更加方便友好;【设计思路分析】1、将哈夫曼树节点的数据类型定义为: ?typedef struct{ //赫夫曼树的结构体char ch;int weight; //权值int parent,lchild,rchild;}htnode,*hfmtree;2、功能函数模块划分 ?1、void HfmCoding(HfmTree &HT,HfmCode &HC,int n)初始化哈夫曼树，按照哈夫曼规则建立2叉树。

实验报告
（ 2016 / 2017 学年第一学期）
课程名称数据结构A
实验名称二叉树的基本操作
及哈夫曼编码译码系统的实现
实验时间2017 年 5 月 1 日指导单位计算机学院计算机科学与技术系
指导教师邹志强
学生姓名吴爱天班级学号B15040916 学院(系) 计算机学院专业信息安全
实验报告
之后三步输出，对应的是三种遍历方式，应该输出的测试结果是：
先序:68 69 72 70 74 71 67 75 65 66
中序:72 69 74 70 71 75 67 68 65 66
后序:72 74 75 67 71 70 69 66 65 68
实验结果符合预期。

对于哈夫曼建树操作我自己又按照自己的想法重写了，里面也去学习了C++的字典类MAP，这个类非常好用，可以简单粗暴地提供一些方法和迭代器，让你将关键字和值绑定，这样我每新加入一个字母的数据块，我就可以记录下这对组合，不用之后搜索和解码的时
之后进行编码，其实也是一个搜索的过程，主要是调用了一个
测试：。

实验报告
（2013/ 2014 学年第二学期）
课程名称数据结构A
实验名称实验二二叉树的基本操作及哈夫曼编码译码系统的实现
实验时间2014 年 4 月8 日
指导单位计算机学院计算机软件教学中心
指导教师朱立华
学生姓名高怡馨班级学号B12140113
专业教育技术学
学院(系) 教育科学与技
术学院
实验报告
七．求二叉树的深度：
A．自然语言描述：
1：判断根节点是否为空，如果根节点为空，返回0
2：如果根节点不为空但是根节点的左右孩子同时为空，返回1
3：如果以上两个条件都不成立
4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为1 5：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0 6：返回4与5步中得出深度较大的那个数作为二叉树的深度数
B．代码详细分析:
template <class T>
int BinaryTree<T>::GetHeight(BTNode<T>* 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;
}
测试结果。

树和哈夫曼树实验报告一．实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二．实验环境Microsoft visual c++三．实验问题描述1. 问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。

基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。

在遍历算法中要求至少有一种遍历采用非递归方法。

测试数据：ABCØØDEØGØØFØØØ（其中Ø表示空格字符）输出结果为：先序：ABCDEGF先序：CBEGDFA先序：CGEFDBA2. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站写一个哈夫曼码的编/译码系统。

基本要求：(至少完成功能1-2）一个完整的系统应具有以下功能：I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

基本要求：E：编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

D：译码（Decoding )。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

哈夫曼编码解码实验1.实验要求掌握二叉树的相关概念掌握构造哈夫曼树，进行哈夫曼编码。

对编码内容通过哈夫曼树进行解码。

2.实验内容通过二叉树构造哈夫曼树，并用哈夫曼树对读取的txt文件进行哈夫曼编码。

编码完成后通过哈夫曼树进行解码。

#include<>#include<>#define MAX 100arent=ht[i].lch=ht[i].rch=0;}j=0;for(i=1;i<=n;i++){/*getchar();printf("输入第%d个叶子节点的值：",i);scanf("%c",&ht[i].data);printf("输入该节点的权值：");scanf("%d",&ht[i].weight);*/for(;j<127;j++){if(Coun[j]!=0){ht[i].data=j;ata);ht[i].weight=Coun[j];eight);break;}}j++;}printf("\n");for(i=1;i<=n;i++){printf("%c",ht[i].data);}printf("\n");for(i=n+1;i<=2*n-1;i++){arent==0)eight<min1){min2=min1;right=left;min1=ht[k].weight;left=k;else if (ht[k].weight<min2){min2=ht[k].weight;right=k;}}ht[left].parent=i;ht[right].parent=i;ht[i].weight=ht[left].weight+ht[right].weight;ht[i].lch=left;ht[i].rch =right;}}arent;while(f!=0){if(ht[f].lch==c)[]='0';else[]='1';;f=ht[f].parent;}hcd[i]=cd;}printf("输出哈夫曼编码：\n");for(i=1;i<=n;i++){printf("%c:",ht[i].data);for(k=hcd[i].start+1;k<=n;k++)printf("%c",hcd[i].bit[k]);printf("\n");}}ata){for(k=hcd[j].start+1;k<=n;k++){s1[h]=hcd[j].bit[k];h++;}break;}}i++;}ch;if(ht[f].lch==0&&ht[f].rch==0){C=ht[f].data;printf("%c",C);f=2*n-1;}}else if(s1[i]=='1'){f=ht[f].rch;if(ht[f].lch==0&&ht[f].rch==0){C=ht[f].data;printf("%c",C);f=2*n-1;}}}printf("\n"); }验总结通过本次实验，对二叉树的应用有了相应的了解，掌握了如何构造哈夫曼编码，如何对编码结果进行解码。

实验六二叉树构造和遍历一. 实验目的⑴掌握二叉树的逻辑结构；⑵掌握二叉树的二叉链表存储结构；⑶掌握基于二叉链表存储的二叉树的遍历操作的实现。

二. 实验环境Windows操作系统，Visual C++ 6.0编程环境。

三. 实验内容和步骤1．观察下面图6-1的二叉树，回答问题。

图6-1（1）写出前序、中序和后序遍历序列；前序：ABDECFG 中序：DBEAFGC 后序：DEBGFCA （2）分别写单支结点和叶子结点；单支结点：CF 叶子结点：DEG（3）以”#”补充所有结点的空分支；ABD##E##CF#G###（4）写出补充空分支后二叉树的前序遍历序列（扩展的前序遍历序列）；ABD##E##CF#G###2．建立工程Bitree，编写Biree.h，Biree.cpp和测试函数Bireemain.cpp,完成下列功能。

⑴建立一棵含有n个结点的二叉树，采用二叉链表存储；⑵前序（或中序、后序）遍历该二叉树。

四．编码头文件Bitree.h#include<iostream>using namespace std;template <class T>struct BiNode{T data;BiNode<T> *lchild, *rchild;};template <class T>class BiTree{public:BiTree(){root=Creat(root);} //有参构造函数，初始化一棵二叉树，其前序序列由键盘输入~BiTree(){Release(root);} //析构函数，释放二叉链表中各结点的存储空间void PreOrder(){PreOrder(root);} //前序遍历二叉树void InOrder(){InOrder(root);} //中序遍历二叉树void PostOrder(){PostOrder(root);} //后序遍历二叉树private:BiNode<T> *root; //指向根结点的头指针BiNode<T> *Creat(BiNode<T> *bt); //有参构造函数调用void Release(BiNode<T> *bt); //析构函数调用void PreOrder(BiNode<T> *bt);void InOrder(BiNode<T> *bt);void PostOrder(BiNode<T> *bt);};template <class T>BiNode<T> *BiTree<T>::Creat(BiNode<T> *bt){T ch;cin>>ch;if(ch=='#')bt=NULL; //建立一棵空树else {bt=new BiNode<T>; //生成一个结点bt->data=ch;bt->lchild=Creat(bt->lchild); //递归建立左子树bt->rchild=Creat(bt->rchild); //递归建立右子树}return bt;}template <class T>void BiTree<T>::Release(BiNode<T> *bt){if(bt!=NULL){Release(bt->lchild);Release(bt->rchild);delete bt;}}template <class T>void BiTree<T>::PreOrder(BiNode<T> *bt){if (bt==NULL) return; //递归调用的结束条件else {cout<<bt->data; //访问根结点的数据域PreOrder(bt->lchild); //前序递归遍历root的左子树PreOrder(bt->rchild); //前序递归遍历root的右子树}}template <class T>void BiTree<T>::InOrder(BiNode<T> *bt){if (bt==NULL) return; //递归调用的结束条件else {InOrder(bt->lchild);cout<<bt->data;InOrder(bt->rchild);}}template <class T>void BiTree<T>::PostOrder(BiNode<T> *bt){if (bt==NULL) return; //递归调用的结束条件else {PostOrder(bt->lchild);PostOrder(bt->rchild);cout<<bt->data;}}主函数main#include"Bitree.h"void main(){int c=1;while(c){cout<<"输入前序序列:";BiTree<char> tree;cout<<"前序遍历:";tree.PreOrder();cout<<endl;cout<<"中序遍历:";tree.InOrder();cout<<endl;cout<<"后序遍历:";tree.PostOrder();cout<<endl;cout<<"0.结束 1.重试"<<endl;cout<<"请选择:";cin>>c;}}五.调试结果（表5-1）（表5-1）二叉树验证实验调试结果六．实验小结本次实验主要是通过实验过程掌握二叉树的逻辑结构，掌握二叉树的二叉链表存储结构和掌握基于二叉链表存储的二叉树的遍历操作的实现。

第1篇一、实验目的1. 理解霍夫曼编码的基本原理和实现方法。

2. 掌握霍夫曼编码在数据压缩中的应用。

3. 通过实验，加深对数据压缩技术的理解。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 数据源：文本文件三、实验原理霍夫曼编码是一种常用的数据压缩算法，适用于无损数据压缩。

它通过使用变长编码表对数据进行编码，频率高的数据项使用短编码，频率低的数据项使用长编码。

霍夫曼编码的核心是构建一棵霍夫曼树，该树是一种最优二叉树，用于表示编码规则。

霍夫曼编码的步骤如下：1. 统计数据源中每个字符的出现频率。

2. 根据字符频率构建一棵最优二叉树，频率高的字符位于树的上层，频率低的字符位于树下层。

3. 根据最优二叉树生成编码规则，频率高的字符分配较短的编码，频率低的字符分配较长的编码。

4. 使用编码规则对数据进行编码，生成压缩后的数据。

5. 在解码过程中，根据编码规则恢复原始数据。

四、实验步骤1. 读取文本文件，统计每个字符的出现频率。

2. 根据字符频率构建最优二叉树。

3. 根据最优二叉树生成编码规则。

4. 使用编码规则对数据进行编码，生成压缩后的数据。

5. 将压缩后的数据写入文件。

6. 读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

7. 比较原始数据和恢复后的数据，验证压缩和解码的正确性。

五、实验结果与分析1. 实验数据实验中，我们使用了一个包含10000个字符的文本文件作为数据源。

在统计字符频率时，我们发现字符“e”的出现频率最高，为2621次，而字符“z”的出现频率最低，为4次。

2. 实验结果根据实验数据，我们构建了最优二叉树，并生成了编码规则。

使用编码规则对数据源进行编码，压缩后的数据长度为7800个字符。

将压缩后的数据写入文件，文件大小为78KB。

接下来，我们读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

比较原始数据和恢复后的数据，发现两者完全一致，验证了压缩和解码的正确性。

数据结构实验，哈夫曼编码译码系统展开全文1. 实验名称: 二叉树的基本操作及哈夫曼编码译码系统的实现2.实验目的：创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。

哈夫曼编码/译码系统。

3. 实验任务：能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。

4. 实验内容（1）在二叉链表上实现二叉树运算a) 设计递归算法，实现二叉树的基本运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子结点数，复制一棵二叉树，交换一棵二叉树的左右子树。

b) 设计算法，按自上到下，自左到右的次序，即按层次遍历一棵二叉树。

c) 设计main函数，测试上述每个运算。

d) 提示：队列结构可以辅助进行层次遍历，队列的元素类型是指向二叉树结点的指针类型。

（2）哈夫曼编码和译码系统a) 设计一个菜单可以循环显示B——建树：读入字符集和各字符频度，建立哈夫曼树。

T——遍历：先序和中序遍历二叉树。

E——生成编码：产生每个字符的哈夫曼编码。

C——编码：输入由字符集中字符组成的任意字符串，利用已经生成的哈夫曼编码进行编码，显示编码结果。

D——译码：利用已建成的哈夫曼树进行译码。

X——退出。

b) 提示：修改二叉树结点类BTNode，增加一个指向双亲的parent域，修改二叉树类的函数MakeTree设置该域的值；可以通过遍历哈夫曼树生成每个叶子结点的哈夫曼编码。

5. 概要设计1) 二叉树首先定义结点类BTNode包括对结点的访问，打印，交换结点左右元素等操作。

并将二叉树类BTree声明为友元类。

二叉树类中包含了建树，判断二叉树是否为空，求结点数，求高度，删除，交换左右子树，三种次序遍历及按层次遍历，清空二叉树等函数。

在主函数中调用实现这些功能。

类和类的层次设计主要算法：PreOrder：输出当前结点元素，左右孩子递归调用函数。

InOrder：左孩子递归调用函数，输出当前结点元素，右孩子递归调用。