JS 自定义迭代器 (`Iterator`)：实现复杂数据结构的遍历

各位靓仔靓女们，今天咱们来聊聊JavaScript里一个稍微有点高级，但又非常实用的家伙——自定义迭代器（Iterator）。别怕，听起来唬人，其实就像给你家冰箱装个自动分类系统，让你找东西更方便。

开场白：为啥需要自定义迭代器？

想象一下，你有一个特别定制的冰箱，里面放的东西不是普通的蔬菜水果，而是各种奇奇怪怪的数据结构，比如一颗二叉树，一个图，或者一个你自己发明的超级复杂的列表。

JavaScript原生的for...of循环，只能遍历数组、字符串、Map、Set这些“大众脸”数据结构。对于你定制的冰箱，for...of直接懵圈：“这啥玩意儿？我不知道咋遍历啊！”

这时候，自定义迭代器就闪亮登场了。它就像一个“冰箱导航员”，专门负责告诉你，怎么一步一步地从这个定制冰箱里拿出东西。

迭代器协议：导航员的“工作手册”

要成为一个合格的“冰箱导航员”，必须遵守一套“工作手册”，也就是迭代器协议。这个协议规定，你的导航员必须提供一个叫做next()的方法。

next()方法就像导航员每次指路时说的话：“下一个东西在这里！”，它会返回一个对象，这个对象包含两个属性：

value: 下一个要取出的值。
done: 一个布尔值，表示是否已经遍历完所有东西。true表示遍历结束，false表示还有东西没拿。

动手实现一个简单的迭代器：遍历链表

咱们先从一个简单的例子开始：遍历一个链表。假设我们有这样一个链表：

const linkedList = {
  head: {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null
      }
    }
  }
};

现在，我们要创建一个迭代器，让我们可以用for...of循环遍历这个链表。

linkedList[Symbol.iterator] = function() {
  let current = this.head; // 从链表的头部开始
  return {
    next() {
      if (current) {
        const value = current.value;
        current = current.next; // 移动到下一个节点
        return { value: value, done: false };
      } else {
        return { value: undefined, done: true }; // 遍历结束
      }
    }
  };
};

// 现在我们可以用 for...of 循环遍历链表了
for (const value of linkedList) {
  console.log(value); // 输出 1, 2, 3
}

代码解释：

linkedList[Symbol.iterator] = function() { ... }: 关键的一步！我们给linkedList对象定义了一个Symbol.iterator属性。这个属性必须是一个函数，返回一个迭代器对象。Symbol.iterator是一个特殊的 symbol，用于告诉 JavaScript 引擎，这个对象是可以迭代的。
let current = this.head;: 在迭代器函数内部，我们用current变量来跟踪当前遍历到的节点，从链表的头部开始。
return { next() { ... } };: 迭代器函数返回一个对象，这个对象必须有一个next()方法。
if (current) { ... }: next()方法内部，我们检查current是否为null。如果不是null，说明还有节点可以遍历。
const value = current.value;: 我们取出当前节点的值。
current = current.next;: 将current移动到下一个节点。
return { value: value, done: false };: 返回一个对象，包含当前节点的值和done: false，表示遍历还没有结束。
else { return { value: undefined, done: true }; }: 如果current是null，说明已经遍历到链表的末尾，返回{ value: undefined, done: true }，表示遍历结束。

更复杂的例子：二叉树的迭代器

链表很简单，现在咱们来个更刺激的：二叉树的迭代器。假设我们有这样一个二叉树：

const binaryTree = {
  value: 1,
  left: {
    value: 2,
    left: { value: 4, left: null, right: null },
    right: { value: 5, left: null, right: null }
  },
  right: {
    value: 3,
    left: { value: 6, left: null, right: null },
    right: { value: 7, left: null, right: null }
  }
};

二叉树的遍历方式有很多种，比如前序遍历、中序遍历、后序遍历。这里我们选择中序遍历（左子树 -> 根节点 -> 右子树）。

binaryTree[Symbol.iterator] = function() {
  const stack = []; // 用栈来模拟递归
  let current = this; // 从根节点开始

  return {
    next() {
      // 1. 将所有左子节点入栈
      while (current) {
        stack.push(current);
        current = current.left;
      }

      // 2. 如果栈为空，说明遍历结束
      if (stack.length === 0) {
        return { value: undefined, done: true };
      }

      // 3. 取出栈顶元素（最左边的节点）
      current = stack.pop();
      const value = current.value;

      // 4. 将当前节点的右子树作为新的起点
      current = current.right;

      return { value: value, done: false };
    }
  };
};

