构造哈夫曼树数据结构
时间: 2023-12-04 20:39:54 浏览: 49
哈夫曼树是一种带权路径长度最短的树,也称为最优二叉树。构造哈夫曼树的过程是将权值从小到大排序,然后每次取出权值最小的两个节点,合并成一个新节点,新节点的权值为两个节点的权值之和,直到所有节点都被合并成一个根节点为止。下面是构造哈夫曼树的具体步骤:
1. 将所有节点按照权值从小到大排序,得到一个节点集合。
2. 取出权值最小的两个节点,合并成一个新节点,新节点的权值为两个节点的权值之和。
3. 将新节点插入到节点集合中,并从集合中删除原来的两个节点。
4. 重复步骤2和3,直到节点集合中只剩下一个节点,即为哈夫曼树的根节点。
下面是一个Python实现的例子:
```python
class Node:
def __init__(self, weight):
self.weight = weight
self.left = None
self.right = None
def build_huffman_tree(weights):
nodes = [Node(weight) for weight in weights]
while len(nodes) > 1:
nodes.sort(key=lambda x: x.weight)
left = nodes.pop(0)
right = nodes.pop(0)
parent = Node(left.weight + right.weight)
parent.left = left
parent.right = right
nodes.append(parent)
return nodes[0]
```
其中,Node类表示哈夫曼树的节点,weight属性表示节点的权值,left和right属性分别表示节点的左右子节点。build_huffman_tree函数接受一个权值列表作为参数,返回构造好的哈夫曼树的根节点。