c - 插入哈夫曼树

Question

我的霍夫曼树有问题；当我尝试构建它时，我将节点放在了错误的位置。例如，我希望权重为 2 的节点(带有子节点 i:1 和 n:1)位于 m:2 和 space:3 的节点之间，但它正好位于我放入的前一个节点 (2与 e:1 和 g:1 的 child )。

我的问题是:如何根据其权重(也称为其两个子节点的总和)和子节点的符号(即右 child “n”出现在“g”的另一个右 child 之前)。

感谢您的帮助!

编辑:另外，我如何按字母顺序打印树的代码；现在我让它们从最右边的树到最左边打印

这是我的插入函数...

    struct node* insert(struct node* head, struct node* temp)

    {

    struct node* previous = NULL;

    struct node* current = head;



     printf("entering insert function\n");



    // finds the previous node, where we want to insert new node

   while (temp->freq > current->freq && current->next != NULL)

  {

     printf("traversing: tempfreq is %lu and currentfreq is %lu\n", temp->freq, current->freq);
     previous = current;

    current = current->next;

   }

   if (current->next == NULL)

   {

    printf("hit end of list\n");

    temp = current->next;

   }

  else

  {

printf("inserting into list\n");

temp->next = current;

previous->next = temp;

  }  

  return head;

 }

Answer 1

当您到达列表末尾时，插入错误。这:

temp = current->next;

应该反过来，否则您只需将 NULL 分配给临时变量，这不会对您的列表执行任何操作。

但我认为你也弄错了你的特殊情况。特殊情况不是“在末尾插入”，而是“插入新头”。如果head == NULL，你的代码将会失败。 (这可能不会发生，因为您已经有了一个没有子节点的节点列表，并且您删除了节点，直到只剩下一个节点，但仍然如此。)

因此，更好的实现可能是:

struct node *insert(struct node *head, struct node *temp)
{
    struct node *previous = NULL;
    struct node *current = head;

    while (current && temp->freq > current->freq) {
        previous = current;
        current = current->next;
    }

    if (previous == NULL) {
        temp->next = head;
        return temp;
    }

    temp->next = current;
    previous->next = temp;

    return head;
}

请注意，当 current 或 previous 为 NULL 时，此代码永远不会取消引用它们。当 current == NULL 时，您的特殊情况“在末尾插入”由常规代码处理。

编辑:关于您按字母顺序打印节点的请求:有很多可能性可以做到这一点。一种方法是向结构中添加一个字符缓冲区，其中包含字母的编码:

struct node {
    int value;
    unsigned long freq;
    struct node *next;
    struct node *left;
    struct node *right;
    char code[32];
};

然后创建一个“字母表”，即指向霍夫曼树节点的 256 个指针的列表，最初全部为空。 (无论如何，您都需要该字母表进行编码。)

struct node *alpha[256] = {NULL};

然后遍历你的树，传递一个临时字符缓冲区并根据需要将节点分配给你的字母表:

void traverse(struct node *n, int level, char buf[], struct node *alpha[])
{
    if (n == NULL) return;

    if (n->value) {
        alpha[n->value] = n;
        strcpy(n->code, buf);
    } else {
        buf[level] = '0';
        traverse(n->left, level + 1, buf, alpha);
        buf[level] = '1';
        traverse(n->right, level + 1, buf, alpha);
    }
}

当节点有值时，即无子节点时，该值(ASCII 代码)将分配给字母表，以便 alpha['a'] 指向值为 的节点'a'。请注意，字母表不会创建节点，它指向现有节点。

最后，打印字母表:

char buf[32];
traverse(head, 0, buf, alphabet);

for (i = 0; i < 256; i++) {
    if (alpha[i] != NULL) {
        printf("%c: %s\n", alpha[i]->value, alpha[i]->code);
    }
}

请注意，32 是 n 个任意值，选择的值对于示例而言足够高。在真实的树中，代码的内存可能是单独分配的。