哈夫曼树的建立（二叉链表）

哈夫曼树是一种带权路径长度最短的二叉树，用于数据压缩等领域。下面是哈夫曼树的建立过程：

1. 将所有权值作为叶子结点，构成n棵只有一个结点的二叉树。
2. 从这n棵二叉树中选出两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，且新二叉树的根节点权值为左右子树根节点权值之和。
3. 将这棵新树插入到n棵二叉树中，删除选出的两棵二叉树，得到n-1棵二叉树。
4. 重复2-3步，直到构造出一棵二叉树，即为哈夫曼树。

下面是代码实现（二叉链表）：

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

// 定义哈夫曼树节点
struct Node {
    int weight; // 权值
    Node* left; // 左儿子
    Node* right; // 右儿子
    Node(int w = 0, Node* l = NULL, Node* r = NULL) : weight(w), left(l), right(r) {}
};

// 比较函数，用于优先队列中节点的排序
struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight;
    }
};

// 构造哈夫曼树
Node* buildHuffmanTree(int* weight, int n) {
    priority_queue<Node*, vector<Node*>, cmp> q;
    for (int i = 0; i < n; i++) {
        q.push(new Node(weight[i]));
    }
    while (q.size() > 1) {
        Node* left = q.top(); q.pop();
        Node* right = q.top(); q.pop();
        Node* parent = new Node(left->weight + right->weight, left, right);
        q.push(parent);
    }
    return q.top();
}

// 先序遍历哈夫曼树
void preOrder(Node* root) {
    if (root) {
        cout << root->weight << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main() {
    // 假设有7个权值，分别为1,2,2,3,4,5,6
    int weight[] = { 1,2,2,3,4,5,6 };
    int n = sizeof(weight) / sizeof(int);
    Node* root = buildHuffmanTree(weight, n);
    preOrder(root); // 输出：23 12 6 3 1 2 5 4 
    return 0;
}