Здание дерева кодирования Хаффмана из упорядоченного списка

Question

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

//My class for the nodes in the ordered linked list that will be converted to a tree 
class fList{ 
public: 
    fList(); 
    int frequency; 
    char letter; 
    fList* next; 
    fList* left; 
    fList* right; 
}; 

fList::fList(){ 
    frequency = 0; 
    letter = NULL; 
    next = NULL; 
    left = NULL; 
    right = NULL; 
} 
fList* head = NULL; 

    . 
    . 
    . 
    . 
    . 

//Create the huffman encoding tree from the linked list stored in head 
while(head->next != NULL){ 
    fList *tree = new fList(); 
    fList *temp = new fList(); 
    fList *trail = new fList(); 

    /* Take the first two frequency numbers, add them, create a new node        
    * with the total frequency number and have new node point to the first       
    * two nodes (right child and left child) 
    */              
    total = (head->frequency + head->next->frequency); 
    tree->frequency = total; 
    //Set a new head node 
    tree->left = head; 
    tree->right = head->next; 
    head = head->next->next; 
    tree->left->next = NULL; 
    tree->right->next = NULL; 

    //place tree node in its correct place in sorted list           
    temp = head; 
    trail = temp; 
    if(head->frequency >= tree->frequency){ 
     tree->next = head; 
     head = tree; 
    } 

    else if(temp->next != NULL){ 
     while(temp != NULL){ 
     if(temp->frequency >= tree->frequency){ 
      tree->next = temp; 
      trail->next = tree; 
      break; 
     } 
     else{ 
      trail = temp; 
      temp = temp->next; 
     } 
     }//while     

    //insert at the end of list                 
    if(temp == NULL){ 
     temp = tree->next; 
     trail->next = tree; 
    } 
    }//else if !=NULL 

    else if(head == NULL || head->next == NULL) head = tree; 
} 

Answer 1

В конце куска кода, который вы в курсе, в строке

else if(temp->next = NULL && head != NULL) head = tree; 

вы случайно обрезаете дерево, установив temp->next = NULL, где вы, вероятно, хотели спросить, temp->next == NULL. Возможно, поэтому некоторые из записей (те, которые связаны с temp), остаются вне окончательного результата.