组合模式的递归迭代器

Question

我有树类AbstractComponent、叶子和复合：

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为基于复合模式的模型编写递归迭代器？我读了这个问题(创建递归迭代器)。对我的问题采用公认的答案是可能的吗？我还从番石榴中找到了TreeTraverser类，但它似乎仅限于一个表示节点的类。

Answer 1

首先，在术语方面提供一些帮助。

• 迭代器不是递归的。您要寻找的是树遍历的策略。
• 虽然树遍历实现通常是递归的，但它们通常不会用于迭代器。
• 组件对象的结构称为属树。

1您需要选择如何遍历复合结构(即泛型树)

如果没有特定的遍历顺序需求，用户1121883解决方案是一个很好的选择，因为它很容易实现。

如果您需要执行不同的策略(例如，深度优先)，请尝试以下方法

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);
        }
    }
}

Answer 2

迭代器不是递归的。不确定我是否理解您的问题，但是结构的基本迭代器应该类似于(从这里开始的级别顺序：遍历 )：

 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;
    }
}