c -插入到霍夫曼树



我的霍夫曼树有问题;当我试图构建它时,我把节点放在了错误的地方。例如,我想让权重为2的节点(子节点I:1和n:1)位于m:2和space:3的节点之间,但它恰好位于我放入的前一个节点(2,子节点e:1和g:1)的后面。

我的问题是:我如何将一个有两个孩子的节点插入到一个霍夫曼树(我使用链表),通过优先级它的权重(又名两个孩子的总和)和孩子的符号(即右子'n'在'g'的另一个右子之前)。

谢谢你的帮助!

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

这是我的插入函数…

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

     printf("entering insert functionn");

    // 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 %lun", temp->freq, current->freq);
     previous = current;
    current = current->next;
   }
   if (current->next == NULL)
   {
    printf("hit end of listn");
    temp = current->next;
   }
  else
  {
printf("inserting into listn");
temp->next = current;
previous->next = temp;
  }  
  return head;
 }

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

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;
}

请注意,当currentpreviousNULL时,这段代码从未解除对它们的保护。当current == NULL .

时,您的特殊情况"insert at end"由常规代码处理。

Edit:关于按字母顺序打印节点的请求:有很多可能性这样做。一种方法是在结构中添加一个字符缓冲区,其中包含字母

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

然后创建一个"字母表",即一个包含256个指向Huffman树节点的指针的列表,最初都为空。(无论如何,你都需要这个字母表来编码。)

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: %sn", alpha[i]->value, alpha[i]->code);
    }
}

请注意,32是一个任意的值,它被选择为足够高的例子。在真正的树中,代码的内存可能是单独分配的。

相关内容

  • 没有找到相关文章

最新更新