Чтобы предоставить своим клиентам наиболее удобный и гибкий интерфейс, запишите его как класс, реализующий Iterator<E>.
Это означает, что клиент может перебирать элементы, найденные во время рекурсии, но ему не нужно реализовывать свой код «для каждого» в качестве обратного вызова (у Java нет красивого способа сделать это), и они могут даже «приостановить» операцию и продолжить ее позже, вне области, в которой они ее начали (или отказаться от нее в любой момент).
Это самый сложный для реализации, хотя. Если структура данных, которую вы просматриваете, представляет собой древовидную структуру с родительскими указателями в каждом узле, то вам не нужны никакие другие данные, кроме текущего узла. Чтобы перейти к следующему узлу, ищите первого ребенка. Если есть один, это следующий узел. В противном случае попробуйте следующий брат. Если его нет, найдите родителя и попытайтесь получить its следующего родного брата и так далее, пока не достигнете нуля, в этом случае больше нет элементов.
В качестве быстрого и грязного примера приведем класс, подобный treenode, нарушающий все правила инкапсуляции для экономии места:
class SimpleNode
{
String name;
public SimpleNode parent, firstChild, nextSibling;
public SimpleNode(String n) { name = n; }
public void add(SimpleNode c)
{
c.parent = this;
c.nextSibling = firstChild;
firstChild = c;
}
public String getIndent()
{
StringBuffer i = new StringBuffer();
for (SimpleNode n = this; n != null; n = n.parent)
i.append(" ");
return i.toString();
}
}
Теперь давайте создадим из него дерево:
SimpleNode root = new SimpleNode("root");
SimpleNode fruit = new SimpleNode("fruit");
root.add(fruit);
fruit.add(new SimpleNode("pear"));
fruit.add(new SimpleNode("banana"));
fruit.add(new SimpleNode("apple"));
SimpleNode companies = new SimpleNode("companies");
root.add(companies);
companies.add(new SimpleNode("apple"));
companies.add(new SimpleNode("sun"));
companies.add(new SimpleNode("microsoft"));
SimpleNode colours = new SimpleNode("colours");
root.add(colours);
colours.add(new SimpleNode("orange"));
colours.add(new SimpleNode("red"));
colours.add(new SimpleNode("blue"));
Теперь, чтобы объяснить это любому, кто не знаком с этой идеей, мы хотим сделать следующее:
for (final SimpleNode n : new SimpleNodeIterator(root))
System.out.println(n.getIndent() + "- " + n.name);
И получите это (я заставил приведенный выше код генерировать нечто, похожее на иерархический список маркеров в SO):
Для этого нам нужно отобразить некоторые стандартные операции в наш SimpleNode класс:
class SimpleNodeIterator extends TreeIterator<SimpleNode>
{
public SimpleNodeIterator(SimpleNode root)
{ super(root); }
protected SimpleNode getFirstChild(SimpleNode of)
{ return of.firstChild; }
protected SimpleNode getNextSibling(SimpleNode of)
{ return of.nextSibling; }
protected SimpleNode getParent(SimpleNode of)
{ return of.parent; }
}
И, наконец, в нижней части нашего дизайна, TreeIterator<TNode> - это очень многократно используемый абстрактный базовый класс, который делает все остальное, теперь мы рассказали, как перемещаться по нашему классу узла:
abstract class TreeIterator<TNode> implements Iterator<TNode>,
Iterable<TNode>
{
private TNode _next;
protected TreeIterator(TNode root)
{ _next = root; }
public Iterator<TNode> iterator()
{ return this; }
public void remove()
{ throw new UnsupportedOperationException(); }
public boolean hasNext()
{ return (_next != null); }
public TNode next()
{
if (_next == null)
throw new NoSuchElementException();
TNode current = _next;
_next = getFirstChild(current);
for (TNode ancestor = current;
(ancestor != null) && (_next == null);
ancestor = getParent(ancestor))
{
_next = getNextSibling(ancestor);
}
return current;
}
protected abstract TNode getFirstChild(TNode of);
protected abstract TNode getNextSibling(TNode of);
protected abstract TNode getParent(TNode of);
}
(Это слегка непослушно, поскольку он реализует Iterator<E> и Iterable<E> на одном и том же объекте. Это просто означает, что вам нужно создать новый объект, чтобы выполнить итерацию во второй раз; не пытайтесь повторно использовать тот же объект).
Это означает, что если ваша иерархическая структура состоит из узлов, для которых вы можете определить эти три простые навигационные операции, то все, что вам нужно сделать, - это получить собственный эквивалент SimpleNodeIterator. Это позволяет очень легко включить эту возможность в любой древовидной реализации.
Если то, что вы повторяете, не может найти родителя, вам нужно сохранить стек во время итерации. Каждый раз, когда вы опускаете уровень, вы помещаете состояние текущего уровня в стек. Когда вы заканчиваете итерацию на текущем уровне, вы вытаскиваете последнее состояние из стека и продолжаете его. Когда стек пуст, все готово. Это означает, что у вас есть некоторое промежуточное хранилище, но его максимальный размер пропорционален глубине рекурсии, а не количеству элементов, поэтому, если данные примерно сбалансированы, тогда они должны быть намного более эффективными для хранения, чем копирование всех элементов в список, прежде чем вернуть его.