如何建立哈夫曼树的，网上搜索一堆，这里就不写了，直接给代码。
1.哈夫曼树结点类：HuffmanNode.h
|
1
2
3
4
5
6
7
8
9
10
|
#ifndef HuffmanNode_h#define HuffmanNode_h template <class T>struct HuffmanNode { T weight; // 存储权值 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左、右孩子和父结点}; #endif /* HuffmanNode_h */ |
2.哈夫曼树最小堆：HuffmanMinHeap.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
#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
|
1
2
3
4
5
6
7
8
9
10
11
|
#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
