这个程序设计了5个类，分别是
队列结点类（ class QueueNode ），因为该队列将来会用来存储树的结点 ，因此将队列设计成模板（template ），可以存储任何自定义的数据类型，用队列输入输出时只需要对输入输出进行重载 就能输出结点里的数据。
classQueueNode //自定义结点类型（队列结点）
{
private:
T data;
QueueNode *next;
public:
void setData(T data) {
this->data = data;
}
void setNext(QueueNode* p) {
this->next = p;
}
T& getData() {
return this->data;
}
QueueNode*& getNext()
{
return this->next;
}
};
该结点就是树的结点类型，由于队列结点是存储数据 ，因此可以设计一个队列类，用来实现队列的一些基本功能 ，
队列类（ class
priorityQueue ），基本的的操作也就是出队和入队 ，在入队这一块，由于将来的哈夫曼树的构造需要一直从结点中找到权值最小的结点，而队列的出队是只能从最顶端出队，因此入队的时候需要对结点排序 ，权值最小的放到最上层，出队时直接拿来用就行。
classpriorityQueue
{
public:
priorityQueue(); //构造函数初始化数据
void insertQueue(T e); //拥有入队排序的功能
T pop(); //出队，出队的同时删除队列的顶端结点
int getNumOfQueue() {
return num; //返回结点数量
}
void print() { //打印显示
QueueNode *p;
p = this->front; // p指向头节点
if (this->front == this->rear) //先判断队列是否为空
{
cout << "当前队列为NULL" << endl;
return;
}
cout << "当前队列的数据为：" << endl;
while (p != this->rear)
{
cout <getNext()->getData() << "\t"<<(p->getNext()->getData()).getWeight()<< endl;
p = p->getNext();
}
cout << endl;
}
protected:
QueueNode* front; //顶端指针存储最顶端结点的地址
QueueNode* rear; //底端指针存储最低端结点的地址
int num; //结点的数量
};
其中所包含的几种算法如下：
priorityQueue::priorityQueue() //实现优先排序
{
num = 0; //初始化结点的数量为0
front = rear = new QueueNode; //类似于链表的头节点，其地址初始由顶端和低端指针存储
rear->setNext(NULL); //头结点的next指针指向为NULL
}
voidpriorityQueue::insertQueue(T e) //入队排序函数
{
num++; //结点的数量增加
QueueNode *p = new QueueNode,*temp = front->getNext(), *pre = front;
//p为新结点申请存储空间 temp和pre分别是两个连续的指针，即pre的next存放的地点永远有temp接收
p->setData(e); //往新结点里存储数据
/*如果队列为空不进行循环，将新结点直接插入头结点的后面
如果队列不为NULL，但是新设置的结点数据较小需要插入到队列里需要进行while循环*/
while (temp && temp->getData()
pre = temp; //pre在前所以将来p（新结点）将插入在其后面
temp = temp->getNext(); //temp在后所以将来p（新结点）将插入在其前面
}
p->setNext(temp); //新结点的next存放temp，即实现了p（新结点）插入temp之前
pre->setNext(p);
while (temp) { //循环到最低端的结点
pre = temp;
temp = temp->getNext();
}
this->rear = pre; //最低端存储指针存放最低端的结点地址
}
TpriorityQueue::pop() //出队
{
num--; //结点的数量少1
T e = front->getNext()->getData();
QueueNode* p = front->getNext(); //找到队列顶端结点
front->setNext(p->getNext()); //顶端指针下移
delete p; //释放空间原先的顶端结点
return e;
}
其次就是哈夫曼树的类 ：
树的结点类（class HfmNode ），和队列一样，需要先设计一个树的结点类，用于存储数据 ，在这包括树的左右孩子指针，和储存的字符变量，还有权值（在这里权值指的是字符出现的次数）。
classHfmNode
{
private:
char Date; //树中的数据
int weight; //结点的权值
HfmNode*lchild, *rchild;
public:
void setDate(char c) { //设置 树中数据
this->Date = c;M
}
void setWeight(int weight) { //设置 权值
this->weight = weight;
}
void setLchild(HfmNode* p) { //设置 左孩子
this->lchild = p;
}
void setRchild(HfmNode *p) { //设置 右孩子
this->rchild = p;
}
int getWeight() { //获得权值的大小
return weight;
}
char& getData() { //获得结点的数据
return this->Date;
}
HfmNode*& getLchild() { //获得左孩子地址
return this->lchild;
}
HfmNode*& getRchild() { //获得右孩子地址
return this->rchild;
}
//运算符重载来实现权值大小的比较
friend bool operator < (HfmNode &obj1,HfmNode obj2)
{
return obj1.weight < obj2.weight;
}
//重载输入输出函数
friend ostream&operator<<(ostream& out, HfmNode& obj)
{
out << obj.Date <<"\t";
return out;
}
friend istream&operator>>(istream& in, HfmNode& obj)
{
in >> obj.Date;
return in;
}
}
树的类（ class ht_Tree ），用于构造哈夫曼树，实现基本的树的功能
在构造哈夫曼树的函数里，传参数是一段任意的字符串，首先对字符串进行权值的计算，然后这些字符不停的入队，入队完成后就是核心部分——出队，构造父节点，再入队，一直循环， 哈夫曼树就构造完成。
class ht_Tree //在该类可以存储树结点的数据类型
{
private:
HfmNode* forest[MAXSIZE];
private:
HfmNode* root;//树的根
intlengh;//结点的数量
public:
ht_Tree(){
this->lengh= 0;//初始化树的结点的数量为NULL
this->root= NULL;//初始化根节点为NULL
}
HfmNode*getRoot() //根结点的获取
{
returnthis->root;
}
//创建树
HfmNode*buildTree(const char* str) {
intt = 0;
inti, j, sign = 0, count = 0;
intpriority[MAXSIZE] = { 0 }; //用于存放计算好的权值
priorityQueue que; //创建一个队列对象，用于将树结点入队
HfmNode*temp = NULL, *ltemp = NULL, *rtemp = NULL;
//统计权值的同时将结点入队
for(i = 0; i < MAXSIZE; i++) { //将所有的ASSIC值和字符串的每个字符进行比较
for(j = 0; str[j] != '\0'; j++) {
if(i == str[j]) {
sign= 1;
count++;//权值增加
}
}
if(sign == 1) {
temp= new HfmNode; //申请一个树结点
temp->setDate(i); //设置数据
temp->setWeight(count); //设置权值
priority[t++]= count;
temp->setLchild(NULL);
temp->setRchild(NULL);
sign= 0;
que.insertQueue(*temp);
count= 0;
j= 0;
}
}
que.print(); //用于测试
while(que.getNumOfQueue() > 1) { //不停的出队形成父节点，然后父节点入队
temp= new HfmNode; //申请父节点
ltemp= new HfmNode; //申请左孩子
rtemp= new HfmNode; //申请右孩子
//出队权值最小的两个结点给临时的左右孩子
*ltemp= que.pop();
*rtemp= que.pop();
//设置父节点的权值 左孩子和右孩子
temp->setWeight(ltemp->getWeight()+ rtemp->getWeight());
temp->setLchild(ltemp);
temp->setRchild(rtemp);
//父节点入队
que.insertQueue(*temp);
}
temp= new HfmNode;//申请根结点
*temp= que.pop();//
returntemp;//返回根节点
}
};
下面就是编码的部分，因此设计了编码类。
编码类（ class codeNode ），思路借用课本中的，即左孩子不为空 路径写1，右孩子为不为空路径写0 ，这一部分用递归 实现，存储后也利用队列模板进行入队 ，输出编码时只需要出队就行。
//字符编码类
class codeNode
{
private:
char key;
charcode[MAXSIZE];//保存字符编码
public:
//实现原理递归的使用
voidencode(HfmNode *tree, char *code, int i, priorityQueue &table)
{ //如果递归到左孩子和右孩子都为NULL则将字符编码
if(!tree->getLchild() && !tree->getRchild()) {
code[i]= '\0';
codeNode*temp = new codeNode; //创建编码对象来保存每个叶子结点的编码
temp->key= tree->getData(); //将该叶子结点保存的字符给编码类里的字符
strcpy(temp->code,code);
//为了能够实现一个字符对应一个编码，利用队列里存储将该结点逐个入队
table.insertQueue(*temp);//将编码入队
}
else {
//递归左孩子写编码
if(tree->getLchild()) {
code[i]= '0'; //如果左孩子不为NULL则路径设置为字符‘0’
encode(tree->getLchild(),code, i + 1, table);
}
//递归右孩子写编码
if(tree->getRchild()) {
code[i]= '1'; //如果右孩子不为NULL则路径设置为字符‘1’
encode(tree->getRchild(),code, i + 1, table);
}
}
}
//通过不停的出队进行打印字符以及对应的编码
voidprintfTable(priorityQueue table)
{
while(table.getNumOfQueue() != 0) { //如果队列里的数据不为0，则继续出队，进行循环
codeNodetemp = table.pop(); //出队
cout<< temp.key << ':' << temp.code << endl;
}
}
//根据编码找出所代表的字符 实现原理（递归）
voiddecode(HfmNode* tree, char* str, int i)
{
if ('0' ==str[i]) //对应的字符为0 则递归左孩子
decode(tree->getLchild(),str, i + 1);
if ('1' ==str[i]) //对应的字符为1，则递归右孩子
decode(tree->getRchild(),str, i + 1);
if(!str[i]) //最终无字符则输出最终的孩子所对应的数据
cout<< tree->getData();
}
friend booloperator < (codeNode a, codeNode b)
{
returntrue;
}
};
