用5个权值3 2 4 5 1构造的哈夫曼树的带权路径长度

首先，我们需要构造哈夫曼树。具体步骤如下：

1. 将权值从小到大排序，得到：1 2 3 4 5。
2. 取出权值最小的两个节点 1 和 2，构造一个新节点，权值为它们的和 3，将新节点插入到原来的节点中，得到：3 3 4 5。
3. 取出权值最小的两个节点 3 和 3，构造一个新节点，权值为它们的和 6，将新节点插入到原来的节点中，得到：4 5 6。
4. 取出权值最小的两个节点 4 和 5，构造一个新节点，权值为它们的和 9，将新节点插入到原来的节点中，得到：9 6。
5. 取出权值最小的两个节点 6 和 9，构造一个新节点，权值为它们的和 15，得到最终的哈夫曼树。

    15
   /  \
  6    9
 / \
4   5

接下来，计算带权路径长度（WPL），即每个叶子节点的权值乘以它到根节点的路径长度之和，然后把所有叶子节点的 WPL 相加即可。

- 叶子节点 1 的 WPL：1 × 3 = 3
- 叶子节点 2 的 WPL：2 × 3 = 6
- 叶子节点 3 的 WPL：3 × 2 = 6
- 叶子节点 4 的 WPL：4 × 2 = 8
- 叶子节点 5 的 WPL：5 × 2 = 10

总的 WPL = 3 + 6 + 6 + 8 + 10 = 33。

所以，用5个权值3 2 4 5 1构造的哈夫曼树的带权路径长度为 33。

相关问题

用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是（ ）。

首先我们需要构建哈夫曼树。哈夫曼树的构建过程如下：

1. 将所有权值从小到大排序，得到{1, 2, 3, 4, 5}。
2. 取出权值最小的两个节点1和2，构建一个新节点，权值为1+2=3，作为1和2的父节点。
3. 将3插入到排序后的序列中，得到{3, 3, 4, 5}。
4. 取出权值最小的两个节点3和3，构建一个新节点，权值为3+3=6，作为3和3的父节点。
5. 将6插入到排序后的序列中，得到{4, 5, 6}。
6. 取出权值最小的两个节点4和5，构建一个新节点，权值为4+5=9，作为4和5的父节点。
7. 将9插入到排序后的序列中，得到{6, 9}。
8. 取出权值最小的两个节点6和9，构建一个新节点，权值为6+9=15，作为6和9的父节点。
9. 得到哈夫曼树，其带权路径长度为：1*3 + 2*3 + 3*4 + 4*5 + 5*1 = 49。

因此，用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是49。

构造哈夫曼树求带权路径长度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函数计算带权路径长度并输出。