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

Question

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

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

EDIT: Мне нужно использовать двоичное дерево.

Answer 1

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

• Wikipedia
• C++ reference

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

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

Edit:

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

Answer 2

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

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