c-二叉树在构建树时丢失了节点

Question

我使用下面的代码构建了一个二进制树（huffman树），它采用了一个按升序排序的链表，但当它完成运行时，它会打印位模式，而树中的一些节点却没有。

代码本质上是：

1. 将父节点设置为指向两个最低节点

2. 分配父节点的内部频率

3. 将列表的开始点指向从原来位置开始的节点2（以避免重复使用节点）

4. 将新的父节点插入树中的正确位置

5. 获取树的长度

6. 打印列表中剩下的所有节点

7. 迭代，直到剩下一个节点（即根节点）。

有什么想法可以解释为什么它一路上会"失去"节点吗？

void build_tree(pqueue *list)
{
    node *temp; 
    node* parent_node;
    int min_1, min_2, ind = 0, counter = 0, length = 2, head;
    int characters[CHARACTERS];
    temp = new_node();
    while (length > 1)
    {
        min_1 = 0;
        min_2 = 0;
        temp = list->start;           
        parent_node = new_node(); 
        parent_node->letter = '#';             
        min_1 = temp->frequency;
        parent_node->left = temp;         
        temp = temp->next;               
        min_2 = temp->frequency;
        parent_node->right = temp;       
        parent_node->frequency = min_1 + min_2;
        list->start = temp->next;
        while (ind == 0) /* inserting a node to the correct place */
        {
            if (temp != NULL && temp->next != NULL)
            {
                temp = temp->next;
                if (temp->frequency >= parent_node->frequency) /* in the middle */
                {
                    parent_node->next = temp->next;
                    temp->next = parent_node;
                    ind = 1;
                }
                else if (temp->next == NULL) /* at the end */
                {
                    temp->next = parent_node;
                    parent_node -> next = NULL;
                    ind = 1;
                }
            }
        }
        ind = 0;
        temp =  list->start;
        while (temp->next != NULL) /* get number of nodes left to insert into tree */
        {
            temp = temp->next;
            counter++;
            printf("%c : %dn", temp->letter, temp->frequency); 
        }
        printf("----------------------------------------------n");
        length = counter;
        counter = 0;
    }
    printf("Found root with value of: %dn", temp->frequency);
    head = 0;
    BitPatterns(temp, characters, head);
    temp = list->start;
    deallocate(temp, list);
}

void BitPatterns(node* root, int characters[], int head)
{
    if (root->left)
    {
        characters[head] = 0;
        BitPatterns(root->left, characters, head +1);
    }
    if (root->right)
    {
        characters[head] = 1;
        BitPatterns(root->right, characters, head +1);
    }

    if (isLeaf(root))
    {
        printf("'%c' : ", root->letter);
        GetChars(characters, head);
    }
}
void GetChars(int characters[], int n)
{
    int i, counter = 0;
    for (i = 0; i < n; ++i)
    {
        printf("%d", characters[i]);
        counter++;
    }
    printf(" (%d * n", counter);
}
int isLeaf(node* root)
{
    return !(root->left) && !(root->right) ;
}

Answer 1

好！这是一个很难调试的问题。但是，我想我已经发现了问题。问题出在while循环中，您可以在其中找到列表的长度，该长度有待处理。由于while循环中的条件是temp->next != NULL，因此，请考虑您的List大小为2，类似于以下内容：：

3-->4-->NULL（数字表示某些节点的频率总和）

list->start指向3。您将测量该列表的长度为1，而不是2，因为您正在检查temp->next != NULL。

因此，您会错过列表中至关重要的第二个节点，并且只在第一个节点上运行BitPatterns()，并且会错过几个节点。

对此，一个可能的解决方案是在函数的开头插入一个while循环来测量一次长度，并且在while循环的每个连续迭代中，可以将其递减1，在该循环中，您组合了两个节点，因为您总是删除两个节点并向列表中添加一个节点，所以您只需要将length递减1。这也将节省您在列表末尾每次计算列表长度时所做的大量额外计算。

类似以下内容：：

temp = list->start;
while(temp != NULL) {
    length++;
    temp = temp->next;
}

编辑：：此外，我在您的代码中看到了另一个逻辑错误：：

考虑一下初始列表是这样的：：

1-->2-->4-->5-->空

将前两个节点合并，让该节点暂时称为A (with freq = 3)，list_start指向4。因此，当你在列表中插入节点时，看起来像这样：：

4-->A-->5-->空

虽然列表，看起来应该是这样的：：

A-->4-->5

这不会影响代码的功能，但可能会导致一些未优化的huffman代码结果。