构造哈夫曼树求带权路径长度C语言

以下是用C语言实现构造哈夫曼树并求带权路径长度的代码：

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

#define MAX_NODE 100   //最大节点数

//哈夫曼树节点结构体
typedef struct {
    int weight;   //权值
    int parent;   //双亲节点
    int lchild;   //左孩子节点
    int rchild;   //右孩子节点
}HTNode;

//哈夫曼编码结构体
typedef struct {
    char ch;   //字符
    char code[20];   //编码
}HFCode;

//创建哈夫曼树
void CreateHT(HTNode ht[], int n) {
    int i, k, min1, min2;
    int x = 2 * n - 1;   //哈夫曼树节点数
    //初始化哈夫曼树
    for (i = 0; i < n; i++) {
        ht[i].parent = -1;
        ht[i].lchild = -1;
        ht[i].rchild = -1;
    }
    for (i = n; i < x; i++) {
        ht[i].parent = -1;
        ht[i].lchild = -1;
        ht[i].rchild = -1;
        //在ht[0~i-1]中找权值最小的两个节点，下标分别为min1、min2
        min1 = min2 = -1;
        for (k = 0; k < i; k++) {
            if (ht[k].parent == -1) {
                if (min1 == -1) {
                    min1 = k;
                }
                else if (min2 == -1) {
                    min2 = k;
                }
                else {
                    if (ht[k].weight < ht[min1].weight) {
                        min2 = min1;
                        min1 = k;
                    }
                    else if (ht[k].weight < ht[min2].weight) {
                        min2 = k;
                    }
                }
            }
        }
        //将两个权值最小的节点合并成一个新节点，下标为i
        ht[i].weight = ht[min1].weight + ht[min2].weight;
        ht[i].lchild = min1;
        ht[i].rchild = min2;
        ht[min1].parent = i;
        ht[min2].parent = i;
    }
}

//生成哈夫曼编码
void CreateHCode(HTNode ht[], int n, HFCode hfc[]) {
    int i, j, k;
    char cd[MAX_NODE];
    int start, c;
    cd[n - 1] = '\0';
    for (i = 0; i < n; i++) {
        start = n - 1;
        c = i;
        while (ht[c].parent != -1) {
            if (ht[ht[c].parent].lchild == c) {
                cd[--start] = '0';
            }
            else {
                cd[--start] = '1';
            }
            c = ht[c].parent;
        }
        strcpy(hfc[i].code, &cd[start]);
    }
}

//打印哈夫曼编码
void PrintHCode(HFCode hfc[], int n) {
    int i;
    printf("字符\t编码\n");
    for (i = 0; i < n; i++) {
        printf("%c\t%s\n", hfc[i].ch, hfc[i].code);
    }
}

//计算带权路径长度
int WPL(HTNode ht[], int n) {
    int i, wpl = 0;
    for (i = 0; i < n; i++) {
        int c = i;
        while (ht[c].parent != -1) {
            if (ht[ht[c].parent].lchild == c) {
                wpl += ht[c].weight;
            }
            c = ht[c].parent;
        }
    }
    return wpl;
}

int main() {
    int n, i;
    HTNode ht[MAX_NODE];
    HFCode hfc[MAX_NODE];
    printf("请输入字符个数：");
    scanf("%d", &n);
    printf("请输入%d个字符及其权值：\n", n);
    for (i = 0; i < n; i++) {
        getchar();   //吃掉回车
        scanf("%c%d", &hfc[i].ch, &ht[i].weight);
    }
    CreateHT(ht, n);
    CreateHCode(ht, n, hfc);
    PrintHCode(hfc, n);
    printf("带权路径长度为：%d\n", WPL(ht, n));
    return 0;
}

该代码实现了哈夫曼树的构建、哈夫曼编码的生成以及带权路径长度的计算。在输入字符及其权值后，先调用CreateHT函数创建哈夫曼树，然后调用CreateHCode函数生成哈夫曼编码，最后调用PrintHCode函数打印哈夫曼编码和WPL函数计算带权路径长度并输出。