0
0
0
1. 云栖社区>
2. 博客>
3. 正文

# 1 基本概念

①根据给定的n个权值，构成n棵二叉树的集合F，其中每棵树中只有一个带有权值的根结点，其左右子树均为空树。

②在F中选取两棵根结点的权值最小的树，并以它们作为左右子树构造一棵新的二叉树，且置新的二叉树根结点的权值为其左、右子树上根结点的权值之和。

③在F中删除这两棵树，同时将新得到的二叉树加入F中。

# 2 赫夫曼树实现

```struct HTnode
{
char ch;
int weight,parent,lchild,rchild;
};```
HuffmanTree类声明如下：
```#pragma once
#define MAXSIZE 1000
#include "HTnode.h"
#include <windows.h>
class HuffmanTree
{
friend class HuffmanCoder;
public:
HuffmanTree(int n,char chA[],int weightA[]):m_HTsize(0),m_HT(NULL)
{
_Create(n,chA,weightA);
}

~HuffmanTree()
{
delete [] m_HT;
}

void Display();
private:
int m_HTsize; //树叶结点个数
HTnode* m_HT;
void _Create(int,char chA[],int weightA[]);
int _MinVal(const int&);
void _Select(const int,int&,int&);
};```
HuffmanTree类实现如下：
```#include "HuffmanTree.h"
#include <iostream>
using namespace std;

void HuffmanTree::_Create(int n,char chA[],int weightA[])
{
int i, s1, s2;
m_HTsize = 2 * n - 1;
m_HT = new HTnode[2 * n - 1];
if (n <= 1)
{
return;
}
for (i = 0; i < n; i++)
{
m_HT[i].ch = chA[i];
m_HT[i].weight = weightA[i];
m_HT[i].parent = -1;
m_HT[i].lchild = -1;
m_HT[i].rchild = -1;
}
while(i < m_HTsize)
{
_Select(i,s1,s2);
m_HT[s1].parent = m_HT[s2].parent = i;
m_HT[i].lchild = s1;
m_HT[i].rchild = s2;
m_HT[i].weight = m_HT[s1].weight + m_HT[s2].weight;
m_HT[i].parent = -1;
i++;
}
}

void HuffmanTree::Display()
{
int i;
std::cout<<"所建立的赫夫曼树的静态链表表示如下："<<std::endl;
std::cout<<"位置\t"<<"字符\t"<<"权值\t"<<"双亲\t"<<"左孩子\t"<<"右孩子"<<endl;
for (i = 0; i < (m_HTsize + 1) / 2; i++)
{
cout<<i<<"\t"<<m_HT[i].ch<<"\t"<<m_HT[i].weight<<"\t"<<m_HT[i].parent
<<"\t"<<m_HT[i].lchild<<"\t"<<m_HT[i].rchild<<endl;
}
while (i < m_HTsize)
{
cout<<i<<"\t\t"<<m_HT[i].weight<<"\t"<<m_HT[i].parent<<"\t"<<m_HT[i].lchild
<<"\t"<<m_HT[i].rchild<<endl;
i++;
}
}

//从前i个结点中选择parent为-1且weight最小的结点，获取其序号
int HuffmanTree::_MinVal(const int& i)
{
int j, k, min = MAXSIZE;
for (j = 0; j < i; j++)
{
if (m_HT[j].parent == -1 && m_HT[j].weight < min)
{
min = m_HT[i].weight;
k = j;
}
}
m_HT[k].parent = MAXSIZE;
return k;
}

void HuffmanTree::_Select(const int i,int& s1,int& s2)
{
int s;
s1 = _MinVal(i);
s2 = _MinVal(i);
if (s1 > s2)
{
s = s1;
s1 = s2;
s2 = s;
}
}```

# 3 赫夫曼树编码

```//赫夫曼编码表结点结构
struct HCnode
{
char ch;
char* pstring;
};```

