C语言实现求哈夫曼树的叶子结点和非叶结点的权值

以下是C语言实现求哈夫曼树的叶子结点和非叶结点的权值的示例代码：

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

#define N 100

// 定义哈夫曼树结点
typedef struct node {
    int weight; // 权值
    int parent; // 父结点下标
    int left; // 左孩子下标
    int right; // 右孩子下标
} HTNode;

// 定义哈夫曼编码结构体
typedef struct code {
    int bit[N]; // 存放哈夫曼编码
    int start; // 编码在bit数组中的起始位置
} HCode;

// 定义求哈夫曼树叶子结点和非叶子结点权值的函数
void get_leaf_and_nonleaf_weight(HTNode ht[], int n, int *leaf_weight, int *nonleaf_weight) {
    *leaf_weight = *nonleaf_weight = 0; // 初始化叶子结点和非叶子结点权值为0
    for (int i = 0; i < n; i++) {
        if (ht[i].left == -1 && ht[i].right == -1) { // 叶子结点
            *leaf_weight += ht[i].weight;
        } else { // 非叶子结点
            *nonleaf_weight += ht[i].weight;
        }
    }
}

int main() {
    int n; // 结点数目
    printf("请输入结点数目：");
    scanf("%d", &n);

    HTNode ht[N * 2 - 1]; // 哈夫曼树结点数组
    HCode hc[N]; // 哈夫曼编码数组

    // 初始化哈夫曼树结点
    for (int i = 0; i < n * 2 - 1; i++) {
        ht[i].parent = -1;
        ht[i].left = -1;
        ht[i].right = -1;
    }

    // 输入结点权值
    printf("请输入%d个结点的权值：", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ht[i].weight);
    }

    // 构建哈夫曼树
    for (int i = 0; i < n - 1; i++) {
        int s1, s2; // 权值最小的两个结点下标
        int w1, w2; // 权值最小的两个结点权值

        // 找出权值最小的两个结点
        w1 = w2 = 32767; // 初始化为最大值
        for (int j = 0; j < n + i; j++) {
            if (ht[j].parent == -1) { // 找没有父结点的结点
                if (ht[j].weight < w1) {
                    s2 = s1;
                    w2 = w1;
                    s1 = j;
                    w1 = ht[j].weight;
                } else if (ht[j].weight < w2) {
                    s2 = j;
                    w2 = ht[j].weight;
                }
            }
        }

        // 合并权值最小的两个结点
        ht[s1].parent = n + i;
        ht[s2].parent = n + i;
        ht[n + i].weight = w1 + w2;
        ht[n + i].left = s1;
        ht[n + i].right = s2;
    }

    // 求叶子结点和非叶子结点的权值
    int leaf_weight, nonleaf_weight;
    get_leaf_and_nonleaf_weight(ht, n * 2 - 1, &leaf_weight, &nonleaf_weight);
    printf("叶子结点权值之和为：%d\n", leaf_weight);
    printf("非叶子结点权值之和为：%d\n", nonleaf_weight);

    return 0;
}

以上代码可以通过输入结点数目和权值，构建哈夫曼树，并求出叶子结点和非叶子结点的权值之和。