我的霍夫曼树有问题;当我试图构建它时,我把节点放在了错误的地方。例如,我想让权重为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;
}
请注意,当current
或previous
是NULL
时,这段代码从未解除对它们的保护。当current == NULL
.
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是一个任意的值,它被选择为足够高的例子。在真正的树中,代码的内存可能是单独分配的。