数据结构(四)Huffman树实现

数据结构…本系列旨在对基础算法进行记录和学习,为了之后的面试一个弥补~~

本系列不是科普文,是为了找工作快速拾遗系列.

快速浏览,不会把学过的东西忘记~~

1.霍夫曼树由来

哈夫曼编码（Huffman Coding）是一种编码方式，也称为“赫夫曼编码”，是David A. Huffman1952年发明的一种构建极小多余编码的方法。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号进行编码，出现频率较高的源符号采用较短的编码，出现频率较低的符号采用较长的编码，使编码之后的字符串字符串的平均长度 、期望值降低，以达到无损压缩数据的目的。
举个例子，现在我们有一字符串：

this is an example of a huffman tree

这串字符串有36个字符，如果按普通方式存储这串字符串，每个字符占据1个字节，则共需要36 * 1 * 8 = 288bit。
经过分析我们发现，这串字符串中各字母出现的频率不同，如果我们能够按如下编码：

字母	频率	编码	---	字母	频率	编码
space	7	111		s	2	1011
a	4	010		t	2	0110
e	4	000		l	1	11001
f	3	1101		o	1	00110
h	2	1010		p	1	10011
i	2	1000		r	1	11000
m	2	0111		u	1	00111
n	2	0010		x	1	10010

编码这串字符串，只需要：
(7+4+4)x3 + (3+2+2+2+2+2+2)x4 + (1+1+1+1+1+1)x 5 = 45+60+30 = 135bit
编码这串字符串只需要135bit！单单这串字符串，就压缩了288-135 = 153bit。

那么，我们如何获取每个字符串的编码呢？这就需要哈夫曼树了。
源字符编码的长短取决于其出现的频率，我们把源字符出现的频率定义为该字符的权值。

2.霍夫曼树

维基-Huffman示意图 维基-Huffman创建 中文-huffman创建

/*创建哈夫曼树*/
template<typename T>
void Huffman<T>::creat(T a[],int size)
{
    for (int i = 0; i < size; i++) //每个节点都作为一个森林
    {
        //为初始序列的元素构建节点。每个节点作为一棵树加入森林中。
        HuffmanNode<T>* ptr = new HuffmanNode<T>(a[i],nullptr,nullptr);  
        forest.push_back(ptr);
    }
    for (int i = 0; i < size - 1; i++)
    {
        //排序，以选出根节点权值最小两棵树
        sort(forest.begin(), forest.end(), [](HuffmanNode<T>* a, HuffmanNode<T>*b){return a->key< b->key; });    
        HuffmanNode<T>*node = new HuffmanNode<T>(forest[0]->key + forest[1]->key, forest[0], forest[1]); //构建新节点
        forest.push_back(node);  //新节点加入森林中
        forest.pop_front(); //删除两棵权值最小的树
        forest.pop_front();
    }
    root = forest.front();
    forest.clear();
};

3.总体代码程序

只是简单实现了Huffman的原理,细节没有进行优化实现

#ifndef HUFFMAN_H
#define HUFFMAN_H

#include<iostream>
#include <deque>
#include <algorithm>

using namespace std;

/*哈夫曼树的节点定义*/
template<typename T>
struct HuffmanNode
{
    HuffmanNode(T k,HuffmanNode<T>*lchildt=nullptr,HuffmanNode<T>*rchildt=nullptr):
        key(k),lchild(lchildt),rchild(rchildt){}

    T key;
    HuffmanNode<T>* lchild;
    HuffmanNode<T>* rchild;
};

template<typename T>
class Huffman
{
public:
    void preOrder();              //前序遍历哈夫曼树
    void inOrder();                  //中序遍历哈夫曼树
    void postOrder();              //后序遍历哈夫曼树

    void creat(T a[], int size);  //创建哈夫曼树
    void destory();                 //销毁哈夫曼树
    void print();                  //打印哈夫曼树

    Huffman():root(nullptr)
    {}
    ~Huffman()
    {
        //destory(root);
    }

private:
    void preOrder(HuffmanNode<T>* pnode);
    void inOrder(HuffmanNode<T>* pnode);
    void postOrder(HuffmanNode<T>* pnode);
    void print(HuffmanNode<T>* pnode);
    void destroy(HuffmanNode<T>* pnode);

private:
    typedef HuffmanNode<T>* pointer;
    pointer root;     //哈夫曼树根节点
    deque<pointer> forest;//森林
};

/*创建哈夫曼树*/
template<typename T>
void Huffman<T>::creat(T a[], int size)
{
    for (int i = 0; i < size; i++) //每个节点都作为一个森林
    {
        pointer ptr = new HuffmanNode<T>(a[i],nullptr,nullptr);
        forest.push_back(ptr);
    }
    for (int i = 0; i < size - 1; i++)
    {
        sort(forest.begin(), forest.end(), [](HuffmanNode<T>* a, HuffmanNode<T>*b){return a->key< b->key; });
        HuffmanNode<T>*node = new HuffmanNode<T>(forest[0]->key + forest[1]->key, forest[0], forest[1]);
        forest.push_back(node);
        forest.pop_front();
        forest.pop_front();
    }
    root = forest.front();
    forest.clear();
}

/*前序遍历哈夫曼树*/
template <typename T>
void Huffman<T>::preOrder(HuffmanNode<T>* pnode)
{
    if (pnode != nullptr)
    {
        cout << pnode->key;
        preOrder(pnode->lchild);
        preOrder(pnode->rchild);
    }
}
template <typename T>
void Huffman<T>::preOrder()
{
    preOrder(root);
}

/*中序遍历哈夫曼树*/
template <typename T>
void Huffman<T>::inOrder(HuffmanNode<T>* pnode)
{
    if (pnode != nullptr)
    {
        inOrder(pnode->lchild);
        cout << pnode->key;
        inOrder(pnode->rchild);
    }
};
template <typename T>
void Huffman<T>::inOrder()
{
    inOrder(root);
}

/*后序遍历哈夫曼树*/
template <typename T>
void Huffman<T>::postOrder(HuffmanNode<T>* pnode)
{
    if (pnode != nullptr)
    {
        postOrder(pnode->lchild);
        postOrder(pnode->rchild);
        cout << pnode->key;
    }
};
template <typename T>
void Huffman<T>::postOrder()
{
    postOrder(root);
}

template<typename T>
void Huffman<T>::print(HuffmanNode<T>* pnode)
{
    if (pnode != nullptr)
    {
        cout << "当前结点：" << pnode->key<<".";
        if (pnode->lchild != nullptr)
            cout << "它的左孩子节点为：" << pnode->lchild->key << ".";
        else cout << "它没有左孩子.";
        if (pnode->rchild != nullptr)
            cout << "它的右孩子节点为：" << pnode->rchild->key << ".";
        else cout << "它没有右孩子.";
        cout << endl;
        print(pnode->lchild);
        print(pnode->rchild);
    }
}

/*销毁哈夫曼树*/
template <typename T>
void Huffman<T>::destory()
{
    destroy(root);
}
template<typename T>
void Huffman<T>::destroy(HuffmanNode<T>* pnode)
{
    if (pnode != nullptr)
    {
        destroy(pnode->lchild);
        destroy(pnode->rchild);
        delete pnode;
        pnode = nullptr;
    }
}

#endif // HUFFMAN_H

注意C++的template只能在一个头文件,千万不要模块化编程一个在.h文件一个在.cpp文件!!!

参考资料:

文章主要参考,且图片均来自大神博文

动态图请参考小甲鱼视频

我之前写的C++链表

吕鑫老师视频,很早之前看得