求哈夫曼树的叶子结点和非叶结点的权值

哈夫曼树是一种带权路径长度最短的树，由一组带权值的叶子节点构建而成。因此，哈夫曼树的叶子节点的权值即为所代表字符的权值，非叶子节点的权值为其左右子树权值之和。

假设有一组权值为{5, 2, 8, 12, 3}的字符，构建哈夫曼树的过程如下：

1. 将所有字符的权值作为单独的树节点。
2. 从中选出两个权值最小的节点，合并成一个新节点，其权值为这两个节点权值之和。将这个新节点作为一棵树的根节点。
3. 重复步骤2，直到所有节点都被合并成为一棵树。

具体过程如下：

第一步，将所有字符的权值作为单独的树节点：

5   2   8   12   3

第二步，选出权值最小的两个节点2和3，合并成为一个新节点，其权值为2+3=5。将这个新节点作为一棵树的根节点：

   5
  / \
 2   3
    / \
   8  12

第三步，选出权值最小的两个节点5和8，合并成为一个新节点，其权值为5+8=13。将这个新节点作为一棵树的根节点：

     13
    /  \
   5    8
  / \   / \
 2   3 12

第四步，选出权值最小的两个节点12和13，合并成为一个新节点，其权值为12+13=25。将这个新节点作为一棵树的根节点：

       25
      /  \
     13   12
    /  \
   5    8
  / \   / \
 2   3

此时，哈夫曼树构建完成。叶子节点的权值分别为2、3、5、8、12，非叶子节点的权值分别为13和25。

相关问题

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;
}

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

给出n个有权值的叶结点,用这些结点生成哈夫曼树,求这棵树的带权路径长度(即这棵树

哈夫曼树是一种最优二叉树，根据给定的n个叶结点的权值，可以通过构建哈夫曼树来实现最小化带权路径长度。以下是求解这棵哈夫曼树带权路径长度的方法：

1. 对于给定的n个叶结点，按照权值从小到大的顺序排列。
2. 选择权值最小的两个叶结点作为新的子树，将它们合并为一个新的父节点，父节点的权值为两个子节点的权值之和，并将这棵树添加到叶子结点集合中。
3. 重复步骤2，直到叶结点集合中只剩下一个根结点。
4. 计算每个结点到根结点的路径长度，路径长度即为从该结点到根结点的边的权值之和。
5. 将每个结点的路径长度乘以该结点的权值，再将所有结点的乘积相加，即可求得哈夫曼树的带权路径长度。

例如，有4个叶结点，权值分别为2、3、4、5，按照从小到大的顺序排列为2、3、4、5。首先选择第一个和第二个叶结点，合并为一个新的父节点，权值为2+3=5。然后选择第三个叶结点和刚合并的节点，合并为一个新的父节点，权值为4+5=9。最后将第四个叶结点和刚合并的节点再合并为一个新的根结点，权值为9+5=14。计算路径长度，根节点的路径长度为0，第一次合并的节点的路径长度为1，第二次合并的节点的路径长度为2，第四个叶结点的路径长度为3。带权路径长度为5×0+5×1+9×2+14×3=74。所以哈夫曼树的带权路径长度为74。

通过以上方法，可以求得n个有权值的叶结点生成的哈夫曼树的带权路径长度。