哈夫曼树算法的原理与实现

本来这篇文章应该在5月的时候写完的，但是由于这几个月都有些事情断断续续地打断我写文章。现在废话不多说直接进入主题，哈夫曼树其实并不是想象中那么难，如果是只看它的介绍的话你会觉得完全不知道这是一颗怎样的树。它只不过是队列和树的结合使用罢了，大概就是先按权重排序，然后压入队列，再两两抽入结合成新的树，再压入队列。这里的列队要优先列队才行，因为只有优先列队才满足先进先出的特点，这样我们就能很方便地每次取出权重最小的2个元素。只要我们不断地重复这个过程，就能实现一颗哈夫曼树。

可能看到这里，你会发现我并没有说明哈夫曼树的作用。那什么是哈夫曼树呢？哈夫曼树就是一颗以权重排列树结点的树，这样的树还叫最优二叉树。从它的第二个名称“最优二叉树”就能知道，这种树的效率是最优的。因为我们要实现的是权重高的结点可以用最短的路径访问，权重低的结点会被放在最下层的地方，所以这样可以大大地提升访问的效率。

主要原理就是：

下面是实现的代码：

[友情提示]
建议先看完上面的实现原理，再看下面的实现代码。其实看懂了原理就能写代码，不需要看我坑爹逻辑写的代码。如果你看懂了原理，但真的不会写代码，请往下看。

Base.h 算法的通用头文件，这个文件主要声明列队和树所要使用的结点结构体。因为考虑通用性的问题，所以我用一个结构体做了两种数据结构都通用的结点。

#pragma once
#ifndef _Base_H_
#define _Base_H_

struct Node{
    int Index;
    char Data;
    Node *pNext;

    Node *pLeft;
    Node *pRight;

};

#endif

PriorityQueue.h 优先列队的头文件，我写的这个列队算法除了基本的操作之外，还有一个比较基础的排序算法（过去的文章有说到排序算法的实现）。

#pragma once
#ifndef _PriorityQueue_H_
#define _PriorityQueue_H_

#include "Base.h"

class PriorityQueue{
public:
    PriorityQueue() : pHead(nullptr){}
    ~PriorityQueue();

    void Add(Node *pTmp);
    Node* Delete();
    void Show();
    void Sort();
    bool IsLast();

private:
    Node *pHead;
};

#endif

PriorityQueue.cpp 优先列队的源文件

#include <iostream>
#include "PriorityQueue.h"

void PriorityQueue::Add(Node *pTmp){
    Node *pNew = new Node, *p = this->pHead;
    pNew->Index = pTmp->Index;
    pNew->Data = pTmp->Data;
    pNew->pNext = pTmp->pNext;

    pNew->pLeft = pTmp->pLeft;
    pNew->pRight = pTmp->pRight;

    if(this->pHead == nullptr){
        this->pHead = pNew;
    }else{
        if(pNew->pLeft != nullptr || pNew->pRight != nullptr){    //part1    树元素
            if(pNew->Index < p->Index){
                pNew->pNext = p;
                p = pNew;
            }else{
                while(p){
                    if(p->pNext != nullptr){
                        if(pNew->Index < p->pNext->Index){
                            pNew->pNext = p->pNext;
                            p->pNext = pNew;
                            break;
                        }
                    }else{
                        p->pNext = pNew;
                        break;
                    }

                    p = p->pNext;
                }

            }

        }else{    //part2    只是一个普通的队列元素
            while(p){
                if(p->Data == pNew->Data){
                    p->Index++;
                    break;
                }

                if(p->pNext == nullptr){
                    p->pNext = pNew;
                    break;
                }

                p = p->pNext;
            }

        }
    }
}

Node* PriorityQueue::Delete(){
    if(this->pHead != nullptr){
        Node *p = this->pHead->pNext, *tmp = new Node;
        tmp->Index = this->pHead->Index;
        tmp->Data = this->pHead->Data;
        tmp->pNext = nullptr;

        tmp->pLeft = this->pHead->pLeft;
        tmp->pRight = this->pHead->pRight;

        delete this->pHead;
        this->pHead = nullptr;

        this->pHead = p;
        return tmp;

    }else{
        return nullptr;
    }

}

