数据结构C语言算法5.10构造哈夫曼树

哈夫曼树是一种经典的树形数据结构，它用于压缩数据、编码和解码等方面。下面是用C语言实现构造哈夫曼树的算法。

1. 定义哈夫曼树节点的结构体：

struct huffman_node {
    int weight; // 权重
    int parent; // 父节点的下标
    int left; // 左子节点的下标
    int right; // 右子节点的下标
};

其中，`weight`表示节点的权重，`parent`表示父节点的下标，`left`和`right`分别表示左右子节点的下标。

2. 构造哈夫曼树的算法：

void huffman_tree(struct huffman_node *ht, int n) {
    int i, j, k;
    int min1, min2;
    for (i = 0; i < 2 * n - 1; i++) {
        ht[i].parent = -1;
        ht[i].left = -1;
        ht[i].right = -1;
    }
    for (i = 0; i < n; i++) {
        printf("请输入第%d个节点的权重：", i + 1);
        scanf("%d", &ht[i].weight);
    }
    for (i = 0; i < n - 1; i++) {
        min1 = min2 = INT_MAX;
        k = 0;
        for (j = 0; j < n + i; j++) {
            if (ht[j].parent == -1 && ht[j].weight < min1) {
                min2 = min1;
                min1 = ht[j].weight;
                k = j;
            } else if (ht[j].parent == -1 && ht[j].weight < min2) {
                min2 = ht[j].weight;
            }
        }
        ht[k].parent = n + i;
        ht[n + i].left = k;
        ht[n + i].right = -1;
        ht[n + i].weight = min1 + min2;
        k = 0;
        for (j = 0; j < n + i; j++) {
            if (ht[j].parent == -1 && ht[j].weight < min1) {
                min2 = min1;
                min1 = ht[j].weight;
                k = j;
            } else if (ht[j].parent == -1 && ht[j].weight < min2) {
                min2 = ht[j].weight;
            }
        }
        ht[k].parent = n + i;
        ht[n + i].right = k;
    }
}

该算法的主要思路是先输入每个节点的权重，然后依次构造哈夫曼树的各个节点。具体的实现过程如下：

- 首先，将哈夫曼树的所有节点的父节点、左右子节点初始化为-1。
- 然后，输入每个节点的权重。
- 接着，依次构造哈夫曼树的各个节点，直到构造完整个哈夫曼树。具体的构造过程如下：
- 找到权重最小的两个节点，分别作为新节点的左右子节点。
- 将新节点的权重设置为两个子节点的权重之和。
- 将新节点的父节点设置为原先没有父节点的节点中权重最小的节点。

3. 测试代码：

int main() {
    int n;
    printf("请输入节点的个数：");
    scanf("%d", &n);
    struct huffman_node ht[2 * n - 1];
    huffman_tree(ht, n);
    return 0;
}

该测试代码用于输入节点的个数，并调用前面实现的构造哈夫曼树的算法。

希望这个算法能对你有所帮助！