如何通过自定义迭代器实现对二叉树、图等复杂原始结构的深度优先遍历

不能直接用for-each遍历二叉树或图，是因为它们未实现Iterable接口；需手动实现迭代器，用栈模拟递归过程以支持深度优先遍历。

不能直接用 for-each 遍历二叉树或图，是因为它们没实现 iterable 接口——缺少 iterator() 方法。java 的增强 for 循环只认这个契约，否则抛出 classcastexception。要支持深度优先遍历，就得手动提供一个迭代器，把递归逻辑“翻译”成栈驱动的状态机。

为什么必须用栈模拟递归

递归本质是系统自动维护调用栈：每层压入参数、局部变量和返回地址；终止后从栈顶逐层弹出。深度优先遍历天然依赖这种“后进先出”顺序。自定义迭代器不能依赖方法调用栈（会溢出、不可控），所以必须显式用 Stack 或 Deque 模拟整个过程。

• 前序遍历：访问根 → 左子树 → 右子树 → 栈中先压右再压左，保证左先弹出
• 中序遍历：访问左子树 → 根 → 右子树 → 需持续向左探到底，再回退取根、转右
• 后序遍历：左 → 右 → 根 → 常用双栈或标记法，避免提前输出根节点

实现自定义迭代器的三步核心

以二叉树中序遍历为例，关键不是“怎么写循环”，而是“怎么管理状态”：

• 构造时预加载最左路径：从根开始一路向左，把所有非空左节点压栈，让栈顶是最深的左叶子
• hasNext() 只查栈是否为空：不预计算下一个元素，保持轻量；空栈即遍历结束
• next() 弹出栈顶，立即压入其右子树的最左路径：比如弹出节点 A，若 A 有右子树，则从 A.right 开始一路向左压栈，确保下一次 next() 返回的是 A 右子树中最靠左的节点

图结构的适配要点

图比树更复杂：可能有环、多起点、无固定根。深度优先迭代器需额外处理：

• 用 Set<Node> 记录已访问节点，防止重复入栈陷入死循环
• 初始化时可接受多个起始节点（如所有入度为 0 的点），或由用户指定根
• 邻接关系不再只是 left/right，而是通过 getNeighbors(node) 动态获取，每次弹出节点后将其未访问邻居全部压栈
• 若需保证确定性顺序（如按字母排序），压栈前对邻居列表排序

别在单个类里塞多种遍历逻辑

一个树类如果同时提供前序、中序、后序的 iterator() 方法，容易导致状态混乱、难以测试。推荐做法是：

• 每个遍历策略单独实现一个 Iterator 子类（如 InorderIterator、PreorderIterator）
• 树类只暴露工厂方法：inOrderIterator()、preOrderIterator()
• 迭代器内部不持有树引用以外的状态，确保线程安全（若需）和可重用性