// 现在我们可以用 for...of 循环遍历二叉树了 (中序遍历)
for (const value of binaryTree) {
  console.log(value); // 输出 4, 2, 5, 1, 6, 3, 7
}

代码解释：

const stack = [];: 我们用一个栈来模拟递归的过程。
while (current) { ... }: 这个循环的作用是将当前节点的所有左子节点都压入栈中。因为中序遍历是先遍历左子树，所以我们要找到最左边的节点。
if (stack.length === 0) { ... }: 如果栈为空，说明已经遍历完所有节点，返回{ value: undefined, done: true }。
current = stack.pop();: 从栈中弹出一个节点，这个节点就是当前要访问的节点（最左边的节点）。
const value = current.value;: 取出当前节点的值。
current = current.right;: 将当前节点的右子树作为新的起点。因为中序遍历是左子树 -> 根节点 -> 右子树，所以访问完根节点后，要访问右子树。

生成器函数：迭代器的“速成班”

手动实现迭代器很麻烦，尤其是对于复杂的数据结构。好消息是，JavaScript提供了一个更方便的工具：生成器函数（Generator Function）。

生成器函数可以让你用更简洁的代码来创建迭代器。它使用yield关键字来暂停函数的执行，并返回一个值。每次调用迭代器的next()方法时，生成器函数会从上次暂停的地方继续执行，直到遇到下一个yield关键字或者函数结束。

用生成器函数重写链表迭代器

linkedList[Symbol.iterator] = function*() { // 注意 * 号
  let current = this.head;
  while (current) {
    yield current.value; // 使用 yield 关键字
    current = current.next;
  }
};

// 仍然可以使用 for...of 循环
for (const value of linkedList) {
  console.log(value); // 输出 1, 2, 3
}

代码解释：

*`function() { … }**:function*`声明一个生成器函数。
yield current.value;: yield关键字用于暂停函数的执行，并返回current.value作为迭代器的值。下次调用next()方法时，函数会从yield语句的下一行继续执行。

用生成器函数重写二叉树迭代器

binaryTree[Symbol.iterator] = function*() {
  function* inorderTraversal(node) {
    if (node) {
      yield* inorderTraversal(node.left); // 递归遍历左子树
      yield node.value; // 访问当前节点
      yield* inorderTraversal(node.right); // 递归遍历右子树
    }
  }

  yield* inorderTraversal(this); // 从根节点开始
};

// 仍然可以使用 for...of 循环
for (const value of binaryTree) {
  console.log(value); // 输出 4, 2, 5, 1, 6, 3, 7
}

代码解释：

*`function inorderTraversal(node) { … }`**: 定义一个递归的生成器函数，用于中序遍历二叉树。
*`yield inorderTraversal(node.left);**:yield*关键字用于委托给另一个迭代器或生成器函数。这里我们将遍历左子树的任务委托给inorderTraversal`函数。
yield node.value;: 访问当前节点的值。
*`yield inorderTraversal(node.right);**: 将遍历右子树的任务委托给inorderTraversal`函数。

自定义迭代器的应用场景

自定义迭代器在很多场景下都非常有用，例如：

处理大数据集： 你可以创建一个迭代器，每次只加载一部分数据，避免一次性加载整个数据集导致内存溢出。
惰性计算： 你可以创建一个迭代器，只有在需要的时候才计算下一个值，提高程序的效率。
遍历特殊的数据结构： 就像我们上面演示的链表和二叉树。
简化异步操作： 结合async/await和生成器函数，可以更方便地处理异步操作。

总结：

自定义迭代器是JavaScript中一个强大的工具，它可以让你更灵活地遍历各种数据结构。虽然刚开始可能有点难理解，但只要掌握了迭代器协议和生成器函数，你就可以轻松地创建自己的迭代器，让你的代码更简洁、更高效。

练习：

尝试创建一个迭代器，遍历一个斐波那契数列。
尝试创建一个迭代器，遍历一个图数据结构。

希望今天的讲解对大家有所帮助！如果有什么问题，欢迎随时提问。下次再见！

发表回复 取消回复

发表回复取消回复