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?Recherche du chemin sur un arbre Huffman
0
A
Répondre
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);