Рекурсивный обход дерева в порядке уровней

Question

У меня есть следующая рекурсивная структура данных и метод, повторяющийся над ней. При этом следует добавить уникальный номер 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: [ ... ] },
        ...
    ]
}

Answer 1

Используйте очередь для хранения узлов на каждом уровне. использование 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 является узким местом, вы можете заменить его другой реализацией очереди и немного изменить алгоритм.