```//HuffmanCoder.h
#pragma once
#include "HCnode.h"
#include "HuffmanTree.h"
class HuffmanCoder
{
public:
HuffmanCoder(const int& n)
{
m_HC = new HCnode[n];
m_HCsize = n;
}

~HuffmanCoder()
{
for (int i = 0; i < m_HCsize; i++)
{
delete [] m_HC[i].pstring;
}
delete [] m_HC;
}

void CreateBook(HuffmanTree&);
void Coder(char ch[]);
void Decoder(HuffmanTree&);
private:
HCnode* m_HC; //赫夫曼编码表基地址指针
int m_HCsize; //外结点个数
};```
```//HuffmanCoder.cpp
#include "HuffmanCoder.h"
#include <iostream>
#include <fstream>
using namespace std;
void HuffmanCoder::CreateBook(HuffmanTree& ht)
{
int i,j,c,f,start;
char* cd = new char[m_HCsize];
cd[m_HCsize-1] = '\0';
cout<<"以下是各字符的赫夫曼编码："<<endl;
for (i = 0; i < m_HCsize; i++)
{
start = m_HCsize - 1;
m_HC[i].ch = ht.m_HT[i].ch;
for (c = i, f = ht.m_HT[i].parent; f !=-1; c = f, f = ht.m_HT[f].parent)
{
if (ht.m_HT[f].lchild == c)
{
cd[--start] = '0';
}
else
{
cd[--start] = '1';
}
}

m_HC[i].pstring = new char[m_HCsize-start];
cout<<"第"<<i<<"个字符"<<ht.m_HT[i].ch<<"的编码是：";
for (j = start; j < m_HCsize; j++)
{
cout<<cd[j];
m_HC[i].pstring[j-start] = cd[j];
}
cout<<endl;
}
}

//对用字符串组成的电文用赫夫曼编码表进行编码
void HuffmanCoder::Coder(char ch[])
{
ofstream outfile("f1.dat",ios::out);
for (int i = 0; i < strlen(ch); i++)
{
for (int j = 0; j < m_HCsize; j++)
{
if (m_HC[j].ch == ch[i])
{
for (int k = 0; m_HC[j].pstring[k];k++)
{
cout<<m_HC[j].pstring[k];
outfile.put(m_HC[j].pstring[k]);
}
break;
}
}
}
cout<<endl;
outfile.close(); //关闭数据文件
}

//对用0,1组成的电文用赫夫曼树进行译码
void HuffmanCoder::Decoder(HuffmanTree& ht)
{
char ch[256];
int j = 0, i = 0, p, pre, root = ht.m_HTsize - 1;
ifstream infile("f1.dat",ios::in);
while (infile.get(ch[j]))
{
j++;
}
ch[j] = 0;
cout<<"需译制的二进制电文是："<<endl;
cout<<ch<<endl;
cout<<"译码结果："<<endl;
pre = -1;
p = root;
while (i < strlen(ch))
{
while(p != -1)
{
if (ch[i] == '0')
{
pre = p;
p = ht.m_HT[p].lchild;
}
else
{
pre = p;
p = ht.m_HT[p].rchild;
}
i++;
}
cout<<ht.m_HT[pre].ch;
i--;
pre = -1;
p = root;
}
cout<<endl;
infile.close();
}```

```//main.cpp
#include <iostream>
#include <fstream>
#include "HuffmanCoder.h"
using namespace std;

void main(int argc, char* argv[])
{
ifstream cin("input.txt");
int n;
cout<<"---此程序实现建立赫夫曼树并求赫夫曼编码---"<<endl<<endl;
cout<<"请输入树叶结点的个数(n>1)：";
cin>>n;
char chA[256];
int WeightA[256];

for (int i = 0; i < n; i++)
{
cout<<"请输入第"<<i<<"个字符及其权值"<<endl;
cin>>chA[i]>>WeightA[i];
}
HuffmanTree ht(n,chA,WeightA);
ht.Display();

HuffmanCoder hc(n);
hc.CreateBook(ht);
cout<<"请输入需编码的字符串（字符串中的字符必须是当前对象中的字符）："<<endl;
cin>>chA;
cout<<"编码结果"<<endl;
hc.Coder(chA);
cout<<endl;
hc.Decoder(ht);
cout<<endl;
system("pause");
}```

+ 关注