复合模式的递归迭代器

Question

我有树 classes AbstractComponent、Leaf 和 Composite：

public abstract class AbstractComponent {
    privavte String name;

    [...]
}

public class Leaf extends AbstractComponent {
    [...]
}

public Composite extends AbstractComponent {
    private List<AbstractComponent> children;

    public void addChild(AbstractComponent a) {
        [...] 
    }

    public List<AbstractComponent> getChildren() {
        return children;
    }
}

我的问题：如何在 Java 中为基于复合模式的模型编写递归迭代器？我读了这个问题 (Creating a recursive iterator)。可以对我的问题采用公认的答案吗？我还从番石榴中找到了 TreeTraverser class，但它似乎仅限于一个代表节点的 class。

Answer 1

迭代器不是递归的。不确定我是否理解你的问题，但你的结构的基本迭代器应该看起来像（从这里开始的级别顺序： http://en.wikipedia.org/wiki/Tree_traversal) :

 public class AbstractComponentIterator implements Iterator<AbstractComponent> {

    Deque<AbstractComponent> stack = new LinkedList<>();


    public AbstractComponentIterator(AbstractComponent root) {
        stack.add(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

      @Override
    public AbstractComponent next() {
        if(stack.isEmpty()){
            throw new NoSuchElementException();
        }
        AbstractComponent node = stack.pop();
        if (node != null) { //only if Composite.children has null 
            if (node instanceof Composite) {
                Composite ac = (Composite) node;
                for (AbstractComponent acc : ac.children) { 
                    stack.add(acc);
                }
            }
        }
        return node;
    }
}

Answer 2

首先是一些术语方面的帮助。

Iterators are not recursive. What you are looking for is a strategy of Tree Traversal。
虽然树遍历实现通常是递归的，但它们通常不会用于迭代器。
您的组件对象的结构称为 generic tree。

1st 您需要选择遍历复合结构的方式（a.k.a 通用树）

user1121883's 如果您没有特定的遍历顺序要求，解决方案是一个很好的选择，因为它实施起来很简单。

如果您需要实施不同的策略（例如深度优先），请尝试以下方法

class AbstractComponent {

    public Iterator<AbstractComponent> iterator() {
        List<AbstractComponent> list = new LinkedList<AbstractComponent>();
        addAllChildren(list);
        list.add(this);
        return list.iterator();
    }

    protected abstract void addAllChildren(List<AbstractComponent> list);
}

public class Leaf extends AbstractComponent {

    //...

    protected void addAllChildren(List<AbstractComponent> list) {
        //DO NOTHING
    }
}

public class Composite extends AbstractComponent {

    //...

    protected void addAllChildren(List<AbstractComponent> list) {
        for (AbstractComponent component : children) {
            // This is where you implement your traversal strategy
            component.addAllChildren(list);
            list.add(component);
        }
    }
}

复合模式的递归迭代器

Recursive iterator for composite pattern

java

iterator

composite