Кодирование двоичного дерева Хаффмана

Question

Я пытаюсь написать функцию, которая принимает дерево хаффмана и символ. Затем он должен кодировать символ и возвращать его.

код до сих пор:

string encode(NodePtr root, char letter) 
{ 
    string encode_str; //a string which will store the encoded string 
    NodePtr tempNode = root; //Initialize a new Huffman to be used in this function 
    NodePtr tempLeft = root->left; 
    NodePtr tempRight = root->right; 

     //A while loop that goes on until we find the letter we want 
     while((tempLeft->letter != letter) || (tempRight->letter != letter)) 
     { 
     if((tempRight->is_leaf()) && (tempRight->letter == letter)) //check if is leaf and is letter 
     { 
       encode_str = encode_str + '1'; 
     } 
     else if ((tempLeft->is_leaf()) && (tempLeft->letter == letter)) //check if is leaf and is letter 
     { 
      encode_str = encode_str + '0'; 
     } 
     else if ((tempRight->is_leaf()) && (tempRight->letter != letter)) //check if is leaf and is NOT letter 
     { 
      tempNode = root->left; 
      tempLeft = tempNode->left; 
      tempRight = tempNode->right; 
      encode_str = encode_str + '0'; 
     } 
      else if ((tempLeft->is_leaf()) && (tempLeft->letter != letter)) //check if is leaf and is NOT letter 
     { 
      tempNode = root->right; 
      tempLeft = tempNode->left; 
      tempRight = tempNode->right; 
      encode_str = encode_str + '1'; 
     } 
     }  

    return encode_str; 
} 

Это не работает до сих пор и отладка не помогло мне либо. Может ли кто-нибудь помочь мне здесь или, по крайней мере, сказать мне, правильно ли я думаю.

Answer 1

Если ни tempLeft, ни tempRight является лист, у вас есть бесконечный цикл:

while((tempLeft->letter != letter) || (tempRight->letter != letter)) 
    { 
     if((tempRight->is_leaf()) && 
      (tempRight->letter == letter)) 
     { 
      // no 
     } 
     else if ((tempLeft->is_leaf()) && 
       (tempLeft->letter == letter)) 
     { 
      // no 
     } 
     else if ((tempRight->is_leaf()) && 
       (tempRight->letter != letter)) 
     { 
      // no 
     } 
     else if ((tempLeft->is_leaf()) && 
       (tempLeft->letter != letter)) 
     { 
      // no 
     } 
    } 

Там должно быть что-то вы собираетесь делать в том случае, когда узлы не являются листья. Может быть, рекурсия?

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

---

Когда один ребенок является листом, а другой не ваша цель письма, вы пытаетесь установить новый tempNode, tempLeft и tempRight для следующего Обойдите цикла.

else if ((tempRight->is_leaf()) && 
      (tempRight->letter != letter)) 
    { 
     tempNode = root->left; 
     tempLeft = tempNode->left; 
     tempRight = tempNode->right; 
     encode_str = encode_str + '0'; 
    } 

Однако, так как вы никогда не изменять root, tempNode = root->left всегда будет установлен tempNode на тот же узел.

Возможно, вы захотите tempNode = tempNode->left.

---

Чтобы избежать повторения кода, вы можете переместить

tempLeft = tempNode->left; 
tempRight = tempNode->right; 

... чтобы быть первым, что происходит в цикле while().

---

Вы говорите, что отладка не помогла. Вы действительно запускаете его в отладчике?

Напишите единичный тест, который устанавливает ваше дерево; подтверждает, что дерево фактически содержит то, что вы намереваетесь; и вызывает эту функцию одной буквой. Решите, как вы думаете, что выполнение должно продолжаться. Теперь запустите код в отладчике, пройдя через него. Когда он перестает делать то, что, по вашему мнению, должен, вы сможете рассуждать о том, почему.

---

Обычный способ реализации Хаффмана Кодирование, чтобы иметь массив конечных узлов, так что вы можете достичь с помощью простого узла доступа к массиву:

NodePtr nodeA = nodes[0]; 

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

string code = ""; 
    NodePtr node = nodeA; 
    while(node->parent != NULL) { 
     code = node->code + code; 
     node = node->parent; 
    }