我正在从以最低频率开始的有序链表（按字母频率排序）构建霍夫曼编码树。创建树后，我遍历了它，看来树的实现不正确。当我遍历树时，有序链表中的一些节点似乎被遗漏了。（我不认为这是因为我的遍历是错误的。）这是我的树代码：
//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;
}