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

实验报告（2014 / 2015 学年第一学期）课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间年月日指导单位指导教师学生姓名班级学号学院(系) 专业二叉树的基本运算：一、问题描述1.设计递归算法，实现二叉树的运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树，交换一棵二叉树的左右子树2.设计算法，自上而下，自左向右即按层次遍历一棵二叉树3.设计main函数，测试上述每个运算二、系统分析和概要设计首先用maketree构造一棵二叉树，然后遍历二叉树，然后交换每个结点的左右子树，接着算出输得高度和叶子节点，最后删除。

三、详细设计2. 核心算法建立二叉树的void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树等都是用递归的方法实现。

四、程序代码流程图#include<iostream.h>template<class T>struct BTNode{BTNode(){lChild=rChild=NULL;}BTNode(const T &x){element=x;lChild=rChild=NULL;}BTNode(const T &x,BTNode<T>* l,BTNode<T>* r){element=x;lChild=l;rChild=r;}T element;BTNode<T>* lChild,* rChild;};template<class T>class BinaryTree{public:BinaryTree(){root=NULL;}~BinaryTree(){Clear();}void Copy(BinaryTree<T> &r) const;bool IsEmpty()const{return root == NULL;}void Clear();void Exchange();bool Root(T& x)const;int GetHeight();void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);void PreOrder(void (*Visit)(T &x));void LevelOrder(void (*Visit)(T& x));int Size();BinaryTree<T>(BinaryTree<T> &t)root=Copy(t.root);}// void InOrder(void (*Visit)(T &x));// void PostOrder(void (*Visit)(T &x));BTNode<T>* Copy(BTNode<T>* t);protected:BTNode<T> * root;private:static int number;void Clear(BTNode<T>* &t);void Exchange(BTNode<T>* t);int GetHeight(BTNode<T>* t);int Size(BTNode<T>* t);void PreOrder(void (*Visit)(T &x),BTNode<T>* t);void LevelOrder(void (*Visit)(T& x),BTNode<T>* t); // void InOrder(void (*Visit)(T &x),BTNode<T>* t);// void PostOrder(void (*Visit)(T &x),BTNode<T>* t); };template <class T>bool BinaryTree<T>::Root(T &x)const{if(root){x=root->element;return true;}elsereturn false;}template <class T>void BinaryTree<T>::Clear(){Clear(root);}template <class T>void BinaryTree<T>::Clear(BTNode<T>* &t){if(t)Clear(t->lChild);Clear(t->rChild);delete t;t=NULL;}}template <class T>void BinaryTree<T>::MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right) {if(root||&left==&right)return;root=new BTNode <T>(x,left.root,right.root);left.root=right.root=NULL;}template <class T>void BinaryTree<T>::BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& 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 <class T>BTNode<T>* BinaryTree<T>::Copy(BTNode<T>* t){if(!t)return NULL;BTNode<T>*q=new BTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);return q;}template <class T>void Visit(T &x){cout<<x<<" ";}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x)){PreOrder(Visit,root);}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x),BTNode<T>* t) {if(t){Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}template <class T>void BinaryTree<T>::Exchange(){Exchange(root);}template <class T>void BinaryTree<T>::Exchange(BTNode<T>* t){if(!t)return;BTNode<T>* temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);}template <class T>int BinaryTree<T>::GetHeight(){return GetHeight(root);}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;elsereturn tempr;}template <class T>int BinaryTree<T>::number=0;template <class T>int BinaryTree<T>::Size(){Size(root);return number;}template <class T>int BinaryTree<T>::Size(BTNode<T>* t){if(t!=NULL){Size(t->lChild);if(t->lChild ==NULL&&t->rChild ==NULL)number++;Size(t->rChild);}return number;}template <class T>void BinaryTree<T>::LevelOrder(void (*Visit)(T& x)) {PreOrder(Visit,root);}void BinaryTree<T>::LevelOrder(void (*Visit)(T& x),BTNode<T>* t) {BTNode *quene[50],*p;int pre=1,rear=1;quene[++pre]=t;while(pre!=0){p=quene[++rear];cout<<p->element<<" ";if(p->lChild !=NULL)quene[++pre]=p->rChild ;if(p->rChild !=NULL)quene[++pre]=p->lChild ;}}void main(){BinaryTree <char> 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<<"二叉树z的先序遍历:"<<endl;z.PreOrder(Visit);cout<<endl;cout<<"层次遍历二叉树:";z.LevelOrder(Visit);cout<<endl;BinaryTree<char> q(z);cout<<"复制的二叉树q的先序遍历:"<<endl;q.PreOrder(Visit);cout<<endl;cout<<"树的高度:";cout<<z.GetHeight()<<endl;cout<<"叶子节点数量:";cout<<z.Size()<<endl;z.Exchange();cout<<"二叉树左右子树交换后的先序遍历:"<<endl;z.PreOrder(Visit);cout<<endl;}五、测试用例和运行结果测试用例如main函数中所示，结果如下图所示。

实验报告
（ 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，这个类非常好用，可以简单粗暴地提供一些方法和迭代器，让你将关键字和值绑定，这样我每新加入一个字母的数据块，我就可以记录下这对组合，不用之后搜索和解码的时
之后进行编码，其实也是一个搜索的过程，主要是调用了一个
测试：。

实验：哈夫曼树编码及译码的实现一．实验题目给定字符集的HUFFMANN编码与解码，这里的字符集及其字符频数自己定义，要求输出个字符集的哈夫曼编码及给定的字符串的哈夫曼码及译码结果。

二．实验原理首先规定构建哈夫曼树，然后进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。

首先定义一个结构体，这个结构体定义时尽可能的大，用来存放左右的变量，再定义一个地址空间，用于存放数组，数组中每个元素为之前定义的结构体。

输入n个字符及其权值。

构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：1.首先将地址空间初始化，将ht[0…n-1]中所有的结点里的指针都设置为空，并且将权值设置为0.2.输入:读入n个叶子的权值存于向量的前n个分量中。

它们是初始森林中n个孤立的根结点上的权值。

3.合并:对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。

每次合并分两步：①在当前森林ht[0…i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。

②将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。

具体操作：将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2 .新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。

4.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。

当用户输入字母时。

就在已经找好编码的编码结构体中去查找该字母。

查到该字母就打印所存的哈夫曼编码。

接着就是完成用户输入0、1代码时把代码转成字母的功能。

这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。

如果是1这就走向该结点的右结点，重复上面步骤。

实验报告
（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;
}
测试结果。

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

