哈夫曼樹(Huffman樹)原理分析及實現(xiàn)

創(chuàng)新互聯(lián)是一家專業(yè)提供蒲城企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計、HTML5、小程序制作等業(yè)務(wù)。10年已為蒲城眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進行中。

1 構(gòu)造原理

假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。 n個權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：
　　(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；
　　(2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；
　　(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；
　　(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

顯然對n個權(quán)值，構(gòu)造哈夫曼樹樹需要合并n-1次，形成的樹結(jié)點總數(shù)為2n-1；

例如：A：60, B:45, C:13 D:69 E:14 F:5 G:3

第一步：找出字符中最小的兩個，小的在左邊，大的在右邊，組成二叉樹。

F和G最小，因此如圖，從字符串頻率計數(shù)中刪除F與G，并返回G與F的和 8給頻率表

重復(fù)第一步：

編碼規(guī)則：添加 0 和 1，規(guī)則左0 右1

2 代碼實現(xiàn)

根據(jù)哈夫曼樹的構(gòu)造原理，為方便實現(xiàn)，我們使用數(shù)組來存儲每個結(jié)點,其命名為Tree；

2.1 節(jié)點結(jié)構(gòu)

節(jié)點具有以下結(jié)構(gòu)：

//結(jié)點結(jié)構(gòu)
struct Node {
    int   val{0};           //節(jié)點的值
    Node* left{nullptr};    //節(jié)點的左孩子
    Node* right{nullptr};   //節(jié)點的右孩子
    Node* parent{nullptr};  //節(jié)點的父節(jié)點

    explicit Node(int value) : val(value) {}

    Node(int value, Node* pleft, Node* pRight, Node* pParent)
        : val(value), left(pleft), right(pRight), parent(pParent) {}
};

2.2 類的實現(xiàn)

Huffman.h

#include 
#include 
#include 
#include 

using namespace std;

struct Node {
    int   val{0};           //節(jié)點的值
    Node* left{nullptr};    //節(jié)點的左孩子
    Node* right{nullptr};   //節(jié)點的右孩子
    Node* parent{nullptr};  //節(jié)點的父節(jié)點

    explicit Node(int value) : val(value) {}

    Node(int value, Node* pleft, Node* pRight, Node* pParent)
        : val(value), left(pleft), right(pRight), parent(pParent) {}
};

class Compare  //比較類，用于構(gòu)造Node*類型的priority_queue
{
public:
    bool operator()(Node* a, Node* b) {
        return a->val > b->val;  //結(jié)點的值越小越靠前
    }
};

class HuffmanTree {
public:
    HuffmanTree();

    ~HuffmanTree();

    Node* Create();

    void PreOrder(Node* pNode);

    void InOrder(Node* pNode);

    void PostOrder(Node* pNode);

    void Encode(Node* pNode, string code);

private:
    Node* root;  // 哈夫曼樹頭

    priority_queue, Compare> nodes;

    void destroyTree(Node* pNode);
};

Hufman.cpp

#include "Huffman.h"

HuffmanTree::HuffmanTree() {
    // priority_queue沒有clear
    while (!nodes.empty()) nodes.pop();
    int a[] = {4, 3, 5, 8, 7, 9};
    int len = sizeof(a) / sizeof(a[0]);
    for (int i = 0; i < len; i++) { nodes.push(new Node(a[i])); }
    root = nullptr;
}

HuffmanTree::~HuffmanTree() {
    destroyTree(root);
}

void HuffmanTree::destroyTree(Node* pNode) {
    if (pNode == nullptr)
        return;
    destroyTree(pNode->left);
    destroyTree(pNode->right);
    delete pNode;
}

Node* HuffmanTree::Create() {
    while (nodes.size() > 1) {
        Node* p1 = nodes.top();
        nodes.pop();
        Node* p2 = nodes.top();
        nodes.pop();

        Node* cur  = new Node(p1->val + p2->val);
        cur->left  = p1;
        cur->right = p2;
        p1->parent = cur;
        p2->parent = cur;

        nodes.push(cur);
    }

    root = nodes.top();
    nodes.pop();

    return root;
}

void HuffmanTree::PreOrder(Node* pNode) {
    if (pNode == nullptr)
        return;
    cout << pNode->val << " ";
    PreOrder(pNode->left);
    PreOrder(pNode->right);
}

void HuffmanTree::InOrder(Node* pNode) {
    if (pNode == nullptr)
        return;
    InOrder(pNode->left);
    cout << pNode->val << " ";
    InOrder(pNode->right);
}

void HuffmanTree::PostOrder(Node* pNode) {
    if (pNode == nullptr)
        return;
    PostOrder(pNode->left);
    PostOrder(pNode->right);
    cout << pNode->val << " ";
}

void HuffmanTree::Encode(Node* pNode, string code) {
    //葉子節(jié)點的處理
    if (pNode->left == nullptr && pNode->right == nullptr)
        cout << pNode->val << " 被編碼為 " << code << endl;

    if (pNode->left) {
        //左子樹，編碼code添加'0'
        code += "0";
        Encode(pNode->left, code);
        //編碼code刪除'0'
        code.erase(code.end() - 1);
    }

    if (pNode->right) {
        //左子樹，編碼code添加'1'
        code += "1";
        Encode(pNode->right, code);
        //編碼code刪除'1'
        code.erase(code.end() - 1);
    }
}

3 測試代碼及輸出

int main() {
    HuffmanTree obj;
    Node*       root = obj.Create();
    cout << "先序遍歷: ";
    obj.PreOrder(root);
    cout << endl;

    cout << "中序遍歷: ";
    obj.InOrder(root);
    cout << endl;

    cout << "后序遍歷: ";
    obj.PostOrder(root);
    cout << endl;

    cout << "哈夫曼編碼: ";
    obj.Encode(root, "");

    return 0;
}

正確輸出：

4 參考資料

1.哈夫曼樹算法及C++實現(xiàn)
2.百度百科·哈夫曼樹
3.數(shù)據(jù)結(jié)構(gòu)：Huffman樹(哈夫曼樹)原理及C++實現(xiàn)