在mongoDB中迭代树

我有这样的数据的集合（例如）：

{ name : "john" , _id : "0" }, { name : "Richard" , parent_id : "0" , _id : "1" }, { name : "Kevin" , parent_id : "0" , _id : "2" }, { name : "William" , parent_id : "1" , _id : "3" }, { name : "George" , parent_id : "3" , _id : "4" } 

我试图写一个函数来接收一个_id并返回所有这个节点深度的所有孩子，例如_id = 0我需要这样的东西：

 [ { name : "Richard" , parent_id : "0" , depth : "1" , _id : "1" }, { name : "Kevin" , parent_id : "0" , depth : "1" , _id : "2" }, { name : "William" , parent_id : "1" , depth : "2" , _id : "3" }, { name : "George" , parent_id : "3" , depth : "3" , _id : "4" } ] 

我写了几个recursion函数来迭代我的mongodb文档，但主要问题是我无法处理callback（asynchronous），不知道何时以及如何结束recursion函数。

我怎样才能做到这一点与Mongodb和Node.js？ 任何想法可以是有用的，谢谢。

Answer 1

有一个着名的algorithm，你可以用来实现你的目标
BFS（呼吸优先search）和DFS（深度优先search） 。
对于这个问题BFS比DFS更好，因为你可以在O（logn）中跟踪你的树也可以使用DFS，但是你必须以recursion的方式来实现它，运行时间将是O（n），并且因为你正在编码节点js你必须在asynchronous中实现它，实现它可能有点困难。
为了实现BFSalgorithm，你必须使用asynchronouswhile循环，因为你必须在你的while循环中有mongo查询，如果你使用正常的javascript，你的BFS将无法工作，因为我们正在谈论节点js而不是php！
所以首先，这是我在BFS代码中使用的asynchronouswhile循环

 function asyncLoop(iterations, func, callback ,foo) { var done = false; var loop = { next: function() { if (done) { return; } if (iterations) { func(loop); } else { done = true; if(callback) callback(foo); } }, isEnd : function(){ return done ; } , refresh : function(it){ iterations = it ; }, break: function() { done = true; callback(); } }; loop.next(); return loop; } 

这是BFSalgorithm节点的js代码：

 function bfs (_id ,callback){ _id = String(_id); var q = [] ,res = [] ; db.tasks.findOne({ _id : _id }).lean().exec(function(err,root){ root.depth = 0 ; q.push(root); asyncLoop(q.length ,function(loop){ res.push(q[0]); db.tasks.find({ _parent : q[0]._id }).lean().exec(function(err,new_nodes){ if(err) console.log(err); else { var d = q[0].depth ; q.shift(); loop.refresh(new_nodes.length + q.length); if(new_nodes.length > 0){ new_nodes.forEach(function(new_node){ new_node.depth = d+1 ; q.push(new_node); }); } loop.next(); } }); },function(){ callback(res) }); }); } 

注：我还保存每个查询的深度，以便您可以深入查询每个查询，并知道此查询在树中的位置。