迭代器模式与 Java 集合：自定义迭代器实现复杂数据结构的遍历

1. 迭代器模式核心概念

迭代器模式提供统一访问接口，实现：

• 解耦遍历逻辑与数据结构
• 支持多种遍历方式（前序/中序/后序）
• 隐藏内部存储细节

关键接口：

public interface Iterator<E> {
    boolean hasNext();
    E next();
    // Java 8+ 支持默认remove()
}

2. Java 集合框架中的迭代器

标准实现方式：

List<String> list = new ArrayList<>();
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

3. 自定义迭代器实现（二叉树示例）

步骤 1：定义树节点

class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;
    
    public TreeNode(T data) {
        this.data = data;
    }
}

步骤 2：实现可迭代树结构

class BinaryTree<T> implements Iterable<T> {
    private TreeNode<T> root;
    
    @Override
    public Iterator<T> iterator() {
        return new InOrderIterator(root);
    }
    
    // 插入节点等方法省略
}

步骤 3：自定义中序遍历迭代器

class InOrderIterator<T> implements Iterator<T> {
    private final Stack<TreeNode<T>> stack = new Stack<>();
    
    public InOrderIterator(TreeNode<T> root) {
        pushLeftNodes(root);
    }
    
    private void pushLeftNodes(TreeNode<T> node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
    
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    @Override
    public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        
        TreeNode<T> current = stack.pop();
        pushLeftNodes(current.right);  // 处理右子树
        
        return current.data;
    }
}

4. 使用自定义迭代器

BinaryTree<Integer> tree = new BinaryTree<>();
// 构建树结构...

// 遍历示例
for (Integer val : tree) {
    System.out.print(val + " ");
}
// 输出：1 3 4 6 7 8 10 13 14（中序遍历结果）

5. 应用场景

1. 复杂数据结构遍历

   • 树形结构（N叉树/B+树）
   • 图结构（DFS/BFS）
   • 组合模式对象

2. 特殊遍历需求

   • 分页遍历
   • 过滤遍历（如只遍历偶数节点）
   • 并行遍历

6. 设计注意事项

1. 线程安全

   • 使用ConcurrentModificationException检测并发修改
   • 推荐快照迭代器（复制数据）

2. 遍历状态保存

   graph LR
   A[迭代器创建] --> B[初始化遍历状态]
   B --> C[保存当前节点指针]
   C --> D[维护辅助数据结构]
   

3. 性能优化

   • 惰性求值：next()时才计算
   • 空间优化：避免全量复制

7. 扩展实现

深度优先遍历框架：

class DFSIterator<T> implements Iterator<T> {
    private final Deque<TreeNode<T>> stack = new ArrayDeque<>();
    
    public DFSIterator(TreeNode<T> root) {
        if (root != null) stack.push(root);
    }
    
    @Override
    public T next() {
        TreeNode<T> node = stack.pop();
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
        return node.data;
    }
}

带过滤功能的迭代器：

class FilteredIterator<T> implements Iterator<T> {
    private final Iterator<T> source;
    private final Predicate<T> filter;
    private T nextItem;
    
    public FilteredIterator(Iterator<T> source, Predicate<T> filter) {
        this.source = source;
        this.filter = filter;
        advance();
    }
    
    private void advance() {
        while (source.hasNext()) {
            T item = source.next();
            if (filter.test(item)) {
                nextItem = item;
                return;
            }
        }
        nextItem = null;
    }
    
    @Override
    public boolean hasNext() {
        return nextItem != null;
    }
}

总结

通过自定义迭代器：

• 可实现对任意复杂数据结构的标准化遍历
• 保持与 Java 集合框架的兼容性
• 满足foreach语法糖要求
• 时间复杂度通常为 $O(n)$，空间复杂度取决于数据结构特性

最佳实践：当标准集合迭代器无法满足遍历需求时，优先考虑自定义迭代器而非暴露内部结构。