二. 实验环境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）二叉树验证实验调试结果六．实验小结本次实验主要是通过实验过程掌握二叉树的逻辑结构，掌握二叉树的二叉链表存储结构和掌握基于二叉链表存储的二叉树的遍历操作的实现。

福建农林大学金山学院实验报告系（教研室）：专业：计算机科学与技术年级：08 实验课程：姓名：学号：实验室号：_______ 计算机号：实验时间：指导教师签字：成绩：实验二：哈夫曼树及哈夫曼编码译码的实现（验证性、4学时）一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。

（1）掌握树的有关操作算法（2）熟悉树的基本存储方法（3）学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。

三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统（2）Turbo C 3.0四、算法描述及实验步骤1．算法描述(1).建立哈夫曼树的算法定义各节点类型其中应包含两类数据一是权重域weight；一是指针域而指针域中应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rdhild和parent来表示因此可用静态三叉链表来实现，在实际构造中由于是叶子节点来构造新的根节点其构造过程中仅与叶子节点的权重有关而与其数据域无关所以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，让后不断的将两颗最小权值的子树合并为一颗权值为其和的较大的子树，逐步生成各自内部节点直到树根。

(2).哈夫曼编码的算法将建立的哈夫曼树从每个叶子节点开始沿着双亲域回到根节点，梅走一步进行编码得到一位编码值；由于每个叶子节点的哈夫曼编码是从根节点到相应的叶子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位置。

2．算法流程图构建哈夫曼树算法流程哈夫曼编码算法流程3．代码仅作参考--redbatzero#include <stdio.h>#include <malloc.h>#define maxvalue 10000 //定义最大权值常量#define maxnodenumber 100 //定义节点最大数#define maxbit 10 //定义哈弗曼编码最大长度typedef struct //定义新数据类型即节点结构{int weight; //权重域int parent,lchild,rchild; //指针域}htnode; //节点类型标识符//typedef htnode * huffmanstree; //定义哈弗曼数类型htnode ht[maxnodenumber]; //定义三叉链表存储数组typedef struct //定义保存一个叶子节点哈弗曼编码的结构{int bit[maxbit]; //定义一维数组为编码域int start; //定义位置域}hcnodetype; //定义编码类型htnode * creatstree(int n) //huffmanstree creatstree(int n) //建立哈夫曼树算法实现函数{int i,j,m1,m2,k1,k2; //局部变量for(i=0;i<2*n-1;i++) //初始化各节点{ht[i].weight=0; //权重初始化为0ht[i].parent=-1; //根节点和给左右孩子初始化为-1ht[i].lchild=-1;ht[i].rchild=-1;}for(i=0;i<n;i++) //权重赋初值，由用户输入{scanf("%d",&ht[i].weight);}for(i=0;i<n-1;i++) //生成新节点构造哈夫曼树{m1=maxvalue; //预置最小权值变量为最大权值m2=maxvalue; //预置次小权值变量为最大权值k1=0; //预置最小权值节点位置为下标为0处k2=0; //预置次小权值节点位置为下标为0处for(j=0;j<n+i;j++) //循环找出每趟最下权值和所在位置if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;m1=ht[j].weight;k1=j;}else //当小于当前次小m2则更新m2及其位置if(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}ht[k1].parent=n+i; //修改最小权值节点的双亲为刚生成的新节点ht[k2].parent=n+i; //修改次小权值节点的双亲为刚生成的新节点ht[n+i].weight=ht[k1].weight+ht[k2].weight; //将新生成的权重值填入新的根节点ht[n+i].lchild=k1; //新生节点左孩子指向k1ht[n+i].rchild=k2; //新生节点右孩子指向k2}return ht; //返回哈夫曼树指针}void getstree(htnode * ht,int n) //哈夫曼编码算法及打印函数的实现{int i,j,c,p; //局部变量的定义hcnodetype cd[maxnodenumber]; //定义存储哈夫曼编码的数组for(i=0;i<n;i++) //循环控制对每一个节点进行编码{c=i; //为编码各节点初始化c和jj=maxbit;do{j--; //j指向bit中存放编码为的正确位置p=ht[c].parent; //p指向c的双亲节点if(ht[p].lchild==c) //如果c是p的左孩子cd[i].bit[j]=0; //编码为赋值0else //否则即c是p的右孩子cd[i].bit[j]=1; //编码赋值1c=p;//更新当前指针，为下一节点编码做准备}while(ht[p].parent!=-1); //判断是否编码结束即循环至最终根节点cd[i].start=j; //编码完成,记下编码开始位置}for(i=0;i<n;i++) //循环打印各节点哈夫曼编码{for(j=cd[i].start;j<maxbit;j++)//循环逐一输出printf("%d",cd[i].bit[j]);printf("\n"); //每输出一编码后换行}}int main() //主函数{int n;printf("请输入节点数:"); //用户输入节点数scanf("%d",&n);htnode * p; // huffmanstree p //定义哈夫曼树类型pp=(htnode * )malloc(sizeof(htnode *));//p=(huffmanstree)malloc(sizeof(huffmanstree))//分配内存空间p=creatstree(n);//调用建立哈夫曼树函数赋返回值给pgetstree(p,n); //调用编码函数读入建立的哈夫曼树p进行编码return 0;}五、调试过程出现该错误是因为type识别不了，即定义哈夫曼树时确切的说是type并不能定义htnode *标识符为huffmanstree：type htnode * huffmanstree这个小错误可以通过连个方法来修改一是将type改为typedef，当然直接删除该定义完全不会影响程序的执行，但在定义建立哈夫曼树函数时返回值应直接用htnode *；该错原因是参数未能成功传递，其中的ht[p]系统当做是未定义的类型可知，在getstree（htnode ht，int n）时正确的应当是传递哈夫曼树的头指针即数组首地址ht因此改为getstree（htnode * ht，int n）六、实验结果通过改正后成功编译连接，进行数据测试{5,20,12,7,47，9}当然编码因为定义时大小的左右排序是不同的所以编码也不唯一，但在这里是以左小右大来分布的，所以编码结果符合预期的。

数据结构实验，哈夫曼编码译码系统展开全文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：左孩子递归调用函数，输出当前结点元素，右孩子递归调用。

南邮数据结构实验报告实验目的，通过本次实验，我们旨在加深对数据结构的理解，掌握数据结构的基本操作和算法设计能力，提高对数据结构的应用能力和实际问题的解决能力。

