Recherche du chemin sur un arbre Huffman

Question

Je travaille sur un arbre Huffman et j'essaie de comprendre comment traverser l'arbre pour trouver le nœud qui a le caractère que je cherche. Lors de la recherche dans l'arbre, je dois garder une chaîne du chemin qui est pris au nœud que je cherche en utilisant 1 et 0 (0 gauche 1 droite). Comment puis-je faire ceci?

Answer 1

Depuis longtemps, j'ai écrit un moteur Huffman, mais je vais essayer.

Pseudo-code.

En supposant que votre noeud Huffman arbre ressemble à ceci

class HuffNode 
{ 
... 
char ch; 
long huffCode; //initialized to zero initially 
HuffNode left,right; 
} 

est donc ici fonction récursive (conversion à itératif devrait être facile)

void buildCodes(HuffNode currentNode, long currentCode) 
{ 
currentNode->huffCode = currentCode; 
if(currentNode->left != null) buildCodes(currentNode->left, currentCode << 1); 
if(currentNode->right != null) buildCodes(currentNode->right, (currentCode << 1) | 1); 
} 

appellent cette façon

buildCodes(rootHuffNode,0);