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

构造哈夫曼树的过程如下：

1. 对权值进行从小到大的排序：{1, 2, 3, 4, 5}。

2. 取出权值最小的两个节点1和2，合并成一个新节点3，其权值为1+2=3。此时节点集合为{3, 3, 4, 5}。

3. 取出权值最小的两个节点3和3，合并成一个新节点6，其权值为3+3=6。此时节点集合为{4, 5, 6}。

4. 取出权值最小的两个节点4和5，合并成一个新节点9，其权值为4+5=9。此时节点集合为{6, 9}。

5. 取出权值最小的两个节点6和9，合并成一个新节点15，其权值为6+9=15。此时节点集合为{15}。

哈夫曼树构造完成，它的带权路径长度为：(1*2)+(2*2)+(3*2)+(4*1)+(5*1)=19。

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

相关问题

哈夫曼树，第一行输入一个数n，表示叶结点的个数。 需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出哈夫曼树的带权路径长度（WPL）。

好的，我来给出一个实现。首先，我们需要定义一个节点类来表示哈夫曼树中的节点，包含权值和左右子节点。代码如下：

class HuffmanNode:
    def __init__(self, weight, left=None, right=None):
        self.weight = weight
        self.left = left
        self.right = right

接着，我们需要构建哈夫曼树。我们可以通过一个优先队列来实现，每次取出权值最小的两个节点，合并成一个新节点，并将其放回优先队列中，直到只剩下一个节点。代码如下：

import heapq

def build_huffman_tree(weights):
    """
    Build a Huffman tree from a list of weights.
    """
    nodes = [HuffmanNode(weight) for weight in weights]
    heapq.heapify(nodes)
    
    while len(nodes) > 1:
        left = heapq.heappop(nodes)
        right = heapq.heappop(nodes)
        parent = HuffmanNode(left.weight + right.weight, left, right)
        heapq.heappush(nodes, parent)
    
    return nodes[0]

最后，我们需要计算哈夫曼树的带权路径长度。遍历树的所有叶子节点，将每个叶子节点的权值乘以其到根节点的距离，然后将所有结果相加即可。代码如下：

def huffman_wpl(root, depth=0):
    """
    Calculate the WPL of a Huffman tree.
    """
    if not root:
        return 0
    
    if not root.left and not root.right:
        return root.weight * depth
    
    return huffman_wpl(root.left, depth+1) + huffman_wpl(root.right, depth+1)

完整代码如下：

import heapq

class HuffmanNode:
    def __init__(self, weight, left=None, right=None):
        self.weight = weight
        self.left = left
        self.right = right

def build_huffman_tree(weights):
    """
    Build a Huffman tree from a list of weights.
    """
    nodes = [HuffmanNode(weight) for weight in weights]
    heapq.heapify(nodes)
    
    while len(nodes) > 1:
        left = heapq.heappop(nodes)
        right = heapq.heappop(nodes)
        parent = HuffmanNode(left.weight + right.weight, left, right)
        heapq.heappush(nodes, parent)
    
    return nodes[0]

def huffman_wpl(root, depth=0):
    """
    Calculate the WPL of a Huffman tree.
    """
    if not root:
        return 0
    
    if not root.left and not root.right:
        return root.weight * depth
    
    return huffman_wpl(root.left, depth+1) + huffman_wpl(root.right, depth+1)

n = int(input())
weights = list(map(int, input().split()))

root = build_huffman_tree(weights)
wpl = huffman_wpl(root)

print(wpl)

这样，我们就可以输入叶子节点个数和权值，输出哈夫曼树的带权路径长度了。

c语言求哈夫曼树的带权路径长度

要求哈夫曼树的带权路径长度，需要先构建哈夫曼树，然后对树中每个叶子节点求出它与根节点的路径长度，再将每个叶子节点的路径长度乘上它的权值，最后把所有叶子节点的乘积相加即可得到带权路径长度。

以下是 C 语言实现哈夫曼树带权路径长度的代码示例：

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

typedef struct node {
    int weight;
    struct node *left;
    struct node *right;
} Node;

typedef struct heap {
    int size;
    int capacity;
    Node **nodes;
} Heap;

Node* create_node(int weight) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->weight = weight;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Heap* create_heap(int capacity) {
    Heap* heap = (Heap*) malloc(sizeof(Heap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->nodes = (Node**) malloc(sizeof(Node*) * capacity);
    return heap;
}

void swap_node(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(Heap *heap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap->size && heap->nodes[left]->weight < heap->nodes[smallest]->weight) {
        smallest = left;
    }
    if (right < heap->size && heap->nodes[right]->weight < heap->nodes[smallest]->weight) {
        smallest = right;
    }
    if (smallest != index) {
        swap_node(&heap->nodes[smallest], &heap->nodes[index]);
        heapify(heap, smallest);
    }
}

void build_heap(Heap *heap) {
    int n = heap->size;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(heap, i);
    }
}

Node* extract_min(Heap *heap) {
    Node* min_node = heap->nodes[0];
    heap->nodes[0] = heap->nodes[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return min_node;
}

void insert(Heap *heap, Node *node) {
    if (heap->size == heap->capacity) {
        printf("Heap is full!\n");
        return;
    }
    heap->size++;
    int i = heap->size - 1;
    while (i > 0 && node->weight < heap->nodes[(i - 1) / 2]->weight) {
        heap->nodes[i] = heap->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    heap->nodes[i] = node;
}

Node* build_huffman_tree(int *weights, int n) {
    Heap* heap = create_heap(n);
    for (int i = 0; i < n; i++) {
        Node* node = create_node(weights[i]);
        insert(heap, node);
    }
    build_heap(heap);
    while (heap->size > 1) {
        Node* left = extract_min(heap);
        Node* right = extract_min(heap);
        Node* parent = create_node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        insert(heap, parent);
    }
    Node* root = extract_min(heap);
    free(heap->nodes);
    free(heap);
    return root;
}

void calculate_wpl(Node* node, int depth, int *wpl) {
    if (node == NULL) {
        return;
    }
    if (node->left == NULL && node->right == NULL) {
        *wpl += node->weight * depth;
        return;
    }
    calculate_wpl(node->left, depth + 1, wpl);
    calculate_wpl(node->right, depth + 1, wpl);
}

int huffman_wpl(int *weights, int n) {
    Node* root = build_huffman_tree(weights, n);
    int wpl = 0;
    calculate_wpl(root, 0, &wpl);
    return wpl;
}

int main() {
    int weights[] = {1, 3, 2, 7, 5};
    int n = sizeof(weights) / sizeof(weights[0]);
    int wpl = huffman_wpl(weights, n);
    printf("Huffman tree WPL = %d\n", wpl);
    return 0;
}

在以上示例中，`build_huffman_tree` 函数用于构建哈夫曼树，`calculate_wpl` 函数用于计算带权路径长度，`huffman_wpl` 函数用于将二者结合起来计算哈夫曼树的带权路径长度。最后，在 `main` 函数中，我们定义了一个权值数组，并调用 `huffman_wpl` 函数计算哈夫曼树的带权路径长度，然后输出结果。