假设用于通信的电文仅由 8 个字母(ABCDEFGH)组成 , 字母在电文中出现的频率分别为 0.07 , 0.19 , 0.02 , 0.06 , 0.32 , 0.03 , 0.21 ,画出哈夫曼树

首先按照概率从小到大排列，得到以下序列：

C: 0.02
F: 0.03
A: 0.07
D: 0.06
B: 0.19
H: 0.21
G: 0.32

接下来构建哈夫曼树：

首先选取概率最小的两个节点 C 和 F，构建一个新节点 CF，权重为 0.05。

接着选取概率最小的两个节点 A 和 D，构建一个新节点 AD，权重为 0.13。

再选取概率最小的两个节点 CF 和 AD，构建一个新节点 CFAD，权重为 0.18。

接着选取概率最小的两个节点 B 和 H，构建一个新节点 BH，权重为 0.4。

最后选取概率最小的两个节点 CFAD 和 BH，构建一个新节点 CFADBH，权重为 0.58。

哈夫曼树如下图所示：

        CFADBH
         /    \
    CFAD      BH
     / \      / \
    CF  AD   B   H
   / \
  C   F

每个字母的哈夫曼编码：

C: 0000
F: 0001
A: 01
D: 10
B: 11 0
H: 11 1
G: 11 01

其中，每个字母的二进制编码即为其在哈夫曼树上从根节点到叶子节点的路径编码，向左走为 0，向右走为 1。

相关问题

假设用于通信的电文仅由8个字母abcdefgh 组成，字母在电文中出现的频率分别为5，29，7，8，14，23，3，11 试画出哈夫曼树，给出个字符编码值，求出平均码长

先根据出现频率构建哈夫曼树：


从根节点开始，左子树路径上的编码为0，右子树路径上的编码为1，则每个字符的编码值为：

- a: 1111
- b: 00
- c: 1101
- d: 1100
- e: 10
- f: 01
- g: 11100
- h: 11101

平均码长 = Σ(每个字符出现的频率 * 对应编码长度) = (5*4 + 29*2 + 7*4 + 8*4 + 14*2 + 23*2 + 3*5 + 11*5) / 100 = 2.45 个比特。

数据结构，用于通讯的电文仅由8个字母组成，分别为A、B、C、D、E、F、G、H，出现的频数分别为7、19、2、6、32、3、21、10。数据结构c语言编写程序给出这8个字母的哈夫曼编码，并输出EGGFACAFEDEGH对应的编码。

在C语言中，我们可以使用二叉树（尤其是哈夫曼树）的数据结构来构建哈夫曼编码。哈夫曼编码是一种自定义的前缀编码，它的构建过程通常涉及创建一个最小带权路径长度的二叉树。这里是一个简单的步骤：

1. 对每个字母计算其频率，然后创建一个频率数组或链表。
2. 使用优先队列（如二叉堆）生成哈夫曼树，每次从频率最低的两个节点合并成一个新的节点，新节点的频率为两者之和，用较短的字符作为左子节点，较长的字符作为右子节点。
3. 重复此过程直到只剩下一个节点，即为哈夫曼树的根节点。
4. 根据构建过程，确定每个字符的路径编码，从根节点开始，沿着左右分支交替走，遇到叶子节点时停止。

以下是一个简化的C语言程序，用于生成哈夫曼编码并输出给定字符串的编码。请注意，这个示例假设了哈夫曼树已经手动构造完成，因为生成完整的哈夫曼树并遍历的过程可能相当复杂。

#include <stdio.h>
#include <stdlib.h>

// 哈夫曼树节点结构体
typedef struct {
    char letter;
    int freq;
    struct Node *left, *right;
} Node;

// 初始化空节点
Node* newNode(char c, int f) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->letter = c;
    node->freq = f;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 求两节点合并后的哈夫曼编码
char combineCodes(Node* left, Node* right) {
    if (left == NULL || right == NULL)
        return left->letter; // 如果有一个为空，直接返回另一个

    if (left->freq < right->freq)
        return combineCodes(left, right->left);
    else
        return combineCodes(left->right, right);
}

int main() {
    const char* letters = "ABCDEFGH";
    int freqs[] = {7, 19, 2, 6, 32, 3, 21, 10};
    Node* root = NULL;

    for (int i = 0; i < sizeof(freqs) / sizeof(freqs[0]); i++) {
        Node* newNode = newNode(letters[i], freqs[i]);
        if (root == NULL)
            root = newNode;
        else {
            Node* queue[2] = {root, newNode};
            while (queue[0] != NULL && queue[1] != NULL) {
                Node* parent = queue[0];
                queue[0] = queue[0]->freq < queue[1]->freq ? queue[0]->right : queue[0]->left;
                queue[1] = queue[1]->freq < parent->freq ? queue[1]->right : queue[1]->left;
                parent->left = queue[0];
                parent->right = queue[1];
            }
        }
    }

    char encodedString[] = "EGGFACAFEDEGH"; // 输入字符串
    for (const char c : encodedString) {
        printf("%c:", c);
        Node* current = root;
        while (current != NULL && current->letter != c)
            current = current->left ? current->left : current->right;
        printf("%c", combineCodes(current->left, current->right)); // 输出当前字符的编码
    }
    printf("\n");

    return 0;
}

在这个例子中，`main`函数首先构建了哈夫曼树，然后遍历给定的编码字符串，根据编码规则输出每个字符的编码。