Javascript：涉及I / O的定向树的DFS遍历
给定一个定向树T，每个节点的子节点数可变，我想find一个从根开始的“好”节点的PATH_SIZE大小的path。
每个节点都有一个isGood()方法和一个按照预期工作的getChildren()方法。
一个简单的DFSrecursion解决scheme将如下所示：（请纠正我，如果我错了）
function findGoodPath(node, depth){ if(!node.isGood()){ return null; } else if (depth==PATH_SIZE){ return [node]; } var children = node.getChildren(); for (var i=0; i<children.length; i++){ var result = findGoodPath(children[i], depth+1); if (result){ return result.concat([node]); } } return null; }
调用findGoodPath(root, 1)应该find一个结果，如果存在的话。
现在的问题是 ：节点对象的getChildren()方法实际上是一个asynchronous方法，在后台执行I / O操作。 它什么都不返回，并期望一个callback参数来处理返回的孩子。
修改后的代码解决scheme（这是错误的 ）可能看起来像这样：
function findGoodPath(node, depth){ if(!node.isGood()){ return null; } else if (depth==PATH_SIZE){ return [node]; } node.getChildren(function(children){ for (var i=0; i<children.length; i++){ var result = findGoodPath(children[i], depth+1); if (result){ return result.concat([node]); } } }); }
这个解决scheme将不起作用：单个节点的子节点的所有getChildren方法将立即被调用，因此它将实际执行一个BFS。 更糟糕的是，返回语句与匿名callback函数相关联，并在封闭函数完成运行后执行。
很明显，需要某种stream量控制机制。 什么是这个问题的简单而优雅的解决scheme？
更新：我已经接受了塞巴斯蒂安的答案，因为它解决了这个问题的recursion，这就是我提出的问题。 我也发布了一个使用asynchronous库while循环的答案，这是我最终使用的。 塞巴斯蒂安很友善地在这里testing这两种方法。 （剧透：表演完全相同）
首先，如果你想深度等于PATH_SIZE，我认为你必须调用findGoodPath（children [i]，depth + 1）。
那么，你确实有一个closures的问题。 通过asynchronous调用，您总是与一个不是您想要的节点实例连接。
你可以做的一个方法是：
node.getChildren((function(_node) { return function(children){ for (var i=0; i<children.length; i++){ var result = findGoodPath(children[i], depth); if (result){ return result.concat([_node]); } } }); })(node));
但是，我认为这只是混合同步function和asynchronousfunction的问题的一部分。 该行：
var result = findGoodPath(children[i], depth)
被写为一个同步调用，而findGoodPath是一个asynchronous函数，所以它也必须用callback书写！
希望能帮助到你
PS：这将有助于有一个jsfiddle …
更新：只是一个尝试。 正如我无法testing，它不工作，但这是主意。 我无法弄清楚是否需要在第二个findGoodPath调用中创build另一个作用域，就像在getChildren调用
function findGoodPath(node, depth, callback){ if(!node.isGood()){ return callback(null); } else if (depth==PATH_SIZE){ return callback([node]); } node.getChildren((function(_node, _callback) { return function(children){ var node = _node, callback = _callback; for (var i=0; i<children.length; i++){ findGoodPath(children[i], depth, function(result) { if (result){ return callback(result.concat([node])); } }); } }); })(node, callback)); }
我现在不是百分百关注的焦点，但是我几乎可以肯定的是， Async.js seriestasks对你来说是正确的解决scheme（如果不是seriestasks，我敢打赌，Async.js中有另一个控制stream程可以做到这一点。
好的，所以有几种方法可以实现asynchronousDFS遍历。 由于asynchronousrecursion有一个变得有点丑陋的倾向，我决定摆脱recursion。
我首先重新实现了使用while循环而不是recursion的函数的同步版本：
function findGoodPathLoop(root){ var nodesToVisit = [{data: root, path:[]}]; while (nodesToVisit.length>0){ var currentNode = nodesToVisit.pop(); if (currentNode.data.isGood()){ var newPath = currentNode.path.concat(currentNode.data); if (newPath.length==PATH_SIZE){ return newPath; } else { var childrenNodes = currentNode.data.getChildren().map(function(child){ return {data: child, path: newPath}; }); nodesToVisit = nodesToVisit.concat(childrenNodes); } } } return null; }
注意 ： 我保存了每个节点的整个path，这不是必须的，只要保存深度并保留当前path的数组，虽然有点麻烦。
然后我使用asynchronous库将此函数转换为asynchronous函数，用async的while()函数replace标准的while()函数：
function findGoodPathAsync(root, pathCallback){ var result = null; var nodesToVisit = [{data: root, path:[]}]; async.whilst( function(){ return nodesToVisit.length>0 && result==null ; }, function(next) { var currentNode = nodesToVisit.pop(); if (currentNode.data.isGood()){ var newPath = currentNode.path.concat(currentNode); if(newPath.length==PATH_SIZE){ result = newPath; next(); } else { currentNode.data.getChildren(function(children){ var childrenNodes = children.map(function(child){ return {data: child, path: newPath}; }); nodesToVisit = nodesToVisit.concat(childrenNodes); next(); }); } } else { next(); } }, function(err) { //error first style callback pathCallback(err, result); } ); }
不是一个漂亮的，但它是可读的，它的工作。