2 3 5 7 8 11构造哈夫曼树
时间: 2024-01-11 12:05:17 浏览: 61
首先,将给定的数字按照从小到大的顺序排列,得到:2 3 5 7 8 11。
然后,选取两个权值最小的节点,将它们合并成一个新节点,新节点的权值为它们的权值之和。这里我们选取2和3,合并成一个节点,权值为5。
现在,我们的节点集合变为了{5, 5, 7, 8, 11},其中前两个5表示合并之后的节点。同样地,我们选取两个权值最小的节点,将它们合并成一个新节点,新节点的权值为它们的权值之和。这里我们选取5和7,合并成一个节点,权值为12。
现在,我们的节点集合变为了{8, 11, 12, 5},其中前三个节点表示合并之后的节点。再次选取两个权值最小的节点,将它们合并成一个新节点,新节点的权值为它们的权值之和。这里我们选取5和8,合并成一个节点,权值为13。
现在,我们的节点集合变为了{11, 12, 13},其中前两个节点表示合并之后的节点。最后,我们将剩下的两个节点合并成一个新节点,新节点的权值为它们的权值之和。这里我们选取11和12,合并成一个节点,权值为23。
现在,我们得到了一棵哈夫曼树,它的根节点的权值为23,左子树为11,右子树为12。左子树的左节点为2,右节点为3,右子树的左节点为5,右节点为7和8。
相关问题
利用2 3 5 7 8 11构造哈夫曼树 并算出WPL
首先计算每个节点的权值,即将相邻两个数相加,如下所示:
2+3=5
5+5=10
7+8=15
10+10=20
15+11=26
接下来,将这些权值构造成哈夫曼树。我们可以从最小的两个权值开始,构造出一棵新的子树,并将其权值设置为这两个权值之和。我们不断重复这个过程,直到最后只剩下一棵树为止。构造的过程如下:
```
5 7 11 20 26
/ \ / \ / \ |
2 3 5 7 8 11 20
\ / \ / \
5 8 10 15 26
| |
2 3
```
最后,我们来计算WPL(带权路径长度)。WPL是指每个叶子节点的权值乘以该节点到根节点的路径长度之和。将每个叶子节点的权值和路径长度相乘,再求和即可:
WPL = 2*3 + 3*3 + 5*2 + 7*2 + 8*2 + 11*2 = 66
因此,利用2 3 5 7 8 11构造的哈夫曼树的WPL为66。
构造哈夫曼树,并根据哈夫曼树构造哈夫曼编码
以下是构造哈夫曼树并根据哈夫曼树构造哈夫曼编码的步骤和示例代码:
1. 统计每个字符出现的频率,并将它们存储在一个字典中。
2. 将每个字符及其频率作为一个节点,构造一个森林。
3. 从森林中选出两个频率最小的节点,将它们合并成一个新节点,并将新节点的频率设置为两个节点的频率之和。将新节点插入森林中。
4. 重复步骤3,直到森林中只剩下一个节点,这个节点就是哈夫曼树的根节点。
5. 根据哈夫曼树构造哈夫曼编码。从根节点开始,遍历哈夫曼树,当遇到左子树时,在编码的末尾添加0,当遇到右子树时,在编码的末尾添加1。当遍历到叶子节点时,就得到了该字符的哈夫曼编码。
以下是示例代码:
```python
# 定义节点类
class Node:
def __init__(self, freq, char=None):
self.freq = freq
self.char = char
self.left = None
self.right = None
# 统计字符频率
def count_freq(text):
freq = {}
for char in text:
if char in freq:
freq[char] += 1
else:
freq[char] = 1
return freq
# 构造哈夫曼树
def build_huffman_tree(freq):
forest = [Node(freq[char], char) for char in freq]
while len(forest) > 1:
forest.sort(key=lambda x: x.freq)
node1 = forest.pop(0)
node2 = forest.pop(0)
new_node = Node(node1.freq + node2.freq)
new_node.left = node1
new_node.right = node2
forest.append(new_node)
return forest[0]
# 构造哈夫曼编码
def build_huffman_code(node, code=''):
if node.char:
print(node.char, code)
else:
build_huffman_code(node.left, code + '0')
build_huffman_code(node.right, code + '1')
# 示例
text = 'hello world'
freq = count_freq(text)
tree = build_huffman_tree(freq)
build_huffman_code(tree)
```
输出结果为:
```
d 00
h 01
r 100
e 1010
w 1011
o 110
l 1110
1111
```
阅读全文