在Javascript中recursion遍历树

这在Java中是非常简单的任务,但是JavaScript的asynchronous特性使得这个任务(对我来说)几乎不可能,至less现在我已经知道了(我没有试图去bash javascript,喜欢这种语言!

这是非常基本的。 顶级树在我的mysql数据库中有一个null的父项。 很容易find孩子。 孩子们有可用的线路。 树的深度是可变的。

private static Set<Tree> getBranches( Tree trunk ) { Set<Tree> treeSet = new HashSet<Tree>(); if ( trunk != null ) { if ( trunk.hasLines() ) { //queries if tree has lines. returns true or false treeSet.add( trunk ); } for ( Tree tree : trunk.treeList ) { treeSet.addAll( getBranches( tree ) ); } } return treeSet; } 

基本上这个方法testing树是否有可用的行。 如果是这样,它将所有这些添加到一个集合。 如果没有,则继续,直到find行。

mysql节点库的asynchronous特性把这个任务变成了地狱。

这是我现在拥有的

  function hasLines(tree_id, callback) { var ret; pool.query('SELECT * from pkg_line_tree where tree_id = ?', [tree_id], function (err, rows) { if (rows.length > 0) { ret = true; } else { ret = false; } callback(ret); }); } function dig(tree_id, treeArray, callback) { pool.query('SELECT * from tree where parent_id = ?', [tree_id], function (err, rows) { if (rows) { for (var i in rows) { hasLines(rows[i].tree_id, function (t) { if (t) { treeArray.push(rows[i].tree_id); } else { treeArray.concat(dig(rows[i].tree_id, treeArray)); } }); } if (callback) { callback(treeArray); } } }); return treeArray; } var treeArray = []; dig(52, treeArray, function (t) { res.json(t); }); 

我真的只需要输出在这个根树中可用的所有孩子。

请让我知道这是否没有道理。 我会尝试重构。 我希望我能得到一些意见。 我不想用Fibers这样的东西来完成这个任务,但是我没有select。 谢谢。

您使用dig()目前不一致:

 // asynchronous with callback dig(52, treeArray, function (t) { res.json(t); }); // then synchronous with `return`? treeArray.concat(dig(rows[i].tree_id, treeArray)); 

另外,最后一行的concat实际上并没有太多的工作,因为它不会改变它所调用的数组。 你可能实际上并不希望它像treeArray那样进行dig ,而不是像在getBranches那样定义一个新的getBranches 。 所以,如果是这样,它会每次将treeArray附加到它自己的末尾。

你仍然可以用多个treeSet使用concat ,但是你必须存储它的return值:

 treeSet = treeSet.concat(subSet); 

而且,你必须用asynchronous迭代器replacefor循环,因为在继续之前,循环不会等待asynchronous操作。 async库有几个选项,如果你想尝试。

所以,使用多个treeSetconcatasync.forEachSeries ,你可以尝试:

 function dig(tree_id, callback) { var treeSet = []; hasLines(tree_id, function (yep) { if (yep) { treeSet.push(tree_id); } pool.query('SELECT * from tree where parent_id = ?', [tree_id], function (err, rows) { function each(row, next) { dig(row.tree_id, function (subSet) { treeSet = treeSet.concat(subSet); next(null); }); } function done() { callback(treeSet); } async.forEachSeries(rows, each, done); }); }); } dig(52, function (treeSet) { res.json(treeSet); }); 

你必须使用asynchronoushttps://github.com/caolan/async

我已经修改你的挖function使用async的forEach方法

 function dig(tree_id, treeArray, AllDone) { pool.query('SELECT * from tree where parent_id = ?', [tree_id], function (err, rows) { if (rows) { async.forEach( rows, function(row, callback) { hasLine(row.tree_id, function(t){ if (t) { treeArray.push(row.tree_id); callback(); } else { dig(row.tree_id, treeArray, callback); } }); }, function(err) { if (err) AllDone(err, treeArray); else AllDone(null, treeArray); }); } else AllDone(null, treeArray) }); } treeArray = []; dig(52, treeArray, function(err, t) { res.json(t); }); 

假设行是一个数组.. forEach遍历每一行并执行hasLine,每次迭代将在完成时调用callback函数,并且当所有callback函数被调用时将调用AllDone 。 这里棘手的部分是recursion,每个recursion调用将有一个forEach循环,只有当所有的callbacks完成后,它才会调用AllDone方法。

然而, forEach并行执行,所以命令不被保存

我认为这应该工作,如果你不关心秩序。

编辑你可以使用forEachSeries来解决订单问题。

我想你需要一个柜台。 计数器表示需要遍历的tree_id的个数。 当你得到一个节点的子节点时,通过子节点数增加它,遍历一个节点后,减小它。 当它等于0时,遍历结束。

 //the number of tree_id need to dig var counter = 1; function dig(tree_id) { pool.query('SELECT * FROM tree WHERE parent_id = ?', [tree_id] , function (err, rows) { if (rows.length) { counter += rows.length; rows.forEach(function (row) { dig(row.tree_id); }) } hasLines(tree_id, function (b) { if (b) treeArray.push(tree_id); }); --counter; if (counter == 0) endOfDig(); }) } dig(1); function endOfDig() { //...following code }