c++构造哈夫曼树源代码

以下是C++语言实现哈夫曼树的构造，包括节点的结构体定义、构造函数、析构函数、哈夫曼树的构建函数以及一些辅助函数。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 节点的结构体定义
struct TreeNode {
    int weight;             // 权值
    TreeNode *left, *right; // 左右子节点指针
    TreeNode(int w) : weight(w), left(NULL), right(NULL) {}
};

// 用于比较两个节点的权值大小
class cmp {
public:
    bool operator()(TreeNode *a, TreeNode *b) {
        return a->weight > b->weight;
    }
};

class HuffmanTree {
private:
    TreeNode *root; // 根节点指针
    void clear(TreeNode *p) {
        if (p) {
            clear(p->left);
            clear(p->right);
            delete p;
        }
    }

public:
    // 构造函数
    HuffmanTree(vector<int> weights) {
        priority_queue<TreeNode *, vector<TreeNode *>, cmp> pq;
        for (int i = 0; i < weights.size(); i++) {
            pq.push(new TreeNode(weights[i]));
        }
        while (pq.size() > 1) {
            TreeNode *left = pq.top();
            pq.pop();
            TreeNode *right = pq.top();
            pq.pop();
            TreeNode *parent = new TreeNode(left->weight + right->weight);
            parent->left = left;
            parent->right = right;
            pq.push(parent);
        }
        root = pq.top();
    }

    // 析构函数
    ~HuffmanTree() {
        clear(root);
    }

    // 获取哈夫曼树的根节点
    TreeNode *getRoot() {
        return root;
    }

    // 判断某个节点是否为叶子节点
    bool isLeaf(TreeNode *p) {
        return (p->left == NULL && p->right == NULL);
    }

    // 获取某个叶子节点的权值
    int getLeafWeight(TreeNode *p) {
        return p->weight;
    }
};

使用方法：

int main() {
    vector<int> weights = {5, 2, 4, 7};
    HuffmanTree tree(weights);
    TreeNode *root = tree.getRoot();
    // ...
    return 0;
}