Итерационный обход бинарных деревьев

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

На просторах интернета я обнаружил два способа реализации подобного алгоритма:

  1. С использованием собственного стека с блэкджеком и
  2. С использованием указателя на родителя(баловство, так как в большинстве случаев, если не всегда, легче, быстрее и правильнее использовать первый вариант).

Второй метод я и реализовал в прикреплённом коде.

Не могу назвать асимптотическую сложность по времени этого алгоритма. Очевидно, что он медленнее рекурсивного, так как нам приходится “бродить” по дереву в поисках ещё не пройденного узла. Зато мы получаем сложность по памяти !!!(не учитывая того, что у нас n указателей на родителя)

Интересные ссылки: Хабрахабр Осторожно java! Wikipedia Осторожно красивые картинки!

traversal.pas (3.4 КБ)

Если количество указателей зависит от дерева, то это уже не O(1) по памяти.

Если делали по картинкам, то $O(n)$: по каждому ребру проходим ровно два раза.

Неа, там один указатель. Сначала спускаемся до наименьшего элемента, после делаем iterator++ пока не дойдем до наибольшего, а затем поднимаемся до корня.

Имеется в виду, что размещение данных в структуру дерева сразу приводит к расходам по памяти O(n), поскольку с каждым элементом данных ассоциирован узел, включающий несколько указателей.

Если считать, что дерево – это и есть входные данные, то, наверное, вы правы.

Естественно, само дерево в оценке алгоритма обхода считаться не должно. Это если бы у нас был алгоритм сортировки массива, скажем, а мы внутри дерево создавали, то оно бы считалось.

Согласен. Не правильно понял первый ответ.

Правда в данном случае всё же есть тонкий момент: обычно дерево не содержит дополнительных указателей на родительский узел, а в представленном алгоритме они используются. Соответственно, в зависимости от того, считать их изначально данными, оценки по памяти будут различаться.

А, ну вот я и писал вначале: если используется O(n) указателей, то сложность по памяти O(n). Не вижу каких-то аргументов против. Это @kvark161 сбивает с толку.

В прикрепленной реализации есть указатель на предка, поэтому можно реализовать за $O(1)$ памяти.

 Институт математики, механики и компьютерных наук ЮФУ, 2005–2021
Администрация форума: В.Н. Брагилевский, С.С. Михалкович, А.М. Пеленицын
Yandex.Metrica