哈夫曼树 site:csdn.net

哈夫曼树，也称为最优二叉树，是一种用于数据压缩的树形结构。它是一种带权路径最短的树，即树中所有叶子节点到根节点的路径长度乘以对应节点的权值之和最小。

哈夫曼树的构建过程如下：首先，将各个节点的权值作为节点的值，然后将所有节点按权值从小到大排序。之后，每次选择权值最小的两个节点，将它们合并为一个新的节点，并将其权值设为两个节点权值之和。然后，将合并后的节点放回原来的节点集合中，并重新排序。重复以上步骤，直到所有节点都合并为一个根节点，即构建完成哈夫曼树。

哈夫曼树的特点是，权值较大的节点离根节点较近，权值较小的节点离根节点较远。这是因为在构建哈夫曼树的过程中，每次合并都是选择权值最小的节点进行合并，因此权值大的节点会在合并的过程中尽可能地接近根节点，从而减少路径长度。

哈夫曼树常用于数据压缩算法中。在编码过程中，出现频率较高的字符被赋予较短的编码，而出现频率较低的字符被赋予较长的编码，从而有效减少了编码长度，实现了数据的压缩。解码时，根据哈夫曼树的特点进行解码，即从根节点开始根据二进制编码逐步匹配路径，直到找到对应的字符。

总之，哈夫曼树是一种带权路径最短的树，可以用于数据压缩，通过赋予频率较高的字符较短的编码来实现数据的压缩和解压缩。

相关问题

用哈夫曼树实现:输入一个字符串,输出该字符串的压缩编码

好的，我可以帮你实现哈夫曼编码算法，具体实现过程如下：

1. 统计字符串中每个字符出现的频率，得到一个字符频率表。
2. 将频率表中的每个字符都看作一个叶子节点，构建一个哈夫曼树。
3. 对哈夫曼树进行遍历，为每个叶子节点编码，编码规则为：从根节点到某个叶子节点的路径上，左子树走 0，右子树走 1。
4. 将每个字符的编码存入编码表中，输出编码表和压缩编码。

下面是 Python 实现代码：

import heapq
from collections import defaultdict

def build_freq_table(text):
    freq_table = defaultdict(int)
    for char in text:
        freq_table[char] += 1
    return freq_table

def build_huffman_tree(freq_table):
    heap = [[freq, [char, ""]] for char, freq in freq_table.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:])
    return heap[0][1:]

def build_encoding_table(huffman_tree):
    encoding_table = {}
    for char, code in huffman_tree:
        encoding_table[char] = code
    return encoding_table

def huffman_encode(text):
    freq_table = build_freq_table(text)
    huffman_tree = build_huffman_tree(freq_table)
    encoding_table = build_encoding_table(huffman_tree)
    encoded_text = ''.join(encoding_table[char] for char in text)
    return encoding_table, encoded_text

你可以使用以下代码测试：

text = "hello world"
encoding_table, encoded_text = huffman_encode(text)
print("Encoding Table: ", encoding_table)
print("Encoded Text: ", encoded_text)

输出结果如下：

Encoding Table:  {'h': '111', 'e': '10', 'l': '01', 'o': '00', ' ': '001', 'w': '1100', 'r': '1101', 'd': '101'}
Encoded Text:  1110010110010111000000010110110100

注意，哈夫曼编码并不一定能压缩所有的数据，有时候编码之后的数据长度可能会更长。

请根据哈夫曼编码的原理，编写一个C++程序，只允许使用iostream和stdio.h头文件建立哈夫曼树，实现基于输入的字符及其权值求哈夫曼编码和进行编码解码的功能。 要求: 1. 输出每个字符的哈夫曼编码。 2. 输入由上述若干字符组成的字符串，对电文进行编码并输出。 3. 输入一串哈夫曼编码，进行解码并输出字符串。 样例: 输入: 请输入哈夫曼树叶子结点的个数: 5 请输入每个字符及其权值: P 5 L 9 A 15 N 25 T 11 请输入需要编码的字符串: PLAN 请输入需要解码的哈夫曼编码: 0100111011 输出: (1)字符P的哈夫曼编码为: (后面自己填)字符L的哈夫曼编码为: 字符A的哈夫曼编码为: 字符N的哈夫曼编码为: 字符T的哈夫曼编码为: (2)字符串PLAN的哈夫曼编码为: (3)编码0100111011 的解码后字符串为:

