数据结构实验，哈夫曼编码/译码系统

饮茶仙人 2016-05-19

展开全文

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声明为友元类。二叉树类中包含了建树，判断二叉树是否为空，求结点数，求高度，删除，交换左右子树，三种次序遍历及按层次遍历，清空二叉树等函数。在主函数中调用实现这些功能。

类和类的层次设计

BTNode

BTree

T element;

BTNode<T> *lchild, *rchild;

BTNode<T>* root;

friend class BTree<T>;

friend void Visit(BTNode<T>*p);

friend void Print(BTNode<T>*p);

friend void ex(BTNode<T>*p);

bool IsEmpty()const;

bool Root(T &x)const;

void MakeTree(const T &e ,BTree<T>& left, BTree<T>& right);

void BreakTree(T &e ,BTree<T>& left,BTree<T>& right);

void PreOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);

void InOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);

void PostOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);

int Size(BTNode<T>* t);

int GetHeight(BTNode<T>* t);

void BfsOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);

void Change(BTNode<T> *t);

void Clear(BTNode<T> *t);

主要算法：

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

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

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

BfsOrder：使用一个队列结构，队列元素是指向结点的指针，将当前结点入队，当队列元素没有全部出队时，队头元素出队，如果有左右孩子，左右孩子进队，循环该操作。

Change：左右孩子递归调用函数，交换当前结点左右孩子。

2) 哈夫曼树

首先定义优先权队列的类PrioQueue，实现Append及Serve，这样就可以实现哈夫曼树的构建。其次修改二叉树结点类BTNode，在增加指向双亲的parent域，修改二叉树类MakeTree函数设置该域的值。在二叉树类中添加编码译码等函数。

类和类的层次设计：

BTree

PrioQueue

HfmTree:public BTree

…

T *q;

int n,maxSize;

T weight;

…

void CreatCode(BTNode<T>*t);//生成哈夫曼编码

String2Code(BTNode<T>*t,char *s);//翻译成哈夫曼码

Code2String(BTNode<T> *t,char code[],int &i,int l)//从哈夫曼码译出原字符串

void AdjustDown(int r,int j);

void AdjustUp(int j);

bool IsEmpty() const

bool IsFull() const

void Append(const T &x);

void Serve(T &x);

operator T()const;

T getW();

void putW(const T& x);

void SetNull();

主要算法：

AdjustDown：向下调整q[r]。设tmp=q[r]，如果tmo大于左右孩子中的最小者，则与该结点交换，依次往下直到不需要调整或到达队列底部。

AdjustUp：该函数与AdjustDown相反，从下往上，与双亲结点比较，如果双亲结点大，则调整，知道双亲结点不再大或者已经到达顶部。

CreatHfmTree：首先构造n棵哈夫曼树对象，每棵树只有一个权值为w[i]的根节点，且该对象的weight为w[i]，将其逐一加入优先权队列。从优先权队列中取出两棵根节点值最小和次小的哈夫曼树x,y。以它们根的权值之和为根的权值，x,y为左右子树构造一棵新哈夫曼树，将新树对象进优先权队列。重复执行n-1次，此时队列中只剩下合并完成的哈夫曼树。从队列中取出构造完成的哈夫曼树，函数返回该哈夫曼树。

CreatCode：首先从根节点开始，每个节点增加项int hfm[]，bit，存储从根节点到该节点的路径，则子孩子的hfm就在双亲节点的hfm[]上增加一个，如果是左孩子则最后一位是0，右孩子就是1。然后递归遍历哈夫曼树，如果是叶子节点就输出其hfm[]。

String2Code：每个结点增加一个项ch存储对应的字幕，如果不是叶子就存’0’，依次比较输入的串的每一个字符，如果叶子节点有就输出该节点的hfm[]。

Code2String：依次读入哈夫曼码，如果是0就往左孩子走，如果是1就往右孩子走，直到走到叶子节点，输出字符。

code:

[cpp] view plain copy

