javascript - mongoDB中的迭代树

Question

我有一组这样的数据(例如):

{
    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 并返回该 Node 任何深度的所有子 Node ，例如对于 _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"
    }
]

我编写了几个递归函数来迭代我的 mongodb 文档，但主要问题是我无法处理回调(异步)并且不知道何时以及如何结束递归函数。

我如何使用 mongodb 和 node.js 做到这一点？任何想法都可能有用，谢谢。

Answer 1

您可以使用 2 个著名的算法来实现您的目标
BFS(Breath First search)和 DFS(Depth First Search) .
对于这个问题，BFS 比 DFS 好，因为你可以在 O(logn) 中跟踪你的树您也可以使用 DFS，但您必须以递归方式实现它，并且运行时间将为 O(n)，并且因为您在 node js 中编码，您必须以异步方式实现它，它可能是实现起来有点困难。
为了实现 BFS 算法，你必须使用异步 while 循环，因为你必须在你的 while 循环中有 mongo 查询，如果你使用普通的 javascript，你的 BFS 将无法工作，因为我们正在谈论 node js不是 php!!!
所以首先这是我在 BFS 代码中使用的异步 while 循环

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

这是BFS算法 Node 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) });
    });
}

注意:我还保存了每个查询的深度，因此您可以了解每个查询的深度并知道该查询在树中的位置。