如何利用迭代器配合 yield* 实现对嵌套集合结构的“非递归式”深度遍历-js教程-PHP中文网

非递归式深度遍历本质是用generator委托替代函数调用栈，通过yield*将控制权移交子遍历器，实现按需产出、o(最大嵌套深度)空间复杂度及天然防环能力。

如何利用迭代器配合 yield* 实现对嵌套集合结构的“非递归式”深度遍历

所谓“非递归式”深度遍历，并不是真的消除递归逻辑，而是把递归调用从函数栈转移到 Generator 的执行上下文里——不压栈、不阻塞、按需产出。关键在于用 yield* 委托子结构的遍历，让嵌套层级的展开由迭代器机制自动调度，而不是靠 JS 引擎维护调用栈。

核心原理：委托代替手动展开

yield* 不是简单地 yield 每一项，而是把当前生成器的控制权完整移交出去；被委托的可迭代对象（比如另一个 generator）执行完后，自动交还控制权。这天然适配树、森林、多叉嵌套等结构——每个子节点都可以返回自己的遍历生成器，主生成器只负责串联，不关心内部怎么走。

避免显式维护栈或队列，代码更贴近数据结构本身
每调用一次 next()，才深入一层，空间复杂度降至 O(最大嵌套深度)
遇到循环引用时，可配合 WeakSet 记录已访问节点，防止无限委托

典型实现：通用嵌套数组扁平化

对形如 [1, [2, [3]], 4] 这类混合值与数组的结构，可用如下 generator：

function* flatten(items) {
  for (const item of items) {
    if (Array.isArray(item)) {
      yield* flatten(item); // 委托给子数组的遍历
    } else {
      yield item;
    }
  }
}

调用方式：Array.from(flatten([1, [2, [3]], 4])) → [1, 2, 3, 4]。注意：这里 flatten 是递归定义的 generator 函数，但执行过程不依赖调用栈深度，而是靠引擎管理的内部状态机。

扩展支持对象树与防环机制

若结构含对象节点（如树节点有 value 和 children），可在遍历时加入访问标记：

function* traverse(node, seen = new WeakSet()) {
  if (seen.has(node)) return;
  seen.add(node);
  yield node.value;
  if (Array.isArray(node.children)) {
    for (const child of node.children) {
      yield* traverse(child, seen);
    }
  }
}

这样即使树中存在共享子节点或人为构造的环，也能安全终止委托链，不会卡死或爆内存。