Кто-нибудь писал или думал о написании итератора для составной (древовидной) структуры без использования рекурсии? Если да, то можете ли вы поделиться своими идеями? Спасибо
Изменить: я думал о Java для lang.
Итератор составных шаблонов без рекурсии
Ответы (2)
Обойти дерево без рекурсии достаточно просто. Предполагая двоичное дерево, каждый узел предположительно имеет три ссылки на другие узлы. Левый ребенок, правый ребенок и родитель. Итак, предполагая порядок итерации слева направо по глубине, вы следуете ссылкам на левого потомка в while-lop (псевдокод while current.left-child != null, current = current.left-child), если левого потомка нет, вы пробуете правого потомка. Если нет и правильного ребенка, вы идете вверх, пока не найдете правого ребенка (while current.right-child == null, current = current.parent)
Вы не указали язык, но поскольку вы хотите избежать рекурсии, я предполагаю, что это какой-то императивный язык, и тогда все вышесказанное должно быть возможным.
Короче говоря, ваш итератор должен содержать ссылку на текущий узел и некоторую информацию о том, в каком направлении он движется.
person
jalf
schedule
06.02.2009
Согласен с обходом двоичного дерева, но я не хотел предполагать двоичное дерево.
- person Vidhya; 06.02.2009
Что ж, сложно пройти по дереву, не сделав каких-либо предположений о его структуре. Тот же подход можно тривиально изменить для любой древовидной структуры. Пройдите через его дочерние элементы, затем перейдите к родительскому и попробуйте следующий дочерний узел
- person jalf; 06.02.2009
Вы можете почерпнуть вдохновение из этого вопроса SO: Обход двоичного дерева после заказа без рекурсии Все, что вам нужно, - это расширить алгоритм на небинарные деревья.
person
GETah
schedule
21.11.2011
