Huffman Кодирование дерева

Question

Я пытаюсь построить дерево кодирования Хаффмана.

главная:

int main() 
{ 
    // Read frequency table and build Huffman tree. 
    NodePtr huffman = build_tree(); 
    print_tree(huffman); 

    // Free the allocated memory. 
    free_memory(huffman); 

    return 0; 
} 

вход должен быть в форме:

number of letters 
"letter" number of occurrences 
"letter2" number of occurrences 

До сих пор я не получил его на работу. Какие-нибудь идеи, что может быть неправильным?

build_tree функция:

NodePtr build_tree() 
{ 
    int characters;//number of characters 
    cin >> characters; 
    char letter; 
    int freq; 
    HuffmanPriorityQueue queue; 
    NodePtr p; 
    for (int i = 0 ; i < characters; i++) 
    { 
     cin >> letter; 
     cin >> freq; 
     NodePtr temp = new HuffmanNode(freq, letter); 
     queue.push(temp); 
    } 
    for (int i = 0 ; i < characters - 1 ; i++) 
    { 
     NodePtr a = queue.top(); 
     queue.pop(); 
     NodePtr b = queue.top(); 
     NodePtr p = new HuffmanNode (a->frequency + b->frequency, NULL); 
     queue.push(p); 
    } 
    return p; 
} 

Функция печати: который был поставлен таким образом, я предполагаю, что это правильно.

void print_tree(NodePtr root, int indent = 0, string prefix = "") 
{ 
    // External nodes are not printed. 
    if (root == NULL) { 
     return; 
    } 

    char letter = ' '; 
    if (root->is_leaf()) { 
     letter = root->letter; 
    } 

    cout << string(indent, ' ') << prefix << "(" << letter << " [" << root->frequency << "]"; 
    if (root->is_leaf()) { 
     cout << ")" << endl; 
    } else { 
     cout << endl; 
     // Print left and right subtrees with the appropriate prefix, and 
     // increased indent (by INDENT_SIZE). 
     print_tree(root->left, indent + INDENT_SIZE, "0"); 
     print_tree(root->right, indent + INDENT_SIZE, "1"); 
     cout << string(indent, ' ') << ")" << endl; 
    } 
} 

Answer 1

У вас есть несколько проблем:

• Наружный NodePtr p никогда не назначается.
• Там нет pop для NodePtr b
• Новый узел не относится к своим детям a и b
• Вы не возвращают корень.

Так следующее может помочь:

for (int i = 0 ; i < characters - 1 ; i++) 
{ 
    NodePtr a = queue.top(); 
    queue.pop(); 
    NodePtr b = queue.top(); 
    queue.pop(); 
    NodePtr p = new HuffmanNode (a, b); // The new node has two children `a` and `b`. 
    queue.push(p); 
} 
return queue.top(); // Return root.