void PriorityQueue::Show(){
    Node *p = this->pHead;

    while(p){
        std::cout << p << "\t" << p->Index << "\t" << p->Data << "\t" << p->pNext << std::endl;

        p = p->pNext;
    }

    std::cout << std::endl;
}

void PriorityQueue::Sort(){
    if(this->pHead != nullptr){
        Node *i = this->pHead, *p = nullptr;
        
        while(i){
            p = i;

            while(p){
                if(p->Index < i->Index){
                    Node *pTmp = new Node;
                    pTmp->Data = i->Data;
                    pTmp->Index = i->Index;
                    
                    i->Data = p->Data;
                    i->Index = p->Index;

                    p->Data = pTmp->Data;
                    p->Index = pTmp->Index;
                }

                p = p->pNext;
            }

            i = i->pNext;
        }

    }
}

bool PriorityQueue::IsLast(){
    if(this->pHead != nullptr){
        return false;
    }else{
        return true;
    }
}

PriorityQueue::~PriorityQueue(){
    delete this->pHead;
    this->pHead = nullptr;
}

HuffmanTree.h 赫夫曼树算法的头文件

#pragma once
#ifndef _HuffmanTree_H_
#define _HuffmanTree_H_

#include "Base.h"
#include "PriorityQueue.h"

class HuffmanTree{
public:
    HuffmanTree(char *str);

    void QueueAction();
    void TreeAction();

    void ShowTree();

private:
    void createTree(Node *pTree);
    void showTree(Node *pTree);

private:
    char *str;
    PriorityQueue queue;
    Node *pTree;

};

#endif

HuffmanTree.cpp 赫夫曼树算法的源文件

#include <iostream>
#include "HuffmanTree.h"

HuffmanTree::HuffmanTree(char *str) : pTree(nullptr){
    this->str = str;
}

void HuffmanTree::QueueAction(){
    int i = 0;

    while(this->str[i] != '\0'){
        int num = this->str[i];

        if(num != 0){
            Node *pTmp = new Node;
            pTmp->Index = 1;
            pTmp->Data = num;
            pTmp->pNext = pTmp->pLeft = pTmp->pRight = nullptr;

            this->queue.Add(pTmp);
        }
        
        i++;
    }

    this->queue.Show();
    this->queue.Sort();
    this->queue.Show();
}

void HuffmanTree::TreeAction(){
    while(!this->queue.IsLast()){
        this->createTree(this->pTree);
    }
}

void HuffmanTree::ShowTree(){
    this->showTree(this->pTree);
}

//////////////////////////////////////////////////////////////////////////
// 私有方法
//////////////////////////////////////////////////////////////////////////

void HuffmanTree::showTree(Node *pTree){
    if(pTree){
        std::cout << pTree << "\t" << pTree->Index << "\t" << pTree->Data << "\t" << pTree->pLeft << "\t" << pTree->pRight << std::endl;
        this->showTree(pTree->pLeft);
        this->showTree(pTree->pRight);
    }
}

void HuffmanTree::createTree(Node *pTree){
    Node *pLeft = this->queue.Delete();
    Node *pRight = this->queue.Delete();

    if(pLeft != nullptr && pRight != nullptr){
        Node *pNew = new Node;
        pNew->Index = pLeft->Index + pRight->Index;
        pNew->pLeft = pLeft;
        pNew->pRight = pRight;
        pNew->pNext = nullptr;

        this->queue.Add(pNew);
    }else{
        this->pTree = pLeft;
    }
}

Main.cpp 程序的主文件

#include <iostream>
#include "HuffmanTree.h"

using namespace std;

int main(){
    //HuffmanTree tree("f88999EEEEAAAAAbbbbbb333333333eeeeeeeeeee");
    HuffmanTree tree("e89AbEb3ee33b33e99EAf8eAAbee333eEEAe3bbee");    //打乱顺序的元素
    tree.QueueAction();
    tree.TreeAction();
    tree.ShowTree();

    system("pause");
    return 0;
}

这坑终于填完了，这月还会更新文章。

标签：算法, 原理, 实现, 树, 哈夫曼

该文章由 Shiqi 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源：https://fdawn.com/CPP/27.html