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

Question

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

Answer 1

Давно я написал двигатель Хаффмана, но я попробую.

Псевдокод.

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

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