Huffman(哈夫曼)樹的一些基本概念
1、1哈夫曼樹的定義
最簡哈夫曼樹是一種資料結構，是由德國數學家馮·哈夫曼發現的，又稱最優二叉樹，是一種帶權路徑長最短的樹。所以Huffman樹是一種二叉樹。
1、2哈夫曼樹的經典應用
哈夫曼樹最經典的應用時在通訊領域的哈夫曼編碼上面。經哈夫曼編碼的資訊消除了冗餘的資料，加提高了通訊通道的傳輸效率，目前，Huffman編碼計數還是資料壓縮的重要方法。關於Huffman編碼的具體介紹與實現，我覺得這篇文章寫的很相信，也很容易理解，感興趣的讀者也可以閱讀一下Huffman編碼的具體介紹與實現。
1、1關於路徑長度
路徑（path） 是樹中一個結點到另一個結點之間的分支構成該兩結點之間的路徑。路徑長度（path length）是指路徑上的分支條數。樹的路徑長度是樹的根節點到每一個結點的路徑長度之和。
根據樹的定義可以清楚的知道，從樹的根結點到達樹中每一結點有且僅有一條路徑。若設樹的根節點處於第一層，某一結點處於第k層，因為從根節點到達這個結點的路徑上的分支條數為k-1,所以有：從根節點到其他各節點的路徑長度等於該結點所處的層次k-1。
二叉樹中，如果想要樹的路徑長度（根節點到各結點的路徑長度之和）達到最小，那麼該二叉樹一定是完全二叉樹或者理想平衡二叉樹。
帶權路徑長度：在一棵樹中，如果其結點上附帶有一個權值，通常把該結點的路徑長度與該結點上的權值之積稱為該結點的帶權路徑長度（weighted path length）。樹的帶權路徑長度：如果樹中每個葉子上都帶有一個權值，則把樹中所有葉子的帶權路徑長度之和稱為樹的帶權路徑長度。設某二叉樹有n個帶權值的葉子結點，則該二叉樹的帶權路徑長度記為：
一般來說，用n（n>0）個帶權值的葉子來構造二叉樹，限定二叉樹中除了這n個葉子外只能出現度為2的結點。那麼符合這樣條件的二叉樹往往可構造出許多顆，其中帶權路徑長度最小的二叉樹就稱為哈夫曼樹或最優二叉樹。
2、Huffman樹的構造過程
為了構造權值集合為{w1, w2, ..., wn}的Huffman樹，Huffman提出了一個構造演算法，這個演算法稱之為Huffman樹。其基本思路為：
（1）根據跟定的n各權值{w1, w2, ..., wn}，構造具有n棵擴充二叉樹的森林F = {T1, T2, ...Tn}，其中每棵擴充二叉樹Ti只有一個權值wi的根節點，其左右子樹均為空。
（2）重複一下步驟，知道F中僅剩下一棵樹為止：
在F中選取兩棵根結點的權值最小的擴充二叉樹，作為左、右子樹構造義一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。
在F中刪去這兩棵二叉樹。
把新的二叉樹加入F。
例如，設給定的權值集合為{7， 5， 2， 4}，構造Huffman樹的過程下圖所示。首先構造每棵樹只有一個結點的森林，參看圖(a)；然後每次選擇兩個根結點權值最小的擴充二叉樹，以他們的左、右子樹構造新的擴充二叉樹，步驟參看(b)，(c)，（d），最後得到一棵擴充二叉樹。
因為在構建Huffman樹的時候需要刪去最小權值的樹，插入新樹的過程，這個過程與最小堆的作用是一致的，利用最小堆可以方便的實現Huffman樹的構造，大家如果對最小堆的概念及實現過程感興趣的話可以看我的上一篇文章資料結構在之-最小堆的生成演算法(下滑調整與上滑調整採用遞迴演算法) 。
3、Huffman樹實現原始碼
3、1 HuffmanTree.h檔案
#pragma once
#include"MinHeap.h"
//最小堆的應用之一：構建漢夫曼樹
//哈夫曼樹結點
template<class T>
struct HuffmanNode
{
T m_tData; //資料域
HuffmanNode<T>* m_ptLChild; //指向左孩子的指標
HuffmanNode<T>* m_ptRChild; //指向右孩子的指標
HuffmanNode<T>* m_ptParent; //指向父節點的指標
//預設建構函式
HuffmanNode() :m_ptLChild(nullptr), m_ptRChild(nullptr), m_ptParent(nullptr) {}
//建構函式
HuffmanNode(const T& data, HuffmanNode<T>* lc = nullptr,
HuffmanNode<T>* rc = nullptr, HuffmanNode<T>* p = nullptr) {
m_tData = data;
m_ptLChild = lc;
m_ptRChild = rc;
m_ptParent = p;
}
HuffmanNode(const HuffmanNode<T>& node) {
this->m_tData = node.m_tData;
this->m_ptParent = node.m_ptParent;
this->m_ptLChild = node.m_ptLChild;
this->m_ptRChild = node.m_ptRChild;
//判大小過載，在構建哈夫曼樹的時候需要用到最小堆，最小堆的建立需要判斷大小
bool operator >(const HuffmanNode<T>& node) { return this->m_tData > node.m_tData; }
bool operator <= (const HuffmanNode<T>& node) { return this->m_tData <= node.m_tData; }
};
class HuffmanTree
public:
HuffmanTree(const T arr[], const int size); //建構函式
HuffmanTree() { m_ptRoot = nullptr; } //預設建構函式
~HuffmanTree() { DeleteTree(m_ptRoot); } //解構函式
void Display() { Display(m_ptRoot); } //輸出漢夫曼樹
private:
HuffmanNode<T>* m_ptRoot; //哈夫曼樹的根節點
//合併樹
void MergeTree(HuffmanNode<T>& lc, HuffmanNode<T>& rc, HuffmanNode<T>* &p);
void Display(HuffmanNode<T>* root); //輸出漢夫曼樹
//哈夫曼的函式建構函式
//利用權值為arr[0]-arr[size - 1]來構造二叉樹
HuffmanTree<T>::HuffmanTree(const T arr[], const int size){
//宣告一個最小堆物件
MinHeap<HuffmanNode<T>> minHeap;
//依次為最小、次小、父節點
HuffmanNode<T>*first, *second, *parent = nullptr;
//先將陣列裝入最小堆中
for (int i = 0; i < size; i++) {
HuffmanNode<T>* tmp = new HuffmanNode<T>(arr[i]);
minHeap.Insert(*tmp);
//進行size - 1次迴圈就可以構建哈夫曼樹
for (int i = 0; i < size - 1; i++) {
first = new HuffmanNode<T>(); //一定要在堆中申請記憶體，臨時變數是不行的
second = new HuffmanNode<T>(); //臨時變數的話在這個函式退出之後，只能找到頂點了
minHeap.RemoveMin(*first); //從最小堆中取出最小結點,從這裡可以看書，要定義複製建構函式！！！！！
minHeap.RemoveMin(*second); //從最小堆中再取出次小的結點
MergeTree(*first, *second, parent);
minHeap.Insert(*parent);
m_ptRoot = parent; //將根節點指向最終樹的源點
void HuffmanTree<T>::DeleteTree(HuffmanNode<T>* ptroot) {
if (ptroot != nullptr) {
DeleteTree(ptroot->m_ptLChild);
DeleteTree(ptroot->m_ptRChild);
delete ptroot;
void HuffmanTree<T>::MergeTree(HuffmanNode<T>& lc, HuffmanNode<T>& rc, HuffmanNode<T>* &parent) {
parent = new HuffmanNode<T>(); //為父結點分配記憶體
//parent新樹左右指標指向引數中的左子樹與右子樹，值為兩個子樹的值之和
parent->m_ptLChild = &lc;
parent->m_ptRChild = &rc;
parent->m_tData = lc.m_tData + rc.m_tData;
//兩個子樹父節點指向引數中的parent新樹
lc.m_ptParent = parent;
rc.m_ptParent = parent;
//輸出漢夫曼樹
void HuffmanTree<T>::Display(HuffmanNode<T>* root) {
//前序遍歷輸出
if (root != nullptr) {
std::cout << root->m_tData << "\t"; //輸出頂點值
Display(root->m_ptLChild); //遞迴呼叫，輸出右孩子
Display(root->m_ptRChild); //遞迴呼叫，輸出左孩子
3、2 main.cpp檔案
//#include"MinHeap.h"
#include"HuffmanTree.h"
#include<iostream>
using namespace std;
int main() {
float arr[] = { 1.2, 3.5, 6.0, 2.2, 4.1, 20.4 };
HuffmanTree<float> hf(arr, 6);
hf.Display();
return 0;
3、3 結果顯示
Huffman(哈夫曼)樹的一些基本概念
1、1哈夫曼樹的定義
最簡哈夫曼樹是一種資料結構，是由德國數學家馮·哈夫曼發現的，又稱最優二叉樹，是一種帶權路徑長最短的樹。所以Huffman樹是一種二叉樹。
1、2哈夫曼樹的經典應用
哈夫曼樹最經典的應用時在通訊領域的哈夫曼編碼上面。經哈夫曼編碼的資訊消除了冗餘的資料，加提高了通訊通道的傳輸效率，目前，Huffman編碼計數還是資料壓縮的重要方法。關於Huffman編碼的具體介紹與實現，我覺得這篇文章寫的很相信，也很容易理解，感興趣的讀者也可以閱讀一下Huffman編碼的具體介紹與實現。
1、1關於路徑長度
路徑（path） 是樹中一個結點到另一個結點之間的分支構成該兩結點之間的路徑。路徑長度（path length）是指路徑上的分支條數。樹的路徑長度是樹的根節點到每一個結點的路徑長度之和。
根據樹的定義可以清楚的知道，從樹的根結點到達樹中每一結點有且僅有一條路徑。若設樹的根節點處於第一層，某一結點處於第k層，因為從根節點到達這個結點的路徑上的分支條數為k-1,所以有：從根節點到其他各節點的路徑長度等於該結點所處的層次k-1。
二叉樹中，如果想要樹的路徑長度（根節點到各結點的路徑長度之和）達到最小，那麼該二叉樹一定是完全二叉樹或者理想平衡二叉樹。
帶權路徑長度：在一棵樹中，如果其結點上附帶有一個權值，通常把該結點的路徑長度與該結點上的權值之積稱為該結點的帶權路徑長度（weighted path length）。樹的帶權路徑長度：如果樹中每個葉子上都帶有一個權值，則把樹中所有葉子的帶權路徑長度之和稱為樹的帶權路徑長度。設某二叉樹有n個帶權值的葉子結點，則該二叉樹的帶權路徑長度記為：
一般來說，用n（n>0）個帶權值的葉子來構造二叉樹，限定二叉樹中除了這n個葉子外只能出現度為2的結點。那麼符合這樣條件的二叉樹往往可構造出許多顆，其中帶權路徑長度最小的二叉樹就稱為哈夫曼樹或最優二叉樹。
2、Huffman樹的構造過程
為了構造權值集合為{w1, w2, ..., wn}的Huffman樹，Huffman提出了一個構造演算法，這個演算法稱之為Huffman樹。其基本思路為：
（1）根據跟定的n各權值{w1, w2, ..., wn}，構造具有n棵擴充二叉樹的森林F = {T1, T2, ...Tn}，其中每棵擴充二叉樹Ti只有一個權值wi的根節點，其左右子樹均為空。
（2）重複一下步驟，知道F中僅剩下一棵樹為止：
在F中選取兩棵根結點的權值最小的擴充二叉樹，作為左、右子樹構造義一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。
在F中刪去這兩棵二叉樹。
把新的二叉樹加入F。
例如，設給定的權值集合為{7， 5， 2， 4}，構造Huffman樹的過程下圖所示。首先構造每棵樹只有一個結點的森林，參看圖(a)；然後每次選擇兩個根結點權值最小的擴充二叉樹，以他們的左、右子樹構造新的擴充二叉樹，步驟參看(b)，(c)，（d），最後得到一棵擴充二叉樹。
因為在構建Huffman樹的時候需要刪去最小權值的樹，插入新樹的過程，這個過程與最小堆的作用是一致的，利用最小堆可以方便的實現Huffman樹的構造，大家如果對最小堆的概念及實現過程感興趣的話可以看我的上一篇文章資料結構在之-最小堆的生成演算法(下滑調整與上滑調整採用遞迴演算法) 。
3、Huffman樹實現原始碼
3、1 HuffmanTree.h檔案
#pragma once
#include"MinHeap.h"
//最小堆的應用之一：構建漢夫曼樹
//哈夫曼樹結點
template<class T>
struct HuffmanNode
{
T m_tData; //資料域
HuffmanNode<T>* m_ptLChild; //指向左孩子的指標
HuffmanNode<T>* m_ptRChild; //指向右孩子的指標
HuffmanNode<T>* m_ptParent; //指向父節點的指標
//預設建構函式
HuffmanNode() :m_ptLChild(nullptr), m_ptRChild(nullptr), m_ptParent(nullptr) {}
//建構函式
HuffmanNode(const T& data, HuffmanNode<T>* lc = nullptr,
HuffmanNode<T>* rc = nullptr, HuffmanNode<T>* p = nullptr) {
m_tData = data;
m_ptLChild = lc;
m_ptRChild = rc;
m_ptParent = p;
}
HuffmanNode(const HuffmanNode<T>& node) {
this->m_tData = node.m_tData;
this->m_ptParent = node.m_ptParent;
this->m_ptLChild = node.m_ptLChild;
this->m_ptRChild = node.m_ptRChild;
}
//判大小過載，在構建哈夫曼樹的時候需要用到最小堆，最小堆的建立需要判斷大小
bool operator >(const HuffmanNode<T>& node) { return this->m_tData > node.m_tData; }
bool operator <= (const HuffmanNode<T>& node) { return this->m_tData <= node.m_tData; }
};
template<class T>
class HuffmanTree
{
public:
HuffmanTree(const T arr[], const int size); //建構函式
HuffmanTree() { m_ptRoot = nullptr; } //預設建構函式
~HuffmanTree() { DeleteTree(m_ptRoot); } //解構函式
void Display() { Display(m_ptRoot); } //輸出漢夫曼樹
private:
HuffmanNode<T>* m_ptRoot; //哈夫曼樹的根節點
//合併樹
void MergeTree(HuffmanNode<T>& lc, HuffmanNode<T>& rc, HuffmanNode<T>* &p);
void Display(HuffmanNode<T>* root); //輸出漢夫曼樹
};
//哈夫曼的函式建構函式
//利用權值為arr[0]-arr[size - 1]來構造二叉樹
template<class T>
HuffmanTree<T>::HuffmanTree(const T arr[], const int size){
//宣告一個最小堆物件
MinHeap<HuffmanNode<T>> minHeap;
//依次為最小、次小、父節點
HuffmanNode<T>*first, *second, *parent = nullptr;
//先將陣列裝入最小堆中
for (int i = 0; i < size; i++) {
HuffmanNode<T>* tmp = new HuffmanNode<T>(arr[i]);
minHeap.Insert(*tmp);
}
//進行size - 1次迴圈就可以構建哈夫曼樹
for (int i = 0; i < size - 1; i++) {
first = new HuffmanNode<T>(); //一定要在堆中申請記憶體，臨時變數是不行的
second = new HuffmanNode<T>(); //臨時變數的話在這個函式退出之後，只能找到頂點了
minHeap.RemoveMin(*first); //從最小堆中取出最小結點,從這裡可以看書，要定義複製建構函式！！！！！
minHeap.RemoveMin(*second); //從最小堆中再取出次小的結點
MergeTree(*first, *second, parent);
minHeap.Insert(*parent);
}
m_ptRoot = parent; //將根節點指向最終樹的源點
}
template<class T>
void HuffmanTree<T>::DeleteTree(HuffmanNode<T>* ptroot) {
if (ptroot != nullptr) {
DeleteTree(ptroot->m_ptLChild);
DeleteTree(ptroot->m_ptRChild);
delete ptroot;
}
}
//合併樹
template<class T>
void HuffmanTree<T>::MergeTree(HuffmanNode<T>& lc, HuffmanNode<T>& rc, HuffmanNode<T>* &parent) {
parent = new HuffmanNode<T>(); //為父結點分配記憶體
//parent新樹左右指標指向引數中的左子樹與右子樹，值為兩個子樹的值之和
parent->m_ptLChild = &lc;
parent->m_ptRChild = &rc;
parent->m_tData = lc.m_tData + rc.m_tData;
//兩個子樹父節點指向引數中的parent新樹
lc.m_ptParent = parent;
rc.m_ptParent = parent;
}
//輸出漢夫曼樹
template<class T>
void HuffmanTree<T>::Display(HuffmanNode<T>* root) {
//前序遍歷輸出
if (root != nullptr) {
std::cout << root->m_tData << "\t"; //輸出頂點值
Display(root->m_ptLChild); //遞迴呼叫，輸出右孩子
Display(root->m_ptRChild); //遞迴呼叫，輸出左孩子
}
}
3、2 main.cpp檔案
//#include"MinHeap.h"
#include"HuffmanTree.h"
#include<iostream>
using namespace std;
int main() {
float arr[] = { 1.2, 3.5, 6.0, 2.2, 4.1, 20.4 };
HuffmanTree<float> hf(arr, 6);
hf.Display();
return 0;
}
3、3 結果顯示