哈夫曼树创建的算法实现

哈夫曼树的创建算法可以分为以下几步：

1. 统计每个字符在待编码字符串中出现的频率，并将其存储在一个数组中。

2. 将数组中的元素构建成森林，每个元素作为一棵只包含自己的树。

3. 选取森林中权值最小的两棵树进行合并，生成一棵新的树，新树的根节点权值为两棵树根节点权值之和。

4. 将新生成的树插入到森林中，并从森林中删除原来的两棵树。

5. 重复步骤3和步骤4，直到森林中只剩下一棵树，即哈夫曼树。

下面是一个基于数组实现的哈夫曼树创建算法的伪代码：

// 定义一个节点结构体
struct Node {
    int weight; // 权值
    int parent; // 父节点
    int left; // 左子节点
    int right; // 右子节点
};

// 创建哈夫曼树的函数
void createHuffmanTree(Node *tree, int *weights, int n) {
    // 初始化森林，每个节点作为一棵只包含自己的树
    for (int i = 0; i < n; i++) {
        tree[i].weight = weights[i];
        tree[i].parent = -1;
        tree[i].left = -1;
        tree[i].right = -1;
    }

    // 合并森林中的树，直到森林中只剩下一棵树
    for (int i = 0; i < n - 1; i++) {
        int min1 = INT_MAX, min2 = INT_MAX; // 记录森林中权值最小的两棵树
        int min1Index = -1, min2Index = -1;

        // 在森林中找到权值最小的两棵树
        for (int j = 0; j < n + i; j++) {
            if (tree[j].parent == -1) { // 只考虑还没有被合并的树
                if (tree[j].weight < min1) {
                    min2 = min1;
                    min2Index = min1Index;
                    min1 = tree[j].weight;
                    min1Index = j;
                } else if (tree[j].weight < min2) {
                    min2 = tree[j].weight;
                    min2Index = j;
                }
            }
        }

        // 合并权值最小的两棵树
        tree[min1Index].parent = n + i;
        tree[min2Index].parent = n + i;
        tree[n + i].weight = tree[min1Index].weight + tree[min2Index].weight;
        tree[n + i].left = min1Index;
        tree[n + i].right = min2Index;
    }
}

在这个算法中，我们使用了一个节点结构体来表示哈夫曼树中的每个节点，包括节点的权值、父节点、左子节点和右子节点。我们首先初始化森林，每个节点作为一棵只包含自己的树。然后，我们重复执行选择权值最小的两棵树进行合并的操作，直到森林中只剩下一棵树为止。最终生成的树就是哈夫曼树。