c - 如何生成霍夫曼树的二进制代码表？

Question

我想实现一个函数，为霍夫曼树中的每个字符提供一个二进制代码。

为了实现该功能，我尝试使用递归函数遍历表格。但是我不知道如何将结果填充为每个字符的二进制代码，以便函数返回一个包含所有字符和二进制代码的结构数组

我希望有人能指出我正确的方向。

提前致谢!

Answer 1

好的，让我们看看可能的解决方案:

#include <stdint.h>

typedef struct code {
    size_t code_length;
    uint32_t code;
} code;

void compute_code_table(tree_t node, code *t, code c) 
{
    if (node->left == NULL) 
        t[node->letter] = c;
    else {
        c.code_length++;
        c.code <<= 1;
        compute_code_table(node->left, t, c);
        c.code += 1;
        compute_code_table(node->right, t, c);
    }
}

void code_print(code *c)
{
    size_t n = c->code_length;
    while (n --> 0)
        putchar('0' + ((c->code >> n) & 1));
}

int main(void)
{
    tree_t root = fixed_tree();
    code table[256] = { 0 };
    code c = { 0 };
    compute_code_table(root, table, c);

    for (size_t i = 0; i < 256; ++i) {
        if (table[i].code_length) {
            printf("%c\t", i);
            code_print(table + i);
            printf("\n");
        }
    }
}

基本上，这个想法是有一个表格，每个叶子都被填满。在执行递归时，我们传递当前节点、表和当前代码。如果我们在叶子上，我们只将代码存储在表中，否则我们需要执行递归:增加代码长度，在最低有效位添加 0 并执行左分支，然后将该 0 更改为 1 和做正确的分支。