哈夫曼树的构造算法c++

### C++ 实现哈夫曼树构造算法

#### 节点结构定义
为了构建哈夫曼树，首先需要定义节点的数据结构。每个节点包含权重、指向左右子节点以及父节点的指针。

template <class T = double>
struct HuffmanTreeNode {
    HuffmanTreeNode(const T &w = T(), int l = 0, int r = 0, int p = 0)
        : _weight(w), _left(l), _right(r), _parent(p) {}

    T _weight;     // 权值
    int _left;      // 左孩子索引
    int _right;     // 右孩子索引
    int _parent;    // 父节点索引
};

此部分代码用于创建哈夫曼树中的各个节点[^3]。

#### 初始化函数
接下来是初始化函数，该函数接收一组频率作为输入参数，并基于这些频率来初始化哈夫曼树所需的数组和其他变量：

void InitHuffmanTree(vector<HuffmanTreeNode<double>>& nodes,
                     vector<char>& chars,
                     const map<char, double>& freqMap) {
    for (auto& pair : freqMap) {
        chars.push_back(pair.first);
        nodes.emplace_back(HuffmanTreeNode<double>(pair.second));
    }
}

这段代码负责读取字符及其对应的出现次数并将其转换成适合后续处理的形式[^2]。

#### 构建哈夫曼树的核心逻辑
核心在于反复选取当前森林中具有最小权值的两棵树合并为一棵新的二叉树直到只剩下一棵为止:

void BuildHuffmanTree(vector<HuffmanTreeNode<double>>& nodes) {
    while (nodes.size() > 1) {
        auto comp = [](const HuffmanTreeNode<double>& a, const HuffmanTreeNode<double>& b) {
            return a._weight > b._weight;
        };
        
        make_heap(nodes.begin(), nodes.end(), comp); // 创建一个小顶堆
        
        pop_heap(nodes.begin(), nodes.end(), comp); // 提取出最小元素
        HuffmanTreeNode<double> nodeA = nodes.back();
        nodes.pop_back();

        pop_heap(nodes.begin(), nodes.end(), comp); // 再次提取出第二小元素
        HuffmanTreeNode<double> nodeB = nodes.back();
        nodes.pop_back();

        // 新建一个内部节点并将上述两个节点设为其子女
        HuffmanTreeNode<double> newNode(nodeA._weight + nodeB._weight);

        newNode._left = static_cast<int>(&nodeA - &nodes[0]);
        newNode._right = static_cast<int>(&nodeB - &nodes[0]);

        nodeA._parent = nodes.size(); // 更新被选作孩子的节点的父亲关系
        nodeB._parent = nodes.size();

        nodes.push_back(newNode);
    }
}

这里实现了选择最小权值结点的过程，并通过不断组合形成最终完整的哈夫曼树。