用c语言写一个算法计算哈夫曼树的WPL值

哈夫曼树的WPL（加权路径长度）是指所有叶子节点的权值乘以它们到根节点的路径长度之和，可以通过以下步骤来计算哈夫曼树的WPL值：

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

typedef struct Node {
    int weight; // 权值
    int parent; // 父节点编号
    int left_child; // 左子节点编号
    int right_child; // 右子节点编号
} Node, *HuffmanTree;

2. 定义比较函数

int cmp(const void *a, const void *b) {
    return ((Node *)a)->weight - ((Node *)b)->weight;
}

3. 构造哈夫曼树

void createHuffmanTree(HuffmanTree tree, int n) {
    int i, m1, m2, x1, x2;
    for (i = 0; i < 2 * n - 1; i++) {
        tree[i].weight = 0;
        tree[i].parent = -1;
        tree[i].left_child = -1;
        tree[i].right_child = -1;
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &tree[i].weight);
    }
    qsort(tree, n, sizeof(Node), cmp);
    for (i = n; i < 2 * n - 1; i++) {
        m1 = m2 = INT_MAX;
        x1 = x2 = -1;
        for (int j = 0; j < i; j++) {
            if (tree[j].parent == -1) {
                if (tree[j].weight < m1) {
                    m2 = m1;
                    x2 = x1;
                    m1 = tree[j].weight;
                    x1 = j;
                } else if (tree[j].weight < m2) {
                    m2 = tree[j].weight;
                    x2 = j;
                }
            }
        }
        tree[x1].parent = i;
        tree[x2].parent = i;
        tree[i].left_child = x1;
        tree[i].right_child = x2;
        tree[i].weight = m1 + m2;
    }
}

4. 计算WPL值

int getWPL(HuffmanTree tree, int n) {
    int wpl = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (tree[j].parent != -1) {
            if (j == tree[tree[j].parent].left_child) {
                wpl += tree[j].weight * (i + 1);
            }
            j = tree[j].parent;
        }
    }
    return wpl;
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct Node {
    int weight; // 权值
    int parent; // 父节点编号
    int left_child; // 左子节点编号
    int right_child; // 右子节点编号
} Node, *HuffmanTree;

int cmp(const void *a, const void *b) {
    return ((Node *)a)->weight - ((Node *)b)->weight;
}

void createHuffmanTree(HuffmanTree tree, int n) {
    int i, m1, m2, x1, x2;
    for (i = 0; i < 2 * n - 1; i++) {
        tree[i].weight = 0;
        tree[i].parent = -1;
        tree[i].left_child = -1;
        tree[i].right_child = -1;
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &tree[i].weight);
    }
    qsort(tree, n, sizeof(Node), cmp);
    for (i = n; i < 2 * n - 1; i++) {
        m1 = m2 = INT_MAX;
        x1 = x2 = -1;
        for (int j = 0; j < i; j++) {
            if (tree[j].parent == -1) {
                if (tree[j].weight < m1) {
                    m2 = m1;
                    x2 = x1;
                    m1 = tree[j].weight;
                    x1 = j;
                } else if (tree[j].weight < m2) {
                    m2 = tree[j].weight;
                    x2 = j;
                }
            }
        }
        tree[x1].parent = i;
        tree[x2].parent = i;
        tree[i].left_child = x1;
        tree[i].right_child = x2;
        tree[i].weight = m1 + m2;
    }
}

int getWPL(HuffmanTree tree, int n) {
    int wpl = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (tree[j].parent != -1) {
            if (j == tree[tree[j].parent].left_child) {
                wpl += tree[j].weight * (i + 1);
            }
            j = tree[j].parent;
        }
    }
    return wpl;
}

int main() {
    int n;
    printf("请输入叶子节点的个数：");
    scanf("%d", &n);
    HuffmanTree tree = (HuffmanTree)malloc(sizeof(Node) * (2 * n - 1));
    createHuffmanTree(tree, n);
    int wpl = getWPL(tree, n);
    printf("哈夫曼树的WPL值为：%d\n", wpl);
    free(tree);
    return 0;
}