一、实验内容。

1. 实验一，线性表的基本操作。

本次实验中，我们首先学习了线性表的基本概念和操作，包括插入、删除、查找等操作，并通过实际编程操作来加深对线性表的理解。

2. 实验二，栈和队列的应用。

在实验二中，我们通过实际编程操作来学习栈和队列的应用，包括中缀表达式转换为后缀表达式、栈的应用、队列的应用等内容。

3. 实验三，树和二叉树的基本操作。

实验三中，我们学习了树和二叉树的基本概念和操作，包括树的遍历、二叉树的建立和遍历等内容，并通过实际编程操作来加深对树和二叉树的理解。

4. 实验四，图的基本操作。

最后，我们学习了图的基本概念和操作，包括图的存储结构、图的遍历等内容，并通过实际编程操作来加深对图的理解。

二、实验过程。

在实验过程中，我们首先对实验内容进行了深入的学习和理解，掌握了数据结构的基本概念和操作方法。

然后，我们通过实际编程操作来加深对数据结构的理解，并通过调试和修改程序来提高对数据结构的应用能力和实际问题的解决能力。

在实验过程中，我们遇到了一些问题，但通过不懈的努力和团队合作，最终顺利完成了实验任务。

三、实验结果与分析。

通过本次实验，我们深入理解了数据结构的基本概念和操作方法，掌握了线性表、栈、队列、树、二叉树和图的基本操作，并通过实际编程操作加深了对数据结构的理解。

同时，我们也提高了对数据结构的应用能力和实际问题的解决能力，为今后的学习和工作打下了坚实的基础。

四、实验总结。

通过本次实验，我们不仅加深了对数据结构的理解，还提高了对数据结构的应用能力和实际问题的解决能力。

在今后的学习和工作中，我们将继续努力，不断提升自己的专业能力，为将来的发展打下坚实的基础。

以上就是本次实验的报告内容，谢谢！。

实验报告实验名称：二叉树的基本操作及哈夫曼编码译码系统的实现一、问题描述1.实验目的和要求a.创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。

b.哈夫曼编码/译码系统。

