javascript - 在 Javascript 中递归遍历树

Question

这是在 Java 中完成的 super 简单的任务，但是 javascript 的异步特性使这个任务(对我来说)几乎不可能，至少就我现在的知识而言是这样。(我不是要抨击 javascript。喜欢这种语言!) .

这是非常基础的。在我的 mysql 数据库中，顶级树的父级为 null。找 child 很容易。 children 可以使用线路。树的深度是可变的。

    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;
}

基本上，该方法测试树是否有可用的行。如果是这样，它会将所有这些添加到一个集合中。如果没有，它将继续，直到找到行。

mysql Node 库的异步特性将这个任务变成了 hell 。

这是我现在拥有的

   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);
     });

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

如果这没有意义，请告诉我。我会尝试重构。我希望我明白了一些要点。我不想使用像 Fibers 这样的东西来完成这项工作，但我别无选择。谢谢。

Answer 1

您对 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最后一行实际上并没有做太多事情，因为它不会改变它所调用的数组。您可能实际上不希望它成为 dig绕过 treeArray而不是定义一个新的 treeSet就像在getBranches .所以，如果是这样，它会附加 treeArray每次都结束。

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

treeSet = treeSet.concat(subSet);

而且，您必须更换 for使用异步迭代器循环此循环，因为循环不会在继续之前等待异步操作。 async library如果您愿意尝试的话，这里有几个选项。

所以，有多个 treeSet小号，concat , 和 async.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);
});