javascript - 如何在javascript中的迭代器生成器中实现递归遍历？

Question

假设我有一棵树，在 javascript 中如下所示:

let rootNode = {name:'', children:[
                   {name:'0', children:[
                       {name:'00', children:[]},
                       {name:'01', children:[
                           {name:'010', children:[]},
                       ]},
                       {name:'02', children:[]},
                   ]},
                   {name:'1', children:[
                       {name:'10', children:[]},
                   ]},
               ]};

我想对其进行预序遍历，我可以这样做:

function preOrderTraversalRecursive(rootNode, visitNodeCallback) {
    function recurse(node) {
        visitNodeCallback(node);
        for (let childNode of node.children)
          recurse(childNode);
    }
    recurse(rootNode);
};
console.log("Pre-order traveral, recursive:");
preOrderTraversalRecursive(rootNode, function visitNodeCallback(node) {
    console.log("  '"+node.name+"'");
});

它给出了预期的输出:

  Pre-order traveral, recursive:
    ''
    '0'
    '00'
    '01'
    '010'
    '02'
    '1'
    '10'

现在假设我想做同样的事情 ES6 生成器风格。我认为它看起来像这样:

function *preOrderGeneratorIteratorRecursive(rootNode) {
    function recurse(node) {
        yield node;
        for (let childNode of node.children)
            recurse(childNode);
    }
    recurse(rootNode);
};
console.log("Pre-order generator iterator, recursive:");
for (let node of preOrderGeneratorIteratorRecursive(rootNode)) {
    console.log("  '"+node.name+"'");
}

但显然这是非法的:Uncaught SyntaxError: Unexpected strict mode reserved word at the yield。

令人失望!我缺少一些语法吗？使生成器表达此算法的最简洁方法是什么？也许使用一些辅助库？

我知道我可以使用如下所示的显式堆栈，但由于以下几个原因，这并不令人满意:(1) 逻辑模糊到没有的地步使用生成器的可读性优势；还不如回去到带有回调的递归版本，以及(2) 这不是真正相同的算法，因为它是向后迭代的在每个 node.children 上。特别是，这意味着它不会工作如果 node.children 是其他类型的可迭代对象，可能来自另一个生成器。

function *preOrderTraversalIteratorGeneratorExplicitStackCheating(rootNode) {
  let stack = [rootNode];
  while (stack.length > 0) {
    let node = stack.pop();
    yield node;
    for (let i = node.children.length-1; i >= 0; --i) // backwards
      stack.push(node.children[i]);
  }
} // preOrderIteratorGeneratorExplicitStackCheating
console.log("Pre-order traveral of tree with explicit stack, cheating:");
for (let node of preOrderTraversalIteratorGeneratorExplicitStackCheating(rootNode)) {
  console.log("  '"+node.name+"'");
}

要明确:我对隐藏可怕细节的特殊用途助手不感兴趣一个显式堆栈遍历实现。我想知道是否有一种方法可以清楚地编写迭代器生成器算法，即使它们恰好是递归的。

Answer 1

这确实是通过 yield* 运算符提供的。从本质上讲，您需要将其视为一个生成器将其功能委托(delegate)给另一个生成器。 (实际上，您可以委托(delegate)给任何可迭代的值。)

例如，您可以这样做:

function *pointlessGenerator() {
    yield* [1, 2, 3, 4];
} 

这将产生 1、2、3 和 4，因为 yield* 运行迭代器并依次产生该迭代器的所有值。如果您传递生成器，则会发生完全相同的行为。

在你的情况下，你想使 recurse 成为一个生成器，然后用 yield* 调用它:

function *preOrderGeneratorIteratorRecursive(rootNode) {
    function *recurse(node) {
        yield node;
        for (let childNode of node.children)
            yield* recurse(childNode);
    }
    yield* recurse(rootNode);
};
console.log("Pre-order generator iterator, recursive:");
for (let node of preOrderGeneratorIteratorRecursive(rootNode)) {
    console.log("  '"+node.name+"'");
}