哈夫曼树

简介
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。

构建哈夫曼树的过程

• 对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
• 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
• 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
• 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

c++代码
HUFFMAN.H

#include <string>
#include "vector"
#include "unordered_map"
#include "map"
#include "stack"
#ifndef HUFFMAN_HUFFMAN_H
#define HUFFMAN_HUFFMAN_H
typedef int elemType;

typedef struct Node {
    elemType weight;
    char c;
    struct Node *lChild = nullptr, *rChild = nullptr, *parent = nullptr;
}Node,*lNode;


class huffman {
private:std::map<char, std::string> codeMap;
    std::vector<std::vector<int>> code;
    std::vector<Node *> node_list;
    std::vector<Node *> node_list_bak;
    Node *root{};
    int findMinNode();
    void deleteNode(int pos);
public:
    huffman(const std::map<char, int>& list, int num);
    void generateTree();
    void generateCode();
    void decode(std::string str);
    void printCode();
    void encode();
    Node *returnNode();
};


#endif //HUFFMAN_HUFFMAN_H

HUFFMAN.C

//
// Created by ren on 2020/12/1.
//

#include "huffman.h"
#include "iostream"
#include <algorithm>
#include "unordered_map"
#include "map"
#include "stack"
huffman::huffman(const std::map<char, int>& list, int num) {
    code.resize(num);
    for (auto & it : list){
        Node *node = (Node *)malloc(sizeof(Node));
        node->c = it.first;
        node->weight = it.second;
        this->node_list.push_back(node);
    }
    this->node_list_bak = this->node_list;
}

void huffman::generateTree() {
    Node *nodeRight, *nodeLeft;
//    auto nodeRight = (Node *)malloc(sizeof(Node));
//    auto nodeLeft = (Node *)malloc(sizeof(Node));
    auto nodeParent = (Node *)malloc(sizeof(Node));
    nodeParent->parent = nullptr;
    nodeParent->c = '\0';
    nodeRight = node_list[findMinNode()];
    deleteNode(findMinNode());
    nodeLeft = node_list[findMinNode()];
    deleteNode(findMinNode());
    nodeParent->rChild = nodeLeft;
    nodeParent->lChild = nodeRight;
    nodeParent->weight = nodeRight->weight + nodeLeft->weight;
    nodeLeft->parent = nodeParent;
    nodeRight->parent = nodeParent;
    node_list.push_back(nodeParent);
    if (node_list.size() != 1) {
        this->generateTree();
    }else this->root = node_list[0];

}
void huffman::generateCode() {
    node_list = node_list_bak;
//    for (int i = 0; i < node_list.size(); ++i) {
//        std::cout << node_list[i]->c << std::endl;
//    }
    for (int i = 0; i < node_list.size(); ++i) {
//        std::vector<int> vec;
        char c = node_list[i]->c;
//        vec.push_back(node_list_bak[i]->c);
        Node *temp = node_list[i];
        while (true) {
            if (temp->parent == nullptr) break;
            if (temp->parent->lChild == temp)
                code[i].push_back(0);
            else if (temp->parent->rChild == temp)
                code[i].push_back(1);
            temp = temp->parent;
        }
        code[i].push_back(c);
        std::string str;
        std::reverse(code[i].begin(), code[i].end());
        for (int j = 1; j < code[i].size(); ++j) {
            str.push_back(std::to_string(code[i][j])[0]);
        }
        codeMap.insert(std::make_pair(code[i][0], str));


    }
}
int huffman::findMinNode() {
    int min = 0;
    for (int i = 0; i < node_list.size(); ++i) {
        if (node_list[min]->weight > node_list[i]->weight) min = i;
    }
    return min;
}

void huffman::deleteNode(int pos) {
    auto p = node_list.begin() + pos;
    node_list.erase(p);
}

void huffman::printCode() {
    for (int i = 0; i < code.size(); ++i) {
        std::cout << char(code[i][0]) << " ";
        for (int j = 1; j < code[i].size(); ++j) {
            std::cout << code[i][j];
        }
        std::cout << std::endl;
    }
}

Node *huffman::returnNode() {
    return root;
}

void huffman::decode(std::string str) {
    Node * node = root;
    for (int i = 0; i < str.size() + 1; ++i) {
        if (node->c){
            std::cout << node->c << " ";
            node = root;
        }
        if (str[i] == '0' and node->c == '\0'){
            node = node->lChild;
        }
        else if (str[i] == '1' and node->c == '\0'){
            node = node->rChild;
        }
    }
}

void huffman::encode() {
    std::string str;
    std::cin >> str;
    for (int i = 0; i < str.size(); ++i) {
        std::cout << codeMap[str[i]];
    }
}

MAIN.C

#include <iostream>
#include "huffman.h"
#include "unordered_map"
int main() {
    int num;
    std::cin >> num;
    std::map<char, int> l;
    std::string s = "abcdefghijklmnopqrstuvwxyz";
    for (int i = 0; i < num; ++i) {
        int weight;
        char c = s[i];
        std::cin >> weight;
        l.insert(std::make_pair(c,weight));
    }
    huffman tree(l, num);
    tree.generateTree();
    tree.generateCode();
    tree.printCode();
    std::cout << "encode data: ";
    tree.encode();
    std::cout << std::endl;
    std::cout << "decode data: ";
    std::string code;
    std::cin >> code;
    tree.decode(code);
}