JavaScript 中的迭代器与生成器在数据结构遍历中的高级应用
字数 715 2025-12-13 09:49:26

JavaScript 中的迭代器与生成器在数据结构遍历中的高级应用

描述

在JavaScript中，迭代器和生成器是处理集合数据遍历的强大工具。本知识点将深入探讨如何利用迭代器和生成器实现复杂的数据结构遍历，包括树结构、图结构的多序遍历，以及如何自定义迭代行为来实现分页遍历、条件遍历等高级场景。

基础概念回顾

1. 迭代器协议

迭代器协议定义了如何依次访问集合中的元素：

// 迭代器对象必须有一个next()方法
const iterator = {
  next() {
    return {
      value: '值',  // 当前迭代的值
      done: false   // 是否迭代完成
    }
  }
}

2. 可迭代协议

可迭代对象必须实现[Symbol.iterator]方法：

const iterable = {
  [Symbol.iterator]() {
    return iterator; // 返回一个迭代器对象
  }
}

树结构的迭代器实现

3. 二叉树节点定义

首先，我们定义一个基本的二叉树节点结构：

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

4. 前序遍历迭代器实现

前序遍历（根-左-右）的迭代器实现：

class BinaryTree {
  constructor(root) {
    this.root = root;
  }

  // 前序遍历的生成器实现
  *preOrderIterator() {
    function* traverse(node) {
      if (node === null) return;
      
      // 先访问根节点
      yield node.value;
      
      // 递归遍历左子树
      if (node.left) {
        yield* traverse(node.left);
      }
      
      // 递归遍历右子树
      if (node.right) {
        yield* traverse(node.right);
      }
    }
    
    yield* traverse(this.root);
  }

  // 实现可迭代协议
  [Symbol.iterator]() {
    return this.preOrderIterator();
  }
}

5. 使用示例

// 创建二叉树
//     1
//    / \
//   2   3
//  / \   \
// 4   5   6
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

const tree = new BinaryTree(root);

// 使用for...of遍历
for (const value of tree) {
  console.log(value); // 输出: 1, 2, 4, 5, 3, 6
}

// 手动使用迭代器
const iterator = tree[Symbol.iterator]();
let result = iterator.next();
while (!result.done) {
  console.log(result.value);
  result = iterator.next();
}

图的广度优先遍历迭代器

6. 图节点定义

class GraphNode {
  constructor(value) {
    this.value = value;
    this.neighbors = []; // 邻接节点
  }
  
  addNeighbor(node) {
    this.neighbors.push(node);
  }
}

7. 广度优先遍历生成器

class Graph {
  constructor() {
    this.nodes = new Map(); // 存储所有节点
  }
  
