数据结构(六)霍夫曼树与编码

今天药忘吃喽~ 2022-05-31 01:22 255阅读 0赞

**1、算法流程**

(1)构建霍夫曼树：自底向上

根据统计频率构建霍夫曼树：

A、把所有的节点扔进排序队列queue中；

B、从queue选择选择前面两个最小的元素a、b，把最小的树a作为左节点，把最小的b作为右节点，以此构建父节点c(c的频率值为a+b的频率值)，然后把a、b从队列删除、把c节点插入队列；

C、循环(A)、(B)步骤构建霍夫曼树，直到queue为空。

(2)编码阶段：自顶向下

A、除了树的根节点没有码值之外，其他的根据左右子节点进行编码，做节点编码为0，右节点编码为1；

B、子节点在父节点码值的基础上，在后面加上一位对应的码值。

(3)解码阶段：自顶向下解码

根据给定的码值，从树根开始递归遍历，遇到0向左走，遇到1向又走，直到码值为空或者遇到叶子节点返回。

**2、代码实现**

#ifndef DATA_STRUCT_TREE_H
    #define DATA_STRUCT_TREE_H
    #include<vector>
    #include <set>
    #include <queue>
    #include <string>
    using namespace std;
    class node{
    public:
        node(){
            left_child=NULL;
            right_child=NULL;
            frequency=0;
            coding.clear();
            words="";
        };
        ~node(){};
    
        node* left_child;
        node* right_child;
        int frequency;
        std::vector<bool> coding;
        string words;
    
    
    public:
        bool operator <(const node& n1) const
        {
            return frequency<n1.frequency;
        }
    };
    class huffman_coding{
    public:
        static void create_tree(std::set<node>&queue,std::vector<node*>&tree){
    
            while (!queue.empty())
            {
                node *left= new node(*queue.begin());
                queue.erase(queue.begin());
                tree.push_back(left);
    
                if (!queue.empty())
                {
                    node *right=new node(*queue.begin());
                    queue.erase(*queue.begin());
                    tree.push_back(right);
    
                    node merge;
                    merge.frequency=left->frequency+right->frequency;
                    merge.left_child=left;
                    merge.right_child=right;
                    queue.insert(merge);
                }
    
    
    
            }
    
        }
        //自顶向下编码
        static void huffman_encoding(node*head){
    
            //广度优先遍历
            std::queue<node*>Q;
            Q.push(head);
            while (!Q.empty())
            {
                node*n=Q.front();
                Q.pop();
                if(n->left_child)
                {
                    n->left_child->coding=n->coding;
                    n->left_child->coding.push_back(false);
                    Q.push(n->left_child);
                }
                if(n->right_child)
                {
                    n->right_child->coding=n->coding;
                    n->right_child->coding.push_back(true);
                    Q.push(n->right_child);
                }
    
            }
        }
        static string huffman_decoding(node*head,vector<bool>coding)
        {
            if(coding.empty()||!(head->right_child)||!(head->left_child))
                return head->words;
            std::vector<bool>::iterator this_code=coding.begin();
    
    
            if(*this_code)//右节点
            {
                coding.erase(this_code);
                return  huffman_decoding(head->right_child,coding);
            }
            else
            {
    
                coding.erase(this_code);
                return huffman_decoding(head->left_child,coding);
            }
    
    
    
    
    
        }
    
        static  void main(){
            //http://blog.csdn.net/xgf415/article/details/52628073
            int frequency[5]={10,8,3,4,5};
            string words[5]={"B","A","C","D","E"};
            std::set<node>queue;
            for(int i=0;i<5;i++)
            {
                node n;
                n.frequency=frequency[i];
                n.words=words[i];
    
                queue.insert(n);
            }
    
    
    
    
            std::vector<node*>tree;
            create_tree(queue,tree);
            huffman_encoding(tree[tree.size()-1]);
    
    
            //打印编码结果
    
            for(std::vector<node*>::iterator it=tree.begin();it!=tree.end();it++)
            {
                if ((*it)->words=="")
                    continue;
                std::cout<<(*it)->words<<":";
                for (int i = 0; i <(*it)->coding.size() ; ++i) {
                    std::cout<<(*it)->coding[i];
                }
                std::cout<<std::endl;
            }
    
            //测试解码
            string decode=huffman_decoding(tree[tree.size()-1],tree[0]->coding);
            std::cout<<decode<<":";
            for (int j = 0; j < tree[0]->coding.size(); ++j) {
                std::cout<<tree[0]->coding[j];
    
    
            }
            std::cout<<std::endl;
    
    
    
    
    
        }
    };
    
    
    
    
    
    #endif //DATA_STRUCT_TREE_H