1

我有以下递归数据结构和迭代它的方法。在这样做的同时，它应该n向每个节点添加一个唯一编号，例如在树的级别顺序遍历中其各自的编号。

var data = {
    children: [
        { children: [ ... ] },
        { children: [ ... ] },
        { children: [ ... ] },
        ...
    ]
}

var process = function (node) {
    node.children.forEach(child, function () {
        process(child);
    });
    return node;
}

如何在不更改数据结构和对处理功能进行最小更改的情况下实现这一点？结果process(data)应该是

var data = {
    n: 1
    children: [
        { n: 2, children: [ ... ] },
        { n: 3, children: [ ... ] },
        { n: 4, children: [ ... ] },
        ...
    ]
}
4

1 回答 1

3

使用队列来存储每个级别的节点。用于null标记一个级别的结束。

最初，将根节点推null送到队列中。然后迭代队列，将每个节点的子节点推入队列并标记非空元素。当你遇到一个null元素时，推送一个新元素。所以两个结果null标志着迭代的结束。

var process = function (node) {
    var queue = [node, null];
    var i = 0, n = 1;
    while (queue[i] != null || (i == 0 || queue[i-1] != null)) {
        if (queue[i] == null) {
            queue.push(null);
        }
        else {
            queue[i].n = n++;
            queue[i].children.forEach(function (elem) {
                queue.push(elem);
            });
        }
        i++;
    }
}

process(data);
console.log(data);

我为队列使用了一个数组，并且没有将访问的元素出列（需要O(n)空间）。如果消耗的空间queue是瓶颈，您可以用其他一些队列实现替换它并稍微改变算法。

于 2013-06-22T02:21:55.377 回答