2.实验任务：能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存3.实验内容：a.①创建一棵二叉树；②先序、中序和后序遍历这棵二叉树；③计算二叉树结点个数b.哈夫曼编码译码系统二程序设计三.程序代码主函数：#include"CreateHfmTree.h"#include<fstream>#include<string>using namespace std;void main(){cout<<"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<Hfm Coding System>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl<<endl;cout<<"'M'------Show this menu."<<endl;cout<<"'B'------Build up tree: read character set and frequency of each character, build up hfm tree."<<endl;cout<<"'T'------Trace the tree: PreOrder and InOrder the BTree."<<endl;cout<<"'E'------Generate code: According to the builded up hfm tree, generate the codes for all character."<<endl;cout<<"'C'------Encode: Input arbitary string formed by characters which have been generated code, utilize the codes to ecode and print the result of encoding.(end with '#')"<<endl;cout<<"'D'------Translate: read codefile.txt, utilize the exisiting hfm tree to translate code and restore code Into hardware file result.txt."<<endl;cout<<"'P'------Print: Print the contents of file: textfile.txt, codefile.txt, result.txt on the screen."<<endl;cout<<"'X'------Exit: Exit this system."<<endl;cout<<"'-'------Delete: Delete character set, character frequencies, codes and HfmTree if they are exist."<<endl;int w[100]; char data[100];int n; char choice; int i,j;HfmTree<int> hfm;HfmNode* ht;HfmCode* hc;char s[1000];repeat1:cout<<endl;cout<<"Please input your chioce: "; cin>>choice;cout<<endl;if(choice=='b' || choice=='B'){cout<<"Please input the number of elementary code: "; cin>>n;cout<<"---------------------------------------------------------------"<<endl;cout<<"Allocating the memory..."<<endl;cout<<"Allocating the complete."<<endl;cout<<"---------------------------------------------------------------"<<endl;cout<<"Please input all the elementary codes: "<<endl;for(int i=0;i<n;i++) cin>>data[i];cout<<"Please input all the Frenquencies: "<<endl;for(i=0;i<n;i++) cin>>w[i];hfm=CreateHfmTree(w,data,4); goto repeat1;}if(choice=='t' || choice=='T'){cout<<"hfm"; hfm.PreOrder(Visit);cout<<"hfm"; hfm.InOrder(Visit);goto repeat1;}if(choice=='e' || choice=='E'){cout<<"Generating code..."<<endl;ht=new HfmNode[2*n-1];hc=new HfmCode[n];hfm.Grcode(w,data,n,ht,hc);for( i=0;i<n;i++){cout<<"'"<<ht[i].word<<"':";for( j=hc[i].start+1;j<n;j++)cout<<hc[i].bit[j];cout<<endl;}cout<<"Code Generate complete."<<endl;goto repeat1;}if(choice=='c' || choice=='C'){cout<<"Please input the article that you want to code: "<<endl;char ch; int i=0;while(1){cin>>ch;s[i++]=ch;if(ch=='#')break;}int length=i;ofstream outf("testfile.txt");if(!outf){cout<<"Can't Open the file!"; return;}i=0;while(s[i]!='#'){outf.put(s[i]);i++;}outf.close();cout<<endl;cout<<"Result of encoding: ";hfm.Encode(ht,hc,n,"testfile.txt","codefile.txt");cout<<endl;cout<<"Encoding complete."<<endl<<endl;goto repeat1;}if(choice=='d' || choice=='D'){cout<<"Starting translating code..."<<endl;cout<<"Result:";hfm.Decode(ht,n,"codefile.txt","resultfile.txt");cout<<endl;goto repeat1;}if(choice=='p' || choice=='P'){cout<<"----------------------testfile.txt----------------------"<<endl;hfm.Print("testfile.txt");cout<<"--------------------------------------------------------"<<endl;cout<<endl<<endl;cout<<"----------------------codefile.txt----------------------"<<endl;hfm.Print("codefile.txt");cout<<"--------------------------------------------------------"<<endl;cout<<endl<<endl;cout<<"----------------------resultfile.txt----------------------"<<endl;hfm.Print("resultfile.txt");cout<<"--------------------------------------------------------"<<endl;cout<<endl<<endl;goto repeat1;}if(choice=='x' || choice=='X')return;if(choice=='-'){hfm.Clear();cout<<"Delete All..."<<endl;goto repeat1;}二叉树类：#include"BTNode.h"#include"seqqueue.h"template<class T>class BinaryTree{public:BinaryTree() {root=NULL;}bool IsEmpty() const;void Clear();bool Root(T& x) const;void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>&right);void MakeTree(const T& x,const T& y,BinaryTree<T>&left,BinaryTree<T>& right);void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);void PreOrder(void (*Visit) (T& x)); void InOrder(void (*Visit) (T& x));void PostOrder(void (*Visit) (T& x));void LevalOrder() ;int Size();protected:BTNode<T> *root;private:void Clear(BTNode<T>* t);void PreOrder(void (*Visit) (T& x),BTNode<T> *T);void InOrder(void (*Visit) (T& x),BTNode<T> *T);void PostOrder(void (*Visit) (T& x),BTNode<T> *T);void LevalOrder(BTNode<T>* t);int Size(BTNode<T>* t);};template<class T>bool BinaryTree<T>::IsEmpty() const{return root==NULL;}template<class T>void BinaryTree<T>::Clear(BTNode<T>* t){if(t){if(t->lChild)Clear(t->lChild);if(t->rChild)Clear(t->rChild);delete t;t=NULL;}}template<class T>void BinaryTree<T>::Clear(){Clear(root);}template <class T>bool BinaryTree<T>::Root(T &x) const{if (root){x=root->element;return true;}elsereturn false;}template <class T>void BinaryTree<T>::MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right){cout<<"here in BinaryTree<T>::MakeTree."<<endl;if(root || &left==&right) return;root=new BTNode<T>(x,left.root,right.root);left.root=right.root=NULL;}template <class T>void BinaryTree<T>:: MakeTree(const T& x,const T& y,BinaryTree<T>& left,BinaryTree<T>& right){if(root || &left==&right) return;root=new BTNode<T>(x,y,left.root,right.root);left.root=right.root=NULL;}template <class T>void BinaryTree<T>::BreakTree(T &x,BinaryTree<T>&left, BinaryTree<T>& right){cout<<"here in BinaryTree<T>::BreakTree."<<endl;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<class T>void Visit(T& x){cout<<x<<" ";}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->lChild);PreOrder(Visit,t->rChild);}}template <class T>void BinaryTree<T>::InOrder(void (*Visit)(T& x)){cout<<"中序遍历为： ";InOrder(Visit,root);}template <class T>void BinaryTree<T>::InOrder (void (*Visit)(T& x),BTNode<T>* t) {if (t){InOrder(Visit,t->lChild);Visit(t->element);InOrder(Visit,t->rChild);}}template <class T>void BinaryTree<T>::PostOrder(void (*Visit)(T& x)){cout<<"后序遍历为： ";PostOrder(Visit,root);cout<<endl;}template <class T>void BinaryTree<T>::PostOrder(void (*Visit)(T& x),BTNode<T>* t) {if (t){PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);Visit(t->element);}}template <class T>void BinaryTree<T>::LevalOrder(BTNode<T>* t){SeqQueue<BTNode<T>*> q(100);if(!t) return ;q.EnQueue(t);while(!q.IsEmpty()){t=q.DeQueue();cout<<t->element<<" ";if(t->lChild) q.EnQueue(t->lChild);if(t->rChild) q.EnQueue(t->rChild);}}template<class T>void BinaryTree<T>::LevalOrder(){LevalOrder(root);}template<class T>int BinaryTree<T>::Size(BTNode<T>* t){if(!t) return 0;elsereturn Size(t->lChild)+Size(t->lChild)+1;}template<class T>int BinaryTree<T>::Size(){return Size(root);}二叉树结点类：#include<iostream.h>template<class T>struct BTNode{BTNode() {lChild=rChild=NULL;}BTNode(const T& x){element=x; lChild=rChild=NULL;}BTNode(const T& x,BTNode<T>* l,BTNode<T>* r){element=x; lChild=l; rChild=r;}BTNode(const T& x,const T& y,BTNode<T>* l,BTNode<T>* r) {element=x; word=y; lChild=l; rChild=r;}T element;T word;BTNode<T> *lChild,*rChild;};哈夫曼树类：#include"BinaryTree.h"#include<fstream>struct HfmNode{char word;int weight;int parent;int lchild;int rchild;};struct HfmCode{int bit[10000];int start;int weight;};template<class T>class HfmTree:public BinaryTree<T>{public:operator T()const {return weight;}T getW() {return weight;}void putW(const T& x) {weight=x;}void SetNull() {root=NULL;}void Grcode(T w[],char c[],int n,HfmNode ht[],HfmCode hc[]);void Encode(HfmNode ht[],HfmCode hc[],int count,char *record,char *tranvers);void Decode(HfmNode ht[],int count,char *in,char *fout);void Print(char *in);private:T weight;};template<class T>void HfmTree<T>::Grcode(T w[],char c[],int n,HfmNode ht[],HfmCode hc[]) {int m1,m2,x1,x2;char d1,d2;int i,j;for(i=0;i<2*n-1;i++){if(i<n){ht[i].weight=w[i];ht[i].word=c[i];}else{ht[i].weight=0;ht[i].word='#';}ht[i].parent=0;ht[i].lchild=-1;ht[i].rchild=-1;}for(i=0;i<n-1;i++){m1=m2=1000;x1=x2=0;d1=d2='#';for( j=0;j<n+i;j++){if(ht[j].weight<m1 && ht[j].parent==0) {m2=m1; m1=ht[j].weight;d2=d1; d1=ht[j].word;x2=x1;x1=j;}else if(ht[j].weight<m2 && ht[j].parent==0) {m2=ht[j].weight;d2=ht[j].word;x2=j;}}ht[x1].parent=n+i;ht[x2].parent=n+i;ht[n+i].weight=ht[x1].weight+ht[x2].weight;ht[n+i].lchild=x1;ht[n+i].rchild=x2;}HfmCode cd;int child,parent;for(i=0;i<n;i++){cd.start=n-1;cd.weight=ht[i].weight;child=i;parent=ht[child].parent;while(parent!=0){if(ht[parent].lchild==child)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;child=parent;parent=ht[child].parent;}for(j=cd.start+1;j<n;j++){hc[i].bit[j]=cd.bit[j];hc[i].start=cd.start;hc[i].weight=cd.weight;}}}template<class T>void HfmTree<T>::Encode(HfmNode ht[],HfmCode hc[],int count,char *record,char *tranvers){ifstream infile(record);if(!infile){cout<<"Can't Open the file!"; return;}ofstream outf(tranvers);if(!outf){cout<<"Can't Open the file!"; return;}char ch;while(infile.get(ch)){for(int i=0;i<count;i++){if(ch==ht[i].word){for(int j=hc[i].start+1;j<count;j++){outf<<hc[i].bit[j];cout<<hc[i].bit[j];}break;}}}outf<<'#';infile.close();outf.close();}template<class T>void HfmTree<T>::Decode(HfmNode ht[],int count,char *in,char *fout) {int i=0;char ch,buffer[100]; //用来存放编码文件中的字符ifstream infile(in);if(!in){cout<<"Can't Open the file!"; return;}while(infile.get(ch)){buffer[i++]=ch;}infile.close();int j=i;int p=2*count-2;ofstream outf(fout);if(!fout){cout<<"Can't Open the file!"; return;}char null=' ';//将译码存放在resultfile文件中for(i=0; buffer[i]!='#' &&i<j;i++ ){if(buffer[i]=='0')p=ht[p].lchild;elsep=ht[p].rchild;if(ht[p].lchild==-1 && ht[p].rchild==-1){outf<<ht[p].word;cout<<ht[p].word;p=2*count-2;}}outf.close();}template<class T>void HfmTree<T>::Print(char *in){ifstream infile(in);if(!infile){cout<<"Can't Open the file!"; return;}char ch;while(infile.get(ch))cout<<ch;cout<<endl;infile.close();}构建哈夫曼树：#include"HfmTree.h"#include"PrioQueue.h"template<class T>HfmTree<T> CreateHfmTree(T w[],char c[],int n){PrioQueue <HfmTree<T> > pq(n);//定义一个元素类型为hfmtree的优先权队列HfmTree<T> x,y,z,zero;for(int i=0;i<n;i++){z.MakeTree(w[i],c[i],x,y); //构造只有一个节点的哈夫曼树对象z.putW(w[i]);pq.Append(z);z.SetNull();}for(i=1;i<n;i++){pq.Serve(x); pq.Serve(y);z.MakeTree(x.getW()+y.getW(),x,y);z.putW(x.getW()+y.getW());pq.Append(z);z.SetNull();}pq.Serve(z);return z;}队列类，优先权队列类：#include<iostream.h>template<class T>class Queue{public:virtual bool IsEmpty() const=0;virtual bool IsFull() const=0;virtual bool Front(T& x) const=0;virtual bool EnQueue(T x)=0;virtual T DeQueue()=0;virtual bool Clear()=0;};#include"queue.h"template<class T>class SeqQueue:public Queue<T>{public:SeqQueue(int mSize);~SeqQueue() {delete []q;}bool IsEmpty() const {return front==rear;}bool IsFull() const {return (rear+1) % maxSize==front;}bool Front(T& x)const;bool EnQueue(T x);T DeQueue();bool Clear() {front=rear=0;return true;}private:int front,rear;int maxSize;T *q;};SeqQueue<T>::SeqQueue(int mSize){maxSize=mSize;q=new T[maxSize];front=rear=0;}//在x中返回队头元素。

