Нахождение индекса узла в дереве Хаффмана

Question

Предположим, у нас есть дерево узлов (дерево Хаффмана), в котором хранятся строковые значения. Как бы я обошел дерево и выполнил бы индекс определенного узла, если бы у меня было такое дерево? Числа, которые я нарисовал внутри кружков, будут индекс , который я хочу (особенно 12 или 13).

Примечание: из-за недопонимания, я повторюсь: #, которые я написал внутри кругов, это , а не значения, которые содержат узлы. Это index этого узла. Моя проблема заключалась в том, что я не мог найти индекс, поскольку деревья странно структурированы - это не классическое дерево BST, а значения внутри не являются числовыми.

Редактировать: Я перерисовал изображение, чтобы сделать мой вопрос более ясным. В любом случае, я понял это. Я напишу ответ после финала.

Answer 1

Отображаемое вами дерево не является двоичным деревом поиска. Центральное свойство бинарного дерева поиска, позволяющее эффективно осуществлять его поиск, заключается в том, что левые потомки узла меньше, а правые потомки больше, чем сам узел (с точки зрения значения индекса).

Если у вас есть правильное двоичное дерево поиска, вы можете найти узел с данным индексом, сравнив его с узлами и следуя соответствующей ветви, начиная с корня.