//BTNode.h
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
using namespace std;
template <class T>
class BTree;
template <class T>
class BTNode
{
public:
BTNode()
{
lchild=rchild=parent=0;
ch='0';
}
BTNode(const T& e)
{
ch='0';
element=e;
lchild=rchild=parent=0;
memset(hfm,-1,sizeof(hfm));
}
BTNode(const T& e,const char c,BTNode<T> *l,BTNode<T> *r)
{
element=e;
ch=c;
lchild=l;
rchild=r;
parent=0;
memset(hfm,-1,sizeof(hfm));
}
T element;
char ch;
int hfm[50],bit;
BTNode<T> *lchild, *rchild,*parent;
friend class BTree<T>;
friend void Visit(BTNode<T>*p);
friend void Print(BTNode<T>*p);
friend void ex(BTNode<T>*p);
};
template <class T>
void Visit(BTNode<T>* p)
{
cout<<p->element<<" ";
}
template <class T>
void ex(BTNode<T>* p)
{
BTNode<T> *tmp;
tmp=p->lchild;
p->lchild=p->rchild;
p->rchild=tmp;
}

[cpp] view plain copy

//BTree.h
#include "BTNode.h"
#include<iostream>
using namespace std;
template<class T>
class BTree
{
public:
BTree(){root=NULL;i=-1;}
~BTree(){}
bool IsEmpty()const;
bool Root(T &x)const;
void MakeTree(const T &e ,const char c,BTree<T>& left,BTree<T>& right);
void BreakTree(T &e ,BTree<T>& left,BTree<T>& right);
int Size()
{
return Size(root);
}
int GetHeight()
{
return GetHeight(root);
}
void PreOrder(void (*Visit)(BTNode<T>* u))
{
PreOrder(Visit,root);
}
void InOrder(void (*Visit)(BTNode<T>* u))
{
InOrder(Visit,root);
}
void PostOrder(void (*Visit)(BTNode<T>* u))
{
PostOrder(Visit,root);
}
void BfsOrder(void (*Visit)(BTNode<T>* u))
{
BfsOrder(Visit,root);
}
void CreatCode()
{
CreatCode(root,i);
}
void PrintCode()
{
PrintCode(root);
}
void Character2Code(char ch)
{
Character2Code(root,ch);
}
void String2Code()
{
String2Code(root);
}
void Code2String()
{
Code2String(root);
}
void Exch()
{
Change(root);
}
void Clear()
{
Clear(root);
}
protected:
int i;
BTNode<T>* root;
private:
void PreOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);
void InOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);
void PostOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);
void BfsOrder(void (*Visit)(BTNode<T>* u), BTNode<T>*t);
void CreatCode(BTNode<T>* t,int i);
void PrintCode(BTNode<T>* t);
void Character2Code(BTNode<T>* t,char ch);
void String2Code(BTNode<T>* t);
void Code2String(BTNode<T>* t);
int Size(BTNode<T>* t);
int GetHeight(BTNode<T>* t);
void Change(BTNode<T> *t);
void Clear(BTNode<T> *t);
};
//二叉树的节点数
template <class T>
int BTree<T>::Size(BTNode<T>* t)
{
if(!t)
return 0;
else
return Size(t->lchild)+Size(t->rchild)+1;
}
//返回二叉树的高度
template<class T>
int BTree<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;
}
//判断二叉树是否为空
template <class T>
bool BTree<T>::IsEmpty() const
{
return root==NULL;
}
//根节点是否赋值
template <class T>
bool BTree<T>::Root(T &x) const
{
if (root)
{
x=root->element;
return true;
}
else return false;
}
//合并两棵二叉树
template <class T>
void BTree<T>::MakeTree(const T &e,const char c,BTree<T>& left,BTree<T>& right)
{
//cout<<"here in BTree<T>::MakeTree"<<endl;
int i=0;
if(root||&left==&right) return;
root=new BTNode<T>(e,c,left.root,right.root);
if(left.root!=right.root)
{
left.root->parent=root;
right.root->parent=root;
left.root->bit=0;
right.root->bit=1;
}
left.root=right.root=NULL;
}
//拆分一棵二叉树
template <class T>
void BTree<T>::BreakTree(T &e,BTree<T>&left, BTree<T>& right)
{
cout<<"here in BTree<T>::BreakTree."<<endl;
if(!root||&left==&right||left.root||right.root) return;
e=root.element; left.root=root.lchild; right.root=root.rchild;
delete root;
root=NULL;
}
//先序遍历二叉树
template <class T>
void BTree<T>::PreOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)
{
if(t)
{
Visit(t);
PreOrder(Visit,t->lchild);
PreOrder(Visit,t->rchild);
}
}
//中序遍历二叉树
template <class T>
void BTree<T>::InOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)
{
if (t)
{
InOrder(Visit,t->lchild);
Visit(t);
InOrder(Visit,t->rchild);
}
}
//后序遍历二叉树
template <class T>
void BTree<T>::PostOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)
{
if (t)
{
PostOrder(Visit,t->lchild);
PostOrder(Visit,t->rchild);
Visit(t);
}
}
//层次遍历即宽度优先遍历二叉树
template <class T>
void BTree<T>::BfsOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)//?t2?ê÷2?′?±éàú
{
int front=0,rear=0;
BTNode<T>* q[100];
q[rear++]=t;
while(front<rear)
{
BTNode<T>* u=q[front++];
if(!u) return;
Visit(u);
if(u->lchild) q[rear++]=u->lchild;
if(u->rchild) q[rear++]=u->rchild;
}
}
//生成哈夫曼编码
template <class T>
void BTree<T>::CreatCode(BTNode<T>* t,int i)
{
if(t)
{
if(t->parent)
{
for(int j=0;j<=i;j++)
t->hfm[j]=t->parent->hfm[j];
t->hfm[++i]=t->bit;
}
CreatCode(t->lchild,i);
CreatCode(t->rchild,i);
i--;
}
}
//遍历打印哈夫曼编码
template <class T>
void BTree<T>::PrintCode(BTNode<T>* t)
{
int i=0;
if(t)
{
if(!t->lchild&&!t->rchild)
{
cout<<"\t"<<t->ch<<":";
while(t->hfm[i]!=-1) cout<<t->hfm[i++];
cout<<endl;
}
PrintCode(t->lchild);
PrintCode(t->rchild);
}
}
//翻译单个字符的哈夫曼码
template <class T>
void BTree<T>::Character2Code(BTNode<T>* t,char ch)
{
int i=0;
if(t)
{
if(t->ch==ch)
{
while(t->hfm[i]!=-1) cout<<t->hfm[i++];
return;
}
Character2Code(t->lchild,ch);
Character2Code(t->rchild,ch);
}
}
//输入字符串并译成哈夫曼码
template <class T>
void BTree<T>::String2Code(BTNode<T>* t)
{
char s[100];
int len;
cout<<"输入由任意字符组成的串:";
cin>>s;
len=strlen(s);
cout<<"生成的哈夫曼码为:";
for(int i=0;i<len;i++)
Character2Code(root,s[i]);
cout<<endl;
}
//输入哈夫曼码并译成字符
template <class T>
void BTree<T>::Code2String(BTNode<T>* t)
{
char code;
BTNode<T> *tmp=t;
cout<<"输入哈夫曼码:";
while(cin>>code)
{
if(t->ch=='0')
{
if(code=='0') t=t->lchild;
else t=t->rchild;
}
else
{
cout<<t->ch;
t=tmp;
}
}
cout<<endl;
}
//镜像交换左右子树
template <class T>
void BTree<T>::Change(BTNode<T> *t)
{
if (t)
{
Change(t->lchild);
Change(t->rchild);
ex(t);
}
}
//清空这棵二叉树
template <class T>
void BTree<T>::Clear(BTNode<T> *t)
{
if(!t) return;
Clear(t->lchild);
Clear(t->rchild);
delete(t);
}