实验报告（2015 / 2016学年第二学期）课程名称数据结构A实验名称二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2016 年 4 月14 日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专业信息管理与信息系统实习题名:二叉树的基本操作班级姓名学号日期2016.04.14一、问题描述设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。

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

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

二、概要设计文件tree.cpp中在该文件中定义二叉树的链式存储结构，用队列实现二叉树的层次遍历，并且编写实现二叉树的各种基本操作函数。

其中包括结点类BTNode，循环队列类SeqQueue，二叉树类BinaryTree。

主函数main的代码如图所示。

三、详细设计1.类和类的层次设计程序定义了循环队列SeqQueue类和二叉树BinaryTree类。

SeqQueue类主要是用队列实现，层次遍历。

运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算树的高度，最后删除二叉树。

（b）二叉树类2.核心算法程序利用循环队列SeqQueue类通过不断出队并输出节点的值，将左右孩子入队直到队列为空实现二叉树的层次遍历。

并运用后序遍历思想，将二叉树树分解为左右子树和根结点，利用(p -> lChild)和(p -> rChild)计算结点数目，并通过交换结点的左右子树实现左右交换，计算树的高度，最后删除二叉树。

核心算法主要是二叉树BinaryTree类中的High，Node_num，Exchange，Level_traversal四个函数，其设计流程图如下：High()Node_num()Exchange（）Level_traversal()四、程序代码template<class T>int BinaryTree<T>::Node_num(BTNode<T>*p) //叶子结点{if(p){if(p -> lChild == NULL && p -> rChild == NULL)return 1;elsereturn Node_num(p -> lChild) + Node_num(p -> rChild);}elsereturn 0;}template<class T>void BinaryTree<T>::Exchange(BTNode<T>*&t) //左右子树交换{if(t){BTNode<T>*q = t -> lChild;t -> lChild = t->rChild;t -> rChild = q;Exchange(t -> lChild);Exchange(t -> rChild);}}template<class T>void BinaryTree<T>::Level_traversal(void(*Visit)(T&x)) //层次遍历{Level_traversal(Visit, root);cout << endl;}template<class T>void BinaryTree<T>::Level_traversal(void(*Visit)(T&x),BTNode<T>*t) //层次遍历{BTNode<T> *a;Visit(t -> element);if(t -> lChild)s.EnQueue(t -> lChild);if(t -> rChild)s.EnQueue(t -> rChild);while(s.Front(a) == true){if(a -> lChild)s.EnQueue(a -> lChild);if(a -> rChild)s.EnQueue(a -> rChild);Visit(a -> element);s.DeQueue();}}五、测试和调试1.测试用例和结果测试结果如下图2.结果分析1)程序能够正确的实现二叉树的基本的建立、删除、复制、遍历以及结点计算等基本操作。

实验报告（2015/2016学年第2学期）课程名称数据结构A实验名称二叉树的基本操作及哈夫曼编译译码系统的实现实验时间2016 年 4 月13 日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专业信息管理与信息系统实验一：二叉树基本操作一、问题陈述在二叉链表上实现二叉树的建立、删除、求高度、求子叶节点数、左右交换、遍历等操作。

二、概要设计建立不同函数，分别实现二叉树的各项基本运算。

三、详细设计1.层次结构：文件一共需要5个函数。

文件中包含各个函数函数的声明。

