Поиск пути на дереве Хаффмана

Question

Я работаю над деревом Хаффмана, и я пытаюсь понять, как пройти дерево, чтобы найти узел, у которого есть характер, который я ищу. Во время поиска в дереве мне нужно сохранить строку пути, который берется к узлу, который я ищу, используя 1 и 0 (0 слева 1 справа). Как я могу это сделать?

Answer 1

С тех пор как я написал двигатель huffman, но я дам ему шанс.

Pseudo Code.

Предполагая, что ваш Хаффмана Tree Node выглядит следующим образом

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

Так вот рекурсивная функция (преобразование его в итерационные должно быть легко)

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); 
} 

назвать это таким образом

buildCodes(rootHuffNode,0);