C++实现哈夫曼树算法

如何建立哈夫曼树的，网上搜索一堆，这里就不写了，直接给代码。

1.哈夫曼树结点类：HuffmanNode.h

#ifndef HuffmanNode_h
#define HuffmanNode_h

template <class T>
struct HuffmanNode {
T weight; // 存储权值
HuffmanNode<T> *leftChild, *rightChild, *parent; // 左、右孩子和父结点
};

#endif /* HuffmanNode_h */

2.哈夫曼树最小堆：HuffmanMinHeap.h

#ifndef HuffmanMinHeap_h
#define HuffmanMinHeap_h

#include "HuffmanNode.h"
#include <iostream>
using namespace std;

const int DefaultSize = 100;

template <class T>
class MinHeap {
public:
MinHeap(); // 构造函数
~MinHeap(); // 析构函数
void Insert(HuffmanNode<T> *current); // 插入
HuffmanNode<T> *getMin(); // 获取最小结点
private:
HuffmanNode<T> *heap; // 动态数组存储最小堆
int CurrentSize; // 目前最小堆的结点数
void ShiftUp(int start); // 向上调整
void ShiftDown(int start, int m); // 下滑
};

// 构造函数
template <class T>
MinHeap<T>::MinHeap() {
heap = new HuffmanNode<T>[DefaultSize]; // 创建堆空间
CurrentSize = 0;
}

// 析构函数
template <class T>
MinHeap<T>::~MinHeap() {
delete []heap; // 释放空间
}

// 插入
template <class T>
void MinHeap<T>::Insert(HuffmanNode<T> *current) {
if(CurrentSize == DefaultSize) {
 cout << "堆已满" << endl;
 return;
}
// 把current的数据复制到“数组末尾”
heap[CurrentSize] = *current;
// 向上调整堆
ShiftUp(CurrentSize);
CurrentSize++;
}

// 获取最小结点并在堆中删除该结点
template <class T>
HuffmanNode<T> *MinHeap<T>::getMin() {
if(CurrentSize == 0) {
 cout << "堆已空!" << endl;
 return NULL;
}
HuffmanNode<T> *newNode = new HuffmanNode<T>();
if(newNode == NULL) {
 cerr << "存储空间分配失败！" << endl;
 exit(1);
}
*newNode = heap[0]; // 将最小结点的数据复制给newNode
heap[0] = heap[CurrentSize-1]; // 用最后一个元素填补
CurrentSize--;
ShiftDown(0, CurrentSize-1); // 从0位置开始向下调整
return newNode;
}

// 向上调整
template <class T>
void MinHeap<T>::ShiftUp(int start) {
// 从start开始，直到0或者当前值大于双亲结点的值时，调整堆
int j = start, i = (j-1)/2; // i是j的双亲

HuffmanNode<T> temp = heap[j];
while(j > 0) {
 if(heap[i].weight <= temp.weight)
  break;
 else {
  heap[j] = heap[i];
  j = i;
  i = (j - 1) / 2;
 }
}
heap[j] = temp;
}

// 向下调整
template <class T>
void MinHeap<T>::ShiftDown(int start, int m) {
int i = start, j = 2 * i + 1; // j是i的左子女

HuffmanNode<T> temp = heap[i];
while(j <= m) {
 if(j < m && heap[j].weight > heap[j+1].weight)
  j++; // 选两个子女中较小者
 if(temp.weight <= heap[j].weight)
  break;
 else {
  heap[i] = heap[j];
  i = j;
  j = 2 * j + 1;
 }
}
heap[i] = temp;
}

#endif /* HuffmanMinHeap_h */

3.哈夫曼树实现：HuffmanTree.h

#ifndef HuffmanTree_h
#define HuffmanTree_h

#include "HuffmanMinHeap.h"
#include "HuffmanNode.h"

template <class T>
class HuffmanTree {
public:
HuffmanTree(); // 构造函数
~HuffmanTree(); // 析构函数
void Create(T w[], int n); // 创建哈夫曼树
void Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent); // 合并
void PreOrder(); // 前序遍历Huffman树
private:
HuffmanNode<T> *root; // 根结点
void Destroy(HuffmanNode<T> *current); // 销毁哈夫曼树
void PreOrder(HuffmanNode<T> *current); // 前序遍历Huffman树
};

// 构造函数
template <class T>
HuffmanTree<T>::HuffmanTree() {
root = NULL;
}

// 析构函数
template <class T>
HuffmanTree<T>::~HuffmanTree() {
Destroy(root); // 销毁哈夫曼树
}

// 销毁哈夫曼树
template <class T>
void HuffmanTree<T>::Destroy(HuffmanNode<T> *current) {
if(current != NULL) { // 不为空
 Destroy(current->leftChild); // 递归销毁左子树
 Destroy(current->rightChild); // 递归销毁右子树
 delete current; // 释放空间
 current = NULL;
}
}

// 创建哈夫曼树
template <class T>
void HuffmanTree<T>::Create(T w[], int n) {
int i;
MinHeap<T> hp; // 使用最小堆存放森林
HuffmanNode<T> *first, *second, *parent = NULL;
HuffmanNode<T>*work = new HuffmanNode<T>();

if(work == NULL) {
 cerr << "存储空间分配失败！" << endl;
 exit(1);
}
for(i = 0; i < n; i++) {
 work->weight = w[i];
 work->leftChild = work->rightChild = work->parent = NULL;
 hp.Insert(work); // 插入到最小堆中
}
for(i=0; i < n-1; i++) { // 做n-1趟，形成Huffman树
 first = hp.getMin(); // 获取权值最小的树
 second = hp.getMin(); // 获取权值次小的树
 parent = new HuffmanNode<T>();
 if(parent == NULL) {
  cerr << "存储空间分配失败！" << endl;
  exit(1);
 }
 Merge(first, second, parent); // 合并
 hp.Insert(parent); // 重新插入到最小堆中
}
root = parent; // 根结点
}
// 合并
template <class T>
void HuffmanTree<T>::Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent) {
parent->leftChild = first; // 左子树
parent->rightChild = second; // 右子树
parent->weight = first->weight + second->weight; // 父结点权值
first->parent = second->parent = parent; // 父指针
}

// 前序遍历Huffman树
template <class T>
void HuffmanTree<T>::PreOrder() {
PreOrder(root);
}

// 前序遍历Huffman树
template <class T>
void HuffmanTree<T>::PreOrder(HuffmanNode<T> *current) {
if(current != NULL) {
 cout << current->weight << " "; // 访问当前结点数据
 PreOrder(current->leftChild); // 递归遍历左子树
 PreOrder(current->rightChild); // 递归遍历右子树
}
}
#endif /* HuffmanTree_h */

4.测试：main.cpp

#include "HuffmanTree.h"

int main(int argc, const char * argv[]) {
int arr[] = {7, 5, 2, 4};
int len = sizeof(arr) / sizeof(arr[0]); // 数组长度
HuffmanTree<int> tree; // Huffman树的对象

tree.Create(arr, len); // 创建Huffman树
tree.PreOrder(); // 前序遍历Huffman树
return 0;
}

测试结果：

来源：https://blog.csdn.net/chuanzhouxiao/article/details/88427411