分别是：status createbitree(bitree *t);status preordertraverse(bitree t);int height(bitree t);void s *t);void leafcounts(bitree t);2.核心算法：主函数四、程序代码#include<iostream.h>#include<malloc.h>#define FALSE 0#define TRUE 1#define OK 1#define maxsize 100typedef int status;typedef int elemtype;typedef struct binode{elemtype data;struct binode *lchild,*rchild;}binode,*bitree;status treecreated=FALSE;int leafcount=0;status createbitree(bitree *t);status preordertraverse(bitree t);int height(bitree t);void s *t);void leafcounts(bitree t);void main(){int choice=0;status leave=FALSE,flag;binode *bt;cout<<"===========二叉树演示程序==============="<<endl;do{cout<<"1：创建二叉树，按先序遍历结果输入"<<endl;cout<<"2：先序遍历二叉树，递归方式遍历二叉树"<<endl;cout<<"3：求叶子数"<<endl;cout<<"4：计算二叉树的高度"<<endl;cout<<"5: 树进行左右翻转"<<endl;cout<<"0：退出"<<endl;cout<<"-------请输入:"<<endl;cin>>choice;switch(choice){case 1:if(treecreated){cout<<"树还没有建立"<<endl;break;};cout<<"请输入代表树的数字："<<endl;flag=createbitree(&bt);if(flag==OK){cout<<"你已经建立了一棵树了！"<<endl;treecreated=TRUE;}break;case 2:if(!treecreated){cout<<"sorry,you must create a tree for further steps!"<<endl;break;}cout<<"先序遍历顺序:"<<endl;preordertraverse(bt);cout<<endl;break;case 3:if(!treecreated){cout<<"sorry,you must create a tree for further steps!"<<endl;break;}leafcounts(bt);cout<<"树的叶子数:"<<leafcount<<endl;cout<<endl;break;case 4:int h;h=height(bt);cout<<"树的高度:"<<h<<endl;break;case 5:s);cout<<"树已经翻转！！！"<<endl;break;case 0:leave=TRUE;break;}}while(!leave);cout<<" 再见"<<endl;}status createbitree(bitree *t){int ch=0;cin>>ch;if(ch==0)(*t)=NULL;else{(*t)=(bitree)malloc(sizeof(binode));(*t)->data=ch;createbitree(&(*t)->lchild);createbitree(&(*t)->rchild);}return OK;}status preordertraverse(bitree t){if(t){cout<<t->data<<" ";preordertraverse(t->lchild);preordertraverse(t->rchild);return OK;}elsereturn OK;}int height(bitree t){int hl,hr;if(t==NULL)return 0;hl=height(t->lchild)+1;hr=height(t->rchild)+1;return (hl>hr?hl:hr);}void s *t){bitree p;if(*t!=NULL){p=(*t)->lchild;(*t)->lchild=(*t)->rchild;(*t)->rchild=p;swap(&(*t)->lchild);swap(&(*t)->rchild);}}void leafcounts(bitree t){if(t){if(t->lchild==NULL && t->rchild==NULL)leafcount++;leafcounts(t->lchild);leafcounts(t->rchild);}}测试和调试五、 实验小结（1） 加深了我对链表方面知识的理解与运用（2） 在进行输入时，一定要细心，少犯没有分号，括号数目不对等低级错误，这会大大增加调试的时间。

南邮数据结构实验报告南邮数据结构实验报告一、实验目的和背景数据结构是计算机科学中非常重要的一门基础课程，它研究了数据的组织、存储和管理方式，是计算机程序设计的基础。

本次实验旨在通过对南京邮电大学数据结构实验的学习和实践，加深对数据结构相关概念和算法的理解，并掌握数据结构在实际问题中的应用。

二、实验内容本次实验涉及到以下几个数据结构的实现和应用：1. 线性表：线性表是最简单的一种数据结构，它包括顺序表和链表两种实现方式。

我们需要实现线性表的基本操作，如插入、删除、查找等，并通过实际案例加深对线性表的理解。

2. 栈和队列：栈和队列是两种特殊的线性表，它们的插入和删除操作都受限制。

我们需要实现栈和队列的基本操作，并通过实例分析它们在实际问题中的应用。

3. 二叉树：二叉树是一种重要的非线性数据结构，它具有良好的递归性质。

我们需要实现二叉树的创建、遍历和查找等操作，并通过实例研究二叉树在排序和搜索问题中的应用。

4. 图：图是一种复杂的非线性数据结构，它由节点和边组成。

我们需要实现图的创建、遍历和最短路径等操作，并通过实例研究图在网络和路径规划等问题中的应用。

三、实验过程和结果在实验过程中，我们首先学习了相关的数据结构概念和算法原理，并通过编程语言实现了上述数据结构的基本操作。

在实验过程中，我们遇到了一些问题，如内存泄漏、指针操作错误等，但通过调试和修改代码，最终成功实现了各个数据结构的功能。

在实验结果方面，我们通过自己编写的测试用例对实现的数据结构进行了验证。

例如，对于线性表的插入和删除操作，我们分别测试了在表头、表尾和表中插入或删除元素的情况，并验证了操作的正确性。

对于二叉树的遍历操作，我们通过构建不同形态的二叉树，验证了前序、中序和后序遍历的正确性。

四、实验总结和心得体会通过本次实验，我们深入了解了数据结构的基本概念和常用算法，掌握了数据结构在实际问题中的应用。

同时，我们也意识到了数据结构的重要性和实践的必要性。

利用二叉树实现哈夫曼编码、解码。

根据主题要求，本文将介绍如何利用二叉树实现哈夫曼编码和解码。

哈夫曼编码是一种常用的数据压缩算法，通过对字符及其出现频率进行编码，使得频率高的字符使用较短的编码，从而实现数据的高效压缩。

下面将详细介绍哈夫曼编码和解码的步骤。

一、哈夫曼编码1. 统计字符出现频率：首先，需要统计待编码文本中各字符的出现频率。

可以通过遍历文本，使用字典或哈希表来记录每个字符及其对应的出现次数。

2. 构建哈夫曼树：根据字符的出现频率，构建哈夫曼树。

哈夫曼树是一种满足以下特点的二叉树：每个非叶子节点都有两个子节点，且叶子节点对应输入文本的字符。

构建哈夫曼树的算法如下：a. 创建一个包含所有字符及其频率的最小优先队列（最小堆）。

b. 将队列中频率最低的两个节点取出，创建一个新的节点作为它们的父节点，父节点的频率等于两个子节点的频率之和。

将这个新的父节点插入队列中。

