javascript - 如何递归且异步地构建未知大小的树？

Question

我正在尝试检索我网站上给定帖子的评论，但由于 node.js 的异步特性，我无法构建嵌套评论。

getBlock([], function(){});    

function getBlock(comments, callback) {
    comments.forEach(function(comment) {
        getChildComments(comment, function(err, children) {
            if (children) {
                getBlock(children, callback);
            }
            comment.Comments = children;

            /* not sure how to decide when to be done?*/
            callback(null, comments);
        });
    });
}

上面的代码适用于同步代码，但不适用于异步代码，因为我无法判断 comments 何时包含要返回到浏览器的所有数据。

我试图跟踪递归调用，并在剩下 0 个调用时结束，但这是有问题的，有时会根据树结构提前返回。

Answer 1

您可以对尚未完成的工作进行计数，当计数达到零时，您可以调用调用者的回调函数。递归树中执行函数的每个实例都将定义自己的回调，因此只有顶级实例进行的调用才会调用第一个语句中的回调(函数体之外):

function getBlock(comments, callback) {
    if (!comments || !comments.length) {
        // Nothing to do, call back synchronously
        callback(comments);
        return;
    }
    var leftOver = comments.length;
    comments.forEach(function(comment) {
        getChildComments(comment, function(err, children) {
            comment.Comments = children;
            // provide custom callback:
            getBlock(children, function () {
                // only call parent's callback when all is done here:
                if (--leftOver === 0) callback(comments);
            });
        });
    });
}

与您的示例代码不同，上面的代码不能使用空数组来调用，而必须使用您想要检索其下面的层次结构的注释对象数组来调用。要获取所有内容，您需要传递一个带有一个虚拟注释对象的数组，该对象将具有未定义的 id(与没有父级的注释的parentId 引用相匹配)。像这样的事情:

getBlock([container], function(){
    console.log(container);
});

下面是一个工作实现，它使用模拟数据和 setTimeout 来模拟异步 getChildComments:

function Comment(id, text, parentId) {
    this.id = id;
    this.text = text;
    this.parentId = parentId;
}

var mockData = [
    new Comment(1, "Michal Jackson died today"),
    new Comment(2, "How did he die?", 1),
    new Comment(3, "His doctor gave him too much of the white stuff", 2),
    new Comment(4, "He died in his sleep", 2),
    new Comment(5, "Oh my god, this can't be true!?", 1),
    new Comment(6, "He will be greatly missed", 1),
    new Comment(7, "I am working in my garden"),
    new Comment(8, "Happy birthday, friend!"),
    new Comment(9, "Thank you!", 8),   
];

function getChildComments(parentComment, callback) {
    // Mock asynchronous implementation, for testing the rest of the code
    setTimeout(function () {
        var children = mockData.filter(function (comment) {
            return comment.parentId === parentComment.id;
        });
        callback(null, children); 
    }, 0);
}

var container = new Comment(); // dummy node to collect complete hierarchy into
getBlock([container], function(){
    console.log(container);
});

function getBlock(comments, callback) {
    if (!comments || !comments.length) {
        // Nothing to do, call back synchronously
        callback(comments);
        return;
    }
    var leftOver = comments.length;
    comments.forEach(function(comment) {
        getChildComments(comment, function(err, children) {
            comment.Comments = children;
            // provide custom callback:
            getBlock(children, function () {
                // only call parent's callback when all is done here:
                if (--leftOver === 0) callback(comments);
            });
        });
    });
}

性能考虑因素

上面是对“如何递归异步构建未知大小的树”的直接回答，但它可能不是获得最终结果的最有效方法。

您从 Postgres 数据库获取数据，并且可能为每次调用 getChildComments 执行查询:这可能需要相对较长的时间才能完成，并且会给数据库引擎带来相当大的负载。

执行单个查询来检索评论的整个层次结构可能会更有效。