  *bfsIterator(startNode) {
    if (!startNode) return;
    
    const visited = new Set();
    const queue = [startNode];
    
    while (queue.length > 0) {
      const node = queue.shift();
      
      if (visited.has(node)) continue;
      
      visited.add(node);
      yield node.value;
      
      // 将未访问的邻居加入队列
      for (const neighbor of node.neighbors) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

高级应用：可配置的遍历迭代器

8. 支持多种遍历策略的树迭代器

class ConfigurableTree {
  constructor(root) {
    this.root = root;
  }
  
  // 遍历策略枚举
  static TraversalStrategy = {
    PRE_ORDER: 'preorder',   // 前序
    IN_ORDER: 'inorder',     // 中序
    POST_ORDER: 'postorder', // 后序
    LEVEL_ORDER: 'levelorder' // 层序
  };
  
  // 可配置的遍历迭代器
  *traverse(strategy = 'preorder') {
    switch (strategy) {
      case ConfigurableTree.TraversalStrategy.PRE_ORDER:
        yield* this.preOrder();
        break;
      case ConfigurableTree.TraversalStrategy.IN_ORDER:
        yield* this.inOrder();
        break;
      case ConfigurableTree.TraversalStrategy.POST_ORDER:
        yield* this.postOrder();
        break;
      case ConfigurableTree.TraversalStrategy.LEVEL_ORDER:
        yield* this.levelOrder();
        break;
    }
  }
  
  // 前序遍历生成器
  *preOrder(node = this.root) {
    if (!node) return;
    
    yield node.value;
    yield* this.preOrder(node.left);
    yield* this.preOrder(node.right);
  }
  
  // 中序遍历生成器
  *inOrder(node = this.root) {
    if (!node) return;
    
    yield* this.inOrder(node.left);
    yield node.value;
    yield* this.inOrder(node.right);
  }
  
  // 后序遍历生成器
  *postOrder(node = this.root) {
    if (!node) return;
    
    yield* this.postOrder(node.left);
    yield* this.postOrder(node.right);
    yield node.value;
  }
  
  // 层序遍历生成器
  *levelOrder() {
    if (!this.root) return;
    
    const queue = [this.root];
    
    while (queue.length > 0) {
      const node = queue.shift();
      yield node.value;
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
}

条件遍历生成器

9. 带条件的遍历

class FilteredTreeIterator {
  constructor(root) {
    this.root = root;
  }
  
  // 过滤遍历生成器
  *filteredTraverse(predicate) {
    function* traverse(node) {
      if (!node) return;
      
      if (predicate(node.value)) {
        yield node.value;
      }
      
      yield* traverse(node.left);
      yield* traverse(node.right);
    }
    
    yield* traverse(this.root);
  }
  
  // 分页遍历生成器
  *pagedTraverse(pageSize = 10) {
    let page = [];
    
    for (const value of this.preOrder()) {
      page.push(value);
      
      if (page.length === pageSize) {
        yield page;
        page = [];
      }
    }
    
    if (page.length > 0) {
      yield page;
    }
  }
}

组合迭代器

10. 多个数据源的组合遍历

class CombinedIterator {
  constructor(iterables) {
    this.iterables = iterables;
  }
  
  // 交替遍历多个可迭代对象
  *alternate() {
    const iterators = this.iterables.map(iterable => iterable[Symbol.iterator]());
    let allDone = false;
    
    while (!allDone) {
      allDone = true;
      
      for (const iterator of iterators) {
        const { value, done } = iterator.next();
        
        if (!done) {
          yield value;
          allDone = false;
        }
      }
    }
  }
  
  // 合并遍历
  *merge(comparator = (a, b) => a - b) {
    const values = [];
    
    // 收集每个迭代器的第一个值
    const iterators = this.iterables.map(iterable => {
      const iterator = iterable[Symbol.iterator]();
      const { value, done } = iterator.next();
      
      return {
        iterator,
        value: done ? null : value,
        done
      };
    });
    
    while (true) {
      // 过滤出未完成的迭代器
      const activeIterators = iterators.filter(item => !item.done && item.value !== null);
      
      if (activeIterators.length === 0) break;
      
      // 找到最小值
      const minItem = activeIterators.reduce((min, current) => 
        comparator(current.value, min.value) < 0 ? current : min
      );
      
      yield minItem.value;
      
      // 推进该迭代器
      const { value, done } = minItem.iterator.next();
      minItem.value = done ? null : value;
      minItem.done = done;
    }
  }
}

性能优化与注意事项

11. 内存优化技巧

// 惰性求值生成器 - 只在需要时计算
function* lazyFibonacci() {
  let a = 0, b = 1;
  
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

// 限制迭代次数
function take(iterator, n) {
  return {
    [Symbol.iterator]: function* () {
      let count = 0;
      for (const value of iterator) {
        if (count >= n) return;
        yield value;
        count++;
      }
    }
  };
}

// 使用示例
const fib = lazyFibonacci();
for (const num of take(fib, 10)) {
  console.log(num); // 只计算前10个斐波那契数
}

12. 迭代器状态管理

class StatefulIterator {
  constructor(data) {
    this.data = data;
    this.index = 0;
  }
  
  [Symbol.iterator]() {
    return this;
  }
  
  next() {
    if (this.index >= this.data.length) {
      return { done: true };
    }
    
    return {
      value: this.data[this.index++],
      done: false
    };
  }
  
  // 添加额外方法
  peek() {
    if (this.index >= this.data.length) {
      return null;
    }
    
    return this.data[this.index];
  }
  
  reset() {
    this.index = 0;
    return this;
  }
}

实际应用场景

13. 文件系统遍历

// 模拟文件系统遍历
class FileSystemIterator {
  constructor(rootDirectory) {
    this.root = rootDirectory;
  }
  
  // 深度优先遍历所有文件
  *listFiles(extensions = null) {
    function* traverse(dir) {
      for (const item of dir.children) {
        if (item.type === 'file') {
          if (!extensions || extensions.includes(item.extension)) {
            yield item;
          }
        } else if (item.type === 'directory') {
          yield* traverse(item);
        }
      }
    }
    
    yield* traverse(this.root);
  }
  
  // 按文件大小过滤
  *listLargeFiles(minSize) {
    for (const file of this.listFiles()) {
      if (file.size >= minSize) {
        yield file;
      }
    }
  }
}

总结

  1. 迭代器协议提供了统一的遍历接口，使得任何数据结构都可以被for...of循环使用
  2. 生成器函数（function*）是创建迭代器的便捷语法糖
  3. 通过自定义迭代器，可以实现复杂数据结构的各种遍历方式
  4. 生成器支持惰性求值，可以高效处理大量数据
  5. 迭代器可以组合使用，实现复杂的遍历逻辑
  6. 在实际应用中，迭代器模式在树遍历、图遍历、文件系统操作、分页处理等场景非常有用

这种高级应用展示了JavaScript迭代器与生成器的真正威力，它们不仅仅是语法特性，更是处理复杂数据遍历问题的强大工具。

JavaScript 中的迭代器与生成器在数据结构遍历中的高级应用 描述 在JavaScript中，迭代器和生成器是处理集合数据遍历的强大工具。本知识点将深入探讨如何利用迭代器和生成器实现复杂的数据结构遍历，包括树结构、图结构的多序遍历，以及如何自定义迭代行为来实现分页遍历、条件遍历等高级场景。 基础概念回顾 1. 迭代器协议 迭代器协议定义了如何依次访问集合中的元素： 2. 可迭代协议 可迭代对象必须实现 [Symbol.iterator] 方法： 树结构的迭代器实现 3. 二叉树节点定义 首先，我们定义一个基本的二叉树节点结构： 4. 前序遍历迭代器实现 前序遍历（根-左-右）的迭代器实现： 5. 使用示例 图的广度优先遍历迭代器 6. 图节点定义 7. 广度优先遍历生成器 高级应用：可配置的遍历迭代器 8. 支持多种遍历策略的树迭代器 条件遍历生成器 9. 带条件的遍历 组合迭代器 10. 多个数据源的组合遍历 性能优化与注意事项 11. 内存优化技巧 12. 迭代器状态管理 实际应用场景 13. 文件系统遍历 总结 迭代器协议 提供了统一的遍历接口，使得任何数据结构都可以被 for...of 循环使用 生成器函数 （ function* ）是创建迭代器的便捷语法糖 通过自定义迭代器，可以实现复杂数据结构的各种遍历方式 生成器支持惰性求值，可以高效处理大量数据 迭代器可以组合使用，实现复杂的遍历逻辑 在实际应用中，迭代器模式在树遍历、图遍历、文件系统操作、分页处理等场景非常有用 这种高级应用展示了JavaScript迭代器与生成器的真正威力，它们不仅仅是语法特性，更是处理复杂数据遍历问题的强大工具。