Двоичное дерево теряет узлы при построении дерева

Question

Я построил двоичное дерево (дерево хаффмана), используя приведенный ниже код, который занимает отсортированный в списке по возрастанию список, однако, когда он заканчивает работу, он печатает битовые шаблоны и несколько узлов, которые должны быть в дереве, нет.

Код существу:

1. наборы родительского узла к точке на двух нижних узлов

2. назначает внутреннюю частоту родительского узла

3. точки начало списка теперь на узлы 2, где он был (чтобы избежать повторного использования узлов)

4. Вставляет новый родительский узел int о правильной позиции в дереве

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 : %d\n", temp->letter, temp->frequency); 
     } 
     printf("----------------------------------------------\n"); 
     length = counter; 
     counter = 0; 
    } 
    printf("Found root with value of: %d\n", 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

Ok! Это было сложно отлаживать. Но, думаю, я нашел проблему. Проблема заключается в цикле while, где вы найдете длину списка, оставшуюся для обработки. Так как условие в цикле while является temp->next != NULL, поэтому, считаю, что ваш список имеет размер 2, что-то вроде этого ::

3 -> 4 -> NULL (Числа представляют собой сумму частот некоторых узлы)

с list->start ссылающийся на 3. и вы будете измерять длину этого списка 1 и не 2, потому что вы проверяете temp->next != NULL.

Из-за этого вы пропустите важный второй узел списка, и вы запустите BitPatterns() только на первом узле, и вы пропустите несколько узлов.

Возможное решение этой проблемы было бы вставить while петлю в начале функции, чтобы измерить длину один раз, и это может быть уменьшен на 1 в каждой последовательной итерации цикла while, где вы объединить два узла , поскольку вы удаляете два узла и каждый раз добавляете один узел в список, вам нужно только уменьшить length на 1. Это также сэкономит много дополнительных вычислений, которые вы делаете в конце списка для вычисления длины список каждый раз.

Нечто подобное ::

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

EDIT :: Кроме того, есть еще одна логическая ошибка, которую я вижу в вашем коде ::

Рассмотрим, что первоначальный список этот ::

1 -> 2 -> 4 -> 5 -> NULL

Вы объединяете первые два узла, позвольте этому узлу называть A (with freq = 3) на данный момент и list_start указывает на 4. Таким образом, когда вы вставляете узел в списке выглядит следующим образом ::

4 -> A -> 5 -> NULL

Хотя список, будет выглядеть примерно так ::

а -> 4 -> 5

Это не влияет на функционирование коды, но может привести к некоторым не-оптимизированным результатам код Хаффмана.