c - 分配二叉树值(霍夫曼编码)

目的是读取文件，计算每个字符的频率并执行霍夫曼编码，其中最常见的字母将是短的二进制代码（即001），最不常见的字母将是较长的二进制代码（即01000100）。

我创建了一个链接列表，其中包含所有字符及其各自频率的排序（升序）列表。这被传递给下面的函数。在此功能中，我旨在添加两个最低频率，并以这种方式构建二叉树，直到树的长度为1。我不确定从这里到哪里去，我知道我必须翻遍树，看看在哪棵树上它向左或向右移动，然后存储0（左）或1（右）。 -但是我不知道如何建立一个功能来做到这一点！

void traverse_list(pqueue *list)
    {
    char letters[CHARACTERS] = { 0 };
    int frequencies[CHARACTERS] = { 0 };
    int j = 0, l = 0, len = 0;
    node *temp = list->head;
    tree *array[CHARACTERS];
    while (temp != NULL)
    {
        letters[j] = temp->letter;
        frequencies[j] = temp -> frequency;
        temp = temp->next;
        j++;
    }
    for (l = 0; l < CHARACTERS; l++)
    {
        if (frequencies[j])
        {
            tree* huffman = calloc(1, sizeof(tree));
            huffman -> letter = letters[l];
            huffman -> frequency = frequencies[l];
            array[len++] = huffman;
        }
    }

    while (len > 1)
    {
        tree* huffman = malloc(sizeof(tree));
        huffman -> left = array[len--];
        huffman -> right = array[len--];
        huffman -> frequency = huffman -> left -> frequency + huffman -> right -> frequency;
        array[len++] = huffman;
    }
}

为了便于阅读，结构如下所示：

typedef struct Node
{
    char letter;
    int frequency;
    struct Node *next;

}node;

typedef struct pqueue
{
    node *head;

}pqueue;

typedef struct tree
{
    struct tree *left;
    struct tree *right;
    char letter;
    int frequency;
}tree;

最佳答案

我不明白为什么您创建了如此多的数组，然后使用它们再次创建新的节点。我认为可以通过修改Node的结构轻松完成此操作。像这样的东西::

typedef struct Node
{
    char letter;
    int frequency;
    struct Node *next;
    struct Node *left, *right;
}node;

因此，您可以执行以下操作来形成树。

void huffman(plist *list) {
    while(1) {
        node *left = list->head;
        list->head = list->head->next;
        node *right = list->head;
        list->head = list->head->next;

        node *huffman = malloc(sizeof(node));
        huffman->frequency = left->frequency;
        huffman->left = left;
        huffman->right = right;
        huffman->next = NULL;

        if(list->head == NULL) {
            list->head = huffman;
            break;
        }
        insertHuffman(root, huffman);
    }
}

您的insertHuffman()只需按排序顺序将新的node插入pList中。因此，最后在树中只剩下一个node，然后您可以简单地遍历以确定每个节点上的值。您绝对可以选择比我使用的while(1)更好的条件！：P我之所以使用它，是因为这是我想到的第一件事。我相信您肯定可以写insertHuffman()。

编辑：：

void printHuffman(node *head, node *parent, char *a, int len) {
    if(head->left == NULL && head->right == NULL) {
        if(parent != NULL && parent->right == head) {
            cout << head->letter << " " << a << "1";
        } else if(parent != NULL && parent->left == head) {
            cout << head->letter << " " << a;
        }
    } else {
        a[len] = '0';
        printHuffman(head->left, head, a, len + 1);
        a[len] = '1';
        printHuffman(head->right, head, a, len + 1);
    }
}

我认为这将打印每个字符的霍夫曼值。

在这里，a是大小为CHARACTERS的字符数组，并且所有初始化为\0的值和len都保存当前代码的值。

编辑2 ::

我已经看到了您尝试将字符tree节点组合为1个tree节点的方法，方法是从升序排序的数组中取出最后两个节点，并将它们组合成一个新的节点，该节点放在数组的末尾。就我对霍夫曼编码的了解而言，您没有将元素与最大频率组合在一起，而是将具有最低频率的元素组合在一起，然后形成了用于查找霍夫曼编码的树。

关于c - 分配二叉树值(霍夫曼编码)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34136730/