c. 重复步骤b，直到队列中只剩下一个节点，这个节点即为哈夫曼树的根节点。

3. 生成编码表：根据哈夫曼树，生成每个字符对应的编码表。

编码表是一个字典或哈希表，其中每个键值对表示一个字符和对应的哈夫曼编码。

生成编码表的算法如下：a. 从根节点出发，向左遍历，记下路径为0，向右遍历，记下路径为1。

b. 当遍历到叶子节点时，将该字符及其对应的路径作为一个键值对添加到编码表中。

c. 重复步骤a 和b，直到遍历完所有叶子节点。

4. 进行编码：根据编码表，将输入文本中的每个字符进行编码。

将每个字符按照编码表进行替换，得到对应的哈夫曼编码序列。

5. 输出编码结果：将编码后的序列保存起来，这就是文本的哈夫曼编码结果。

二、哈夫曼解码1. 读入编码结果：将编码结果作为输入，准备进行哈夫曼解码。

2. 遍历编码结果：从根节点开始，根据字符编码的每一位进行遍历。

通过判断当前位是0 还是1，决定向左还是向右移动，并进入相应的子节点。

3. 判断是否为叶子节点：在移动到某个节点后，判断该节点是否为叶子节点。

课程设计报告（ 2013 /2014 学年第 2 学期）题目：二叉树基本操作与哈夫曼编码译码系统的设计专业：学生姓名：班级学号：指导教师指导单位日期课题题目二叉树基本操作与哈夫曼编码译码系统的设计一、课题内容和要求创建一棵二叉树，分别实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。

设计哈夫曼编码/译码系统。

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

二、需求分析我们根据需求得到以上的菜单，以链表方式存储二叉树，以插入二叉搜索树的方式，将数据一个一个地插入二叉树，以递归的方式分别实现先、中、后三种方式的遍历和计算二叉树的高度，删除二叉树时，先搜索找到那个节点，若有两个子节点，查找中序遍历直接后继节点，之后常规的替代删除操作，最后是哈夫曼树的实现，从文件读取字符串的时候，用while循环来得到每个字母的出现次数，得到权值，之后实现哈夫曼树，通过译码函数输出译码序列。

