Алгоритм создания Итератора для класса BinaryTree

Question

Я хочу добавить двунаправленный итератор (например, итератор, экспортируемый с помощью std :: set) в мой класс параметризованного BinaryTree, но я не могу найти ни одного алгоритма.

Простая структура узла Двоичного дерева, он содержит три указателя, левый, правый, родительский:

Answer 1

С заданной структурой вы хотите действовать следующим образом:

1. Чтобы начать итерацию, вы найдете самый левый узел.
2. Чтобы перейти к следующему узлу, операция зависит от того, где вы сейчас находитесь:
   1. Если у вашего узла есть правый дочерний элемент, вы переходите к этому дочернему элементу и находите его самого левого преемника (если левого дочернего узла нет, узел, на котором вы находитесь, является следующим узлом).
   2. Если у ваших узлов нет нужного потомка, вы двигаетесь вверх по цепочке родителей, пока не найдете родителя, для которого вы использовали ссылку на левый узел: следующий узел становится этим узлом.
3. Чтобы двигаться в другом направлении, вы меняете роли слева и справа.

По сути, это реализует обход дерева по порядку без стеков. Если ваше дерево не изменилось во время итерации (маловероятный сценарий) или у вас нет ссылки на родительский узел, вы можете явно поддерживать стек в итераторе.

Answer 2

Хороший подход к этой проблеме может состоять в том, чтобы сначала написать свой рекурсивный алгоритм предварительного заказа, не используя шаблоны, а затем вы можете создать шаблонную версию и реализовать правильные итераторы.

Просто мысль,

Answer 3

Вы не можете использовать рекурсию для реализации итератора в C ++, потому что ваш итератор должен вернуться из всей обработки, прежде чем он сможет вернуть результат.

Только языки, такие как C # и Python, которые имеют концепцию yield, могут использовать рекурсию для создания итераторов.

Ваш итератор должен поддерживать стек еще не посещенных узлов.

Наверху, я думаю, что алгоритм выглядит примерно так:

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