首页写出“给定n个节点，每个节点的权重w(i)（1≤i≤n），构造一颗哈夫曼树，并输出带权路径长度”的代码

写出“给定n个节点，每个节点的权重w(i)（1≤i≤n），构造一颗哈夫曼树，并输出带权路径长度”的代码

时间: 2024-12-17 20:55:20 浏览: 32

构建哈夫曼树并计算带权路径长度通常涉及到优先队列的数据结构以及贪心算法。这里是一个简单的Python代码示例，使用了`heapq`库来实现最小堆： ```python import heapq def build_huffman_tree(weights): # 将权重转换为键值对，存储在堆中 heap = [(weight, index) for index, weight in enumerate(weights)] while len(heap) > 1: # 从堆中取出两个最小的元素（带权） min1, min1_index = heapq.heappop(heap) min2, min2_index = heapq.heappop(heap) # 创建一个新的节点，包含这两个节点 new_node = (min1 + min2, [min1_index, min2_index]) # 把新节点放回堆中 heapq.heappush(heap, new_node) # 最后的单个节点就是哈夫曼树的根 return heap[0][1] # 返回整个树 def huffman_path_length(tree, weights): def dfs(node, path_weight=0): if isinstance(node, int): # 如果是叶子节点，返回其权重 return weights[node] else: left_weight = dfs(node[0], path_weight) right_weight = dfs(node[1], path_weight + left_weight) return left_weight + right_weight # 计算带权路径长度 return dfs(tree) # 示例用法 weights = [10, 5, 15, 8, 6] # 节点权重列表 huffman_tree = build_huffman_tree(weights) path_length = huffman_path_length(huffman_tree, weights) print(f"哈夫曼树的带权路径长度为: {path_length}")

阅读全文