三、概要设计typedef char Etype;typedef struct btnode{Etype data;struct btnode * lch,* rch;int weight;}btnode;typedef struct btree{struct btnode * root;}btree;typedef struct {int weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char ** HuffmanCode;其他的就是各类函数，见下文。

四、详细设计#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<conio.h>#include<fstream.h>typedef char Etype;typedef struct btnode{Etype data;struct btnode * lch,* rch;int weight;}btnode;typedef struct btree{struct btnode * root;}btree;btnode * newnode(){btnode * p=(btnode*)malloc(sizeof(btnode));return p;}btnode * newnode(Etype e){btnode * p=(btnode*)malloc(sizeof(btnode));p->data=e;p->lch=NULL;p->rch=NULL;return p;}void MAKEBTREE(btree * bt,int x,btree *lt,btree * rt) {btnode * p=newnode();p->weight=x;p->lch=lt->root;p->rch=rt->root;lt->root=NULL;rt->root=NULL;bt->root=p;}void CREATEBTREE(btree * bt) /*构造一颗空二叉数*/{bt->root=NULL;}//模仿先序递归遍历方法，建立二叉树btnode *creat_bt2(){btnode *t;Etype e;scanf("%c",&e);if(e=='#')t=NULL; //对于'#'值，不分配新结点else{t=(btnode *)malloc(sizeof(btnode));t->data=e;t->lch=creat_bt2(); //左孩子获得新指针值t->rch=creat_bt2(); //右孩子获得新指针值}return t;} //creat_bt2void preorder(btnode *p) //前序遍历{if(p){printf("%3c",p->data);preorder(p->lch);preorder(p->rch);}} //preorder//中序递归遍历二叉树void inorder(btnode *p){if(p){inorder(p->lch);cout<<p->data<<endl;inorder(p->rch);}} //inorder//后序递归遍历二叉树void postorder(btnode *p){if(p){ postorder(p->lch);postorder(p->rch);cout<<p->data<<endl;}} //postorderint Depth(btnode * p){if(!p)return 0;elsereturn 1+((Depth(p->lch)>Depth(p->rch))?Depth(p->lch):Depth(p->rch)); }int leafcount(btnode * bt) //输入btree的root { //计算叶结点数int count=0;if(bt!=NULL){leafcount(bt->lch);leafcount(bt->rch);}if((bt->lch==NULL)&&(bt->rch==NULL))count++;return count;}int remove(btree *bt) //输入那个节点的值{btnode *p=bt->root;btnode *c,*r,*s,*q;Etype x,e;cout<<"请输入要删除的节点的值"<<endl;cin>>e;while(p&&p->data!=e){q=p;if(e<p->data)p=p->lch;else p=p->rch;}if(!p){cout<<"不存在"<<endl;return 0;}x=p->data;if(p->lch&&p->rch){s=p->rch;r=p;while(s->lch){r=s;s=s->lch;}p->data=s->data;p=s;q=r;}if(p->lch)c=p->lch;else c=p->rch;if(p==bt->root)bt->root=c;else if(p==q->lch)q->lch=c;else q->rch=c;free(p);return 1;}int insert(btree *btr,Etype et) //二叉搜索树的插入函数{btnode * r, *p=btr->root, *q;while(p){q=p;if(et<p->data)p=p->lch;else if(et>p->data)p=p->rch;else{cout<<"duplicate"<<endl;return 0;}}r=newnode(et);if(btr->root)if(et<q->data)q->lch=r;else q->rch=r;else btr->root=r;return 1;}void mycreate (btree bt) //创建二叉搜索树{int x=1;Etype c;cout<<"第一个输入的值为根的值,请输入根值"<<endl;cin>>c;btnode btn;btn.lch=NULL;btn.rch=NULL;btn.data=c;bt.root->data=btn.data;bt.root->lch=btn.lch;bt.root->rch=btn.rch;c=getchar();cout<<"其他节点的值"<<endl;while((c=getchar())!='\n'&& x){x=insert(&bt,c);}}void Fmin(btree ht[],int * k1,int * k2,int k) {int a,b,c,d;a=ht[0].root->weight;b=ht[0].root->weight;*k1=0;*k2=0;for(c=0;c<k;c++){if(a>=ht[c].root->weight){a=ht[c].root->weight;*k1=c;}}for(d=0;d<k;d++){if(d==*k1)continue;if(b>=ht[d].root->weight){b=ht[d].root->weight;*k2=d;}}}btree createhfmtree() //生成哈弗曼树{btree zero,ht[26];int i,k,k1,k2;int w[26];for(i=0;i<26;i++)w[i]=0;CREATEBTREE(&zero);FILE* fp;fp=fopen("c:\\test.txt","r+");while(!feof(fp)){w[fgetc(fp)-97]++;}for(i=0;i<26;i++){MAKEBTREE(&ht[i],w[i],&zero,&zero);ht[i].root->data=97+i;printf("%3d ",ht[i].root->data);}for(k=25;k>0;k--){Fmin(ht,&k1,&k2,k);MAKEBTREE(&ht[k1],ht[k1].root->weight+ht[k2].root->weight,&ht[k1],&ht[k2]);ht[k1].root->data='!';printf("%3d ",ht[k1].root->data);ht[k2]=ht[k];}return ht[0];}int m,s1,s2;typedef struct {int weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char ** HuffmanCode;void Select(HuffmanTree HT,int n) {int i,j;for(i=1;i<=n;i++)if(HT[i].parent==0){s1=i;break;}for(j=i+1;j<=n;j++)if(HT[j].parent==0){s2=j;break;}for(i=1;i<=n;i++){if(HT[i].parent==0)if(HT[s1].weight>HT[i].weight)if(s2!=i)s1=i;}for(j=1;j<=n;j++){if(HT[j].parent==0)if(HT[s2].weight>HT[j].weight)if(s1!=j)s2=j;}if(s1>s2){int temp=s1;s1=s2;s2=temp;}}void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {int i;char *cd;int p;int cdlen;if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));for (i=1; i<=n; i++){HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for (i=n+1; i<=m; i++){HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}//添加查看，便于调试/*printf("构造过程显示：\n");for(i=1;i<=m;i++)printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);system("pause");*/for(i=n+1;i<=m;i++){Select(HT,i-1);HT[s1].parent = i; HT[s2].parent = i;HT[i].lchild = s1; HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;//添加查看，便于调试/*printf("s1=%d,s2=%d\n",s1,s2);for(j=1;j<=i;j++)printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);system("pause");*/}cd = (char *)malloc(n*sizeof(char));p=m;cdlen=0;for(i=1;i<=m;i++)HT[i].weight=0;while(p){if(HT[p].weight==0){HT[p].weight=1;if(HT[p].lchild!=0){p=HT[p].lchild;cd[cdlen++]='0';}else if(HT[p].rchild==0){HC[p]=(char *)malloc((cdlen+1)*sizeof(char));cd[cdlen]='\0';strcpy(HC[p],cd);}}else if(HT[p].weight==1){HT[p].weight=2;if(HT[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]='1';}}else{HT[p].weight=0;p=HT[p].parent;--cdlen;}}}int hfm(){HuffmanTree HT;HuffmanCode HC;int *w,i;int n=0;int x,y,z=0;FILE *fp;fp=fopen("c:\\test.txt","r+");FILE * fp2=fopen("c:\\test.txt","r+"); int zimu[26]={0};repeat:while(!feof(fp)){y=fgetc(fp);for(x=97;x<123;x++){for(i=0;i<z;i++){if(y==zimu[i])goto repeat;}if(x==y){n++;zimu[z]=y;z++;}}}HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode)); w=(int *)malloc(n*sizeof(int));for(i=0;i<n;i++){w[i]=0;}while(!feof(fp2)){w[fgetc(fp2)-97]++;}HuffmanCoding(HT,HC,w,n);printf("输出编码：\n");for(i=1;i<=n;i++)printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);return 0;}void main(){char ch;int k;btree * t;btree bt,hfmbt;bt.root=(btnode *)malloc(sizeof(btnode));do{printf("\n\n\n");printf("\n===================主菜单===================");printf("\n\n 1.建立二叉搜索树");printf("\n\n 2.建立二叉树方式二");printf("\n\n 3.先序递归遍历二叉树");printf("\n\n 4.中序递归遍历二叉树");printf("\n\n 5.后序递归遍历二叉树");printf("\n\n 6.计算二叉树的高度");printf("\n\n 7.删除某个二叉树节点");printf("\n\n 8.从文件读取文本得到权值生成哈夫曼树");printf("\n\n 0.结束程序运行");printf("\n============================================");printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8)");scanf("%d",&k);switch(k){case 1:mycreate(bt);t=&bt;break;case 2:printf("\n请输入二叉树各结点值:");fflush(stdin);t->root=creat_bt2();break; //调用递归建立二叉树算法case 3:if(t){printf("先序遍历二叉树:");preorder(t->root);printf("\n");}else printf("二叉树为空!\n");break;case 4:if(t){printf("中序遍历二叉树:");inorder(t->root);printf("\n");}else printf("二叉树为空!\n");break;case 5:if(t){printf("后序遍历二叉树:");postorder(t->root);printf("\n");}else printf("二叉树为空!\n");break;case 6:if(t){printf("二叉树的高度为：%d",Depth(t->root));printf("\n");}else printf("二叉树为空！\n");break;case 7:remove(t);break;case 8:hfm();break;case 0:exit(0);} //switch}while(k>=1&&k<=10);printf("\n再见！按回车键，返回…\n");ch=getchar();} //main五、测试数据及其结果分析六、调试过程中的问题创建二叉树的时候，要注意生成节点，不能只是给指针赋值，只有生成节点，二叉树才能保存下来。

数据结构实验报告题目：数据结构实验报告学院：工商管理学院班级：信息1001姓名：彭振宇学号：时间：2012/6/26实验三：树和二叉树的应用一．实验题目：树和二叉树的应用二．实验内容：哈夫曼编码设计三．实验目的：掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。

四．实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。

五．概要设计原理：1.选择parent为0且weight最小的两个结点。

其序号分别为s1和s22.建立赫夫曼树叶3.从叶子到根逆向求每个字符的赫夫曼编码4.输出构造的树5.输出得到的各权Huffman编码六．详细程序清单及注释说明：#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 30 //最大叶子数#define MAXCODE 10000 //编码最大长度#define OK 1#define ERROR 0#define OVERLOW -2//=============赫夫曼树和赫夫曼编码的存储表示=====typedef struct{unsigned int weight;unsigned int parent, lchild, rchild;}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表/*----------------算法描述----------------*/void Select(HuffmanTree HT, int n, int *s1, int *s2)//选择parent为0且weight最小的两个结点。