使用5 29 7 8 14 23 3 11 构建哈夫曼树,输出这些数字对应的子低向上哈夫曼编码
时间: 2023-06-09 20:07:54 浏览: 103
好的,根据给出的数字构建哈夫曼树,可以得到以下的树结构:
68
/ \
24 44
/ \ / \
12 12 20 24
/\ /\ /\ /\
5 7 8 4 14 6 17 7
对于每个数字对应的编码,可以采用以下的方式进行计算:
- 5:向左子树走一步,得到编码 0
- 7:向左子树走一步,然后向左子树走一步,得到编码 00
- 8:向左子树走一步,然后向右子树走一步,得到编码 01
- 14:向右子树走一步,然后向左子树走一步,得到编码 10
- 23:向右子树走一步,然后向右子树走一步,得到编码 11
- 3:向左子树走一步,然后向左子树走一步,然后向左子树走一步,得到编码 000
- 11:向左子树走一步,然后向左子树走一步,然后向右子树走一步,得到编码 001
因此,这些数字对应的子低向上哈夫曼编码是:
5:0
7:00
8:01
14:10
23:11
3:000
11:001
相关问题
掌握哈夫曼树、哈夫曼编码的概念和基本理论,设计实现哈夫曼编码
哈夫曼树是一种小根堆,它的每个节点都有一个权值,哈夫曼树的根节点距离其它叶子节点最远,因此可以用于构建最优二进制编码。
构建哈夫曼编码的过程如下:
1. 统计字符的出现频率,并按照从小到大的顺序构建哈夫曼树。
2. 对于哈夫曼树中的每个叶子节点,将其对应的字符编码为0,向上遍历到根节点,左儿子对应的编码为0,右儿子对应的编码为1。
3. 遍历待编码的字符串,根据哈夫曼树的编码规则将每个字符编码成二进制数。
4. 将所有编码后的二进制数拼接起来即为哈夫曼编码。
下面是Python实现哈夫曼编码的示例代码:
```python
import heapq
from collections import defaultdict
def huffman_encoding(data):
freq = defaultdict(int)
for c in data:
freq[c] += 1
heap = [[wt, [sym, '']] for sym, wt in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
huff_code = dict(heapq.heappop(heap)[1:])
encoded_data = ''.join([huff_code[c] for c in data])
return encoded_data, huff_code
def huffman_decoding(encoded_data, huff_code):
inv_huff_code = {v: k for k, v in huff_code.items()}
decoded_data = ''
i = 0
while i < len(encoded_data):
j = i + 1
while encoded_data[i:j] not in inv_huff_code:
j += 1
decoded_data += inv_huff_code[encoded_data[i:j]]
i = j
return decoded_data
if __name__ == '__main__':
data = 'hello world'
encoded_data, huff_code = huffman_encoding(data)
decoded_data = huffman_decoding(encoded_data, huff_code)
print(encoded_data) # 100011011001110110101001011010000
print(decoded_data) # hello world
```
在上面的代码中,我们首先使用`defaultdict`统计字符出现频率,并将其存储在堆中。然后我们使用循环从堆中弹出两个最小的元素,合并它们并将它们放回堆中的过程,直到堆中只有一个元素。在这个过程中,我们将左儿子赋值为0,右儿子赋值为1,并将哈夫曼编码存储在一个字典中。最后,我们将编码后的二进制数拼接起来并返回哈夫曼编码。
对于解码过程,我们只需要将哈夫曼编码反转并存储在另一个字典中,然后遍历编码后的二进制数并查找对应的字符即可。
给定一组结点及对应的权值,创建一棵哈夫曼树,输出每个结点的哈夫曼编码,和整棵树的WPL值。用c++实现
以下是C语言实现哈夫曼树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE_NUM 1000
#define MAX_CODE_LEN 100
struct Node {
int weight;
int parent;
int lchild;
int rchild;
};
void create_huffman_tree(struct Node* nodes, int n);
void get_huffman_code(struct Node* nodes, int n, char (*code)[MAX_CODE_LEN], int* wpl);
void print_huffman_code(struct Node* nodes, char (*code)[MAX_CODE_LEN], int n, int wpl);
int main() {
int n;
struct Node nodes[MAX_NODE_NUM];
char code[MAX_NODE_NUM][MAX_CODE_LEN];
int wpl;
printf("请输入结点个数:");
scanf("%d", &n);
printf("请输入每个结点的权值:");
for (int i = 0; i < n; i++) {
scanf("%d", &nodes[i].weight);
nodes[i].parent = -1;
nodes[i].lchild = -1;
nodes[i].rchild = -1;
}
create_huffman_tree(nodes, n);
get_huffman_code(nodes, n, code, &wpl);
print_huffman_code(nodes, code, n, wpl);
return 0;
}
void create_huffman_tree(struct Node* nodes, int n) {
for (int i = 0; i < n - 1; i++) {
int min1 = -1, min2 = -1;
for (int j = 0; j < n; j++) {
if (nodes[j].parent == -1) {
if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
min2 = j;
}
}
}
nodes[min1].parent = n + i;
nodes[min2].parent = n + i;
nodes[n + i].weight = nodes[min1].weight + nodes[min2].weight;
nodes[n + i].lchild = min1;
nodes[n + i].rchild = min2;
}
}
void get_huffman_code(struct Node* nodes, int n, char (*code)[MAX_CODE_LEN], int* wpl) {
*wpl = 0;
for (int i = 0; i < n; i++) {
int p = nodes[i].parent;
int len = 0;
while (p != -1) {
if (nodes[p].lchild == i) {
code[i][len++] = '0';
} else {
code[i][len++] = '1';
}
p = nodes[p].parent;
}
code[i][len] = '\0';
*wpl += nodes[i].weight * len;
}
}
void print_huffman_code(struct Node* nodes, char (*code)[MAX_CODE_LEN], int n, int wpl) {
printf("哈夫曼编码为:\n");
for (int i = 0; i < n; i++) {
printf("%d: %s\n", nodes[i].weight, code[i]);
}
printf("WPL = %d\n", wpl);
}
```
在这个代码中,我们首先定义了一个 `Node` 结构体来表示哈夫曼树中的结点。其中,`weight` 表示结点的权值,`parent` 表示结点的父节点在数组中的下标,`lchild` 和 `rchild` 分别表示结点的左右子节点在数组中的下标。我们还定义了两个常量,`MAX_NODE_NUM` 表示最大结点数,`MAX_CODE_LEN` 表示哈夫曼编码的最大长度。
在 `main` 函数中,我们首先读入结点个数和每个结点的权值,并初始化每个结点的 `parent`、`lchild` 和 `rchild` 为 -1。然后调用 `create_huffman_tree` 函数创建哈夫曼树,调用 `get_huffman_code` 函数获取每个结点的哈夫曼编码和整棵树的 WPL 值,最后调用 `print_huffman_code` 函数输出结果。
`create_huffman_tree` 函数通过贪心策略构建哈夫曼树。具体来说,它每次从未被选择过的结点中选出权值最小的两个结点,将它们合并为一个新的结点,并将新结点的权值设为它们的权值之和,左右子节点分别为这两个结点。重复这个过程,直到所有结点都被合并成了一个根节点为止。
`get_huffman_code` 函数通过遍历哈夫曼树获取每个结点的哈夫曼编码,并计算整棵树的 WPL 值。具体来说,它对于每个结点,从它的父节点开始向上遍历,若当前结点是父节点的左子节点,则在编码字符串末尾添加一个 0,否则添加一个 1。重复这个过程,直到遍历到根节点为止。最后,将编码字符串翻转并存储到 `code` 数组中,同时累加每个结点的权值乘以编码长度,即为整棵树的 WPL 值。
`print_huffman_code` 函数将每个结点的权值和哈夫曼编码输出到屏幕上,并输出整棵树的 WPL 值。