假设用于通信的电文仅由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 个字母(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。

编写一个实验程序，假定用于通信的电文仅由a、b、c、d、e、f、g、h等8个字母组成(no=8），字母在电文中出现的频率分别为7、19、2、6、32、3、21和10，试为这些字母设计哈夫曼编码。要求：完成哈夫曼编码设计后，转向90度打印此哈夫曼树，要求使用c++

为了编写一个C++程序，我们首先需要创建一个哈夫曼树结构，并实现构建哈夫曼树和生成编码的功能。这里是一个简单的示例：

#include <iostream>
#include <queue>
#include <unordered_map>

// 定义节点结构
struct Node {
    char data;
    int freq;
    Node* left;
    Node* right;
};

// 插入节点到堆中
Node* insert(Node** root, char data, int freq) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->freq = freq;
    newNode->left = nullptr;
    newNode->right = nullptr;

    if (*root == nullptr) {
        *root = newNode;
    } else {
        Node* current = *root;
        while (true) {
            if (freq < current->freq) {
                if (current->left == nullptr) {
                    current->left = newNode;
                    break;
                } else {
                    current = current->left;
                }
            } else {
                if (current->right == nullptr) {
                    current->right = newNode;
                    break;
                } else {
                    current = current->right;
                }
            }
        }
    }

    return *root;
}

// 哈夫曼树构造函数
void buildHuffmanTree(Node** root, std::unordered_map<char, Node*>& huffmanMap) {
    std::priority_queue<Node*, std::vector<Node*>, std::greater<Node*>> heap(*root);

    // 构建并合并哈夫曼树
    while (heap.size() > 1) {
        Node* left = heap.top(); heap.pop();
        Node* right = heap.top(); heap.pop();

        Node* newNode = new Node();
        newNode->freq = left->freq + right->freq;
        newNode->left = left;
        newNode->right = right;
        heap.push(newNode);
        
        huffmanMap[left->data] = left;
        huffmanMap[right->data] = right;
    }

    *root = heap.top();  // 最终的哈夫曼树根节点
}

// 计算编码
std::string getHuffmanCode(Node* node, std::string code) {
    if (node->left != nullptr) {
        getHuffmanCode(node->left, code + "0");
    } else {
        getHuffmanCode(node->right, code + "1");
    }

    return node->data ? code : "";
}

int main() {
    const char* letters = "abcdefgh";
    int frequencies[] = {7, 19, 2, 6, 32, 3, 21, 10};
    int no = sizeof(frequencies) / sizeof(frequencies[0]);

    std::unordered_map<char, Node*> huffmanMap;
    Node* root = nullptr;

    for (int i = 0; i < no; ++i) {
        insert(&root, letters[i], frequencies[i]);
    }

    buildHuffmanTree(&root, huffmanMap);

    // 转向90度打印哈夫曼树
    // 这里由于C++控制台打印限制，无法直接按照90度的方式显示。你可以选择将哈夫曼树结果保存到文件或图形界面展示。

    // 打印编码
    for (const auto& pair : huffmanMap) {
        std::cout << "Character: " << pair.first << ", Huffman Code: " << getHuffmanCode(pair.second, "") << "\n";
    }

    return 0;
}

这个程序首先初始化一个空的哈夫曼树，然后通过插入节点和优先队列合并形成最终的哈夫曼树。`getHuffmanCode`函数用于递归地计算每个字符的编码。请注意，实际的90度打印功能通常不在文本控制台上实现，因为这超出了标准输出范围。你可以考虑将哈夫曼树的结果导出到其他可视化工具或文件中。