С++. Бинарные деревья. Обход всех элементов без рекурсии
Суть:
Есть класс список элементов. Расположение элементов в форме бинарного дерева.
Реализовано добавление элементов, вывод на экран через рекурсию (от головы до хвоста)
Задача:
Сделать еще функцию вывода на экран элементов, но уже без рекурсии. Порядок вывода: от головы до хвоста. Как без рекурсии обойти все элементы?
Помогите пожалуйста. То, что получается либо работает частично, либо вообще не работает.
Спасибо заранее тем, кто попытается реально помочь.
Ты совершенно зря заблокировал абсолютно правильный ответ. Для обхода дерева в глубину нужен только стек (очередь LIFO) - безо всякой рекурсии.
На каждом шаге выводим значение текущего элемента, помещаем в стек ссылку на правый дочерний узел (если он есть) и переходим к левому дочернему узлу; если левого узла нет - извлекаем узел из стека и делаем его текущим.
А вот для обхода в ширину необходима очередь FIFO:
1. Заносим в очередь ссылку на корень дерева.
2. Повторяем в цикле, пока очередь не исчерпана: берём элемент из очереди, выводим его значение, посещаем в очередь ссылки на дочерние узлы этого элемента (если они есть) - сначала ссылку на левого потомка, потом на правого.
Вместо рекурсии используй стек. Собссно, рекурсия - это и есть использование возможностей стека, только это неявное использование возможностей встроенного стека. А тебе нужно сделать обычную структуру данных и прямо работать с ней.