Поиск двоичного дерева & amp; отслеживание

Question

Поиск двоичного дерева & amp; отслеживание

У меня есть двоичное дерево узла, содержащее целое число и символ. Я работаю над кодированием Хаффмана и хочу получить двоичное представление узлов. «0» добавляется к строке для каждого левого ответвления, а «1» добавляется для каждого правого ответвления.

Я думаю о поиске символа, но отслеживаю его ветви, если он не находится в левом узле, удалите последний ‘0’, добавленный к строке, и вернитесь вверх и проверьте правильность.
Это выглядит очень сложным. Есть ли другой способ для меня, чтобы отслеживать узел?

РЕДАКТИРОВАТЬ:
Я должен использовать бинарное дерево.

1

algorithm binary-tree c++huffman-code

Решение

Другие решения

Вы говорите о кодировании вывода Хаффмана?

Вы захотите построить таблицу выходных кодов и длин для каждого возможного входного символа — не обходите дерево для каждого входного символа.

2

Источник

Accepted Answer

Походит на структуру данных стека:

Вы отслеживаете, где находитесь в дереве, используя стек следующим образом:

путь = std::stack<int>
перейти к родителю == pop()
перейти к левому ребенку == push(0)
перейти к правому ребенку == push(1)

Редактировать:

Вы можете использовать std::vector<int> с push_back а также pop_back вместо. Он по-прежнему ведет себя как стек, но вы можете получить весь список нулей и единиц в конце, если вы используете вектор.

2