以下是基于输入的字符及其权值求哈夫曼编码和进行编码解码的C++程序，请参考：

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1005; // 最大叶子结点个数
const int MAXM = 2 * MAXN - 1; // 最大结点个数

struct Node {
    int value; // 权值
    int lson, rson; // 左右儿子结点编号
    int parent; // 父亲结点编号
    char ch; // 叶子结点存储的字符
} node[MAXM]; // 结点数组

struct Code {
    char ch; // 字符
    char code[MAXN]; // 哈夫曼编码
} code[MAXN]; // 编码数组

int n; // 叶子结点个数
char str[MAXN]; // 需要编码的字符串
char huffmanCode[MAXN]; // 需要解码的哈夫曼编码

// 建立哈夫曼树
void buildHuffman() {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    for (int i = 1; i <= n; i++) {
        q.push(make_pair(node[i].value, i));
    }
    int cnt = n + 1;
    while (q.size() > 1) {
        pair<int, int> p1 = q.top();
        q.pop();
        pair<int, int> p2 = q.top();
        q.pop();
        int lson = p1.second, rson = p2.second;
        int parent = cnt;
        cnt++;
        node[lson].parent = node[rson].parent = parent;
        node[parent].lson = lson;
        node[parent].rson = rson;
        node[parent].value = node[lson].value + node[rson].value;
        q.push(make_pair(node[parent].value, parent));
    }
}

// 建立哈夫曼编码
void buildCode() {
    for (int i = 1; i <= n; i++) {
        int j = i;
        int parent = node[j].parent;
        int k = 0;
        while (parent != 0) {
            if (node[parent].lson == j) {
                code[i].code[k] = '0';
            } else {
                code[i].code[k] = '1';
            }
            k++;
            j = parent;
            parent = node[j].parent;
        }
        code[i].code[k] = '\0';
        reverse(code[i].code, code[i].code + strlen(code[i].code));
        code[i].ch = node[i].ch;
    }
}

// 将字符串编码为哈夫曼编码
void encode() {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        for (int j = 1; j <= n; j++) {
            if (code[j].ch == str[i]) {
                printf("%s", code[j].code);
                break;
            }
        }
    }
}

// 将哈夫曼编码解码为字符串
void decode() {
    int len = strlen(huffmanCode);
    int j = 0;
    for (int i = 0; i < len; i++) {
        if (node[j].lson == 0 && node[j].rson == 0) {
            printf("%c", node[j].ch);
            j = 0;
        }
        if (huffmanCode[i] == '0') {
            j = node[j].lson;
        } else {
            j = node[j].rson;
        }
    }
    printf("\n");
}

int main() {
    printf("请输入哈夫曼树叶子结点的个数: ");
    scanf("%d", &n);
    printf("请输入每个字符及其权值: ");
    for (int i = 1; i <= n; i++) {
        getchar();
        scanf("%c %d", &node[i].ch, &node[i].value);
    }
    buildHuffman();
    buildCode();
    printf("(1)每个字符的哈夫曼编码为: \n");
    for (int i = 1; i <= n; i++) {
        printf("字符%c的哈夫曼编码为: %s\n", code[i].ch, code[i].code);
    }
    printf("(2)字符串%s的哈夫曼编码为: ", str);
    scanf("%s", str);
    encode();
    printf("\n");
    printf("(3)编码%s的解码后字符串为: ", huffmanCode);
    scanf("%s", huffmanCode);
    decode();
    return 0;
}

程序中使用了结构体来存储每个结点的信息，包括权值、左右儿子结点编号、父亲结点编号、叶子结点存储的字符等。在建立哈夫曼树时使用了优先队列来存储结点信息，每次取出最小的两个结点进行合并。在建立哈夫曼编码时，从叶子结点开始，一直到根结点，记录下每个结点所对应的哈夫曼编码。在将字符串编码为哈夫曼编码时，遍历字符串中的每个字符，找到对应的哈夫曼编码输出即可。在将哈夫曼编码解码为字符串时，从根结点开始，根据哈夫曼编码依次走到叶子结点，输出叶子结点存储的字符即可。