Algoritmos y Estructuras de Datos (VJ1215)

string Huffman::decodificar(const string & mensajeCodificado) const {
  
   string mensajeOriginal;
   Nodo * n = raiz;
  
   for (char caracter : mensajeCodificado) {
      if (caracter == '0')
	 n = n->izquierdo;
      else
	 n = n->derecho;
      if (n->izquierdo == nullptr) { // Hemos alcanzado nodo hoja
	 mensajeOriginal += n->caracter;
	 n = raiz;
      }
   }
  
   return mensajeOriginal;

}
      

En esta solución comprobamos que hemos alcanzado una hoja viendo que no tiene hijo izquierdo, porque todos los nodos del árbol de Huffman tienen cero o dos hijos. Si un nodo no tiene hijo izquierdo, seguro que tampoco tiene hijo derecho.