按级别顺序recursion树遍历

我有下面的recursion数据结构和迭代它的方法。 虽然这样做，它应该添加一个唯一的数字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消耗的空间是一个瓶颈，那么可以用其他一些队列实现replace它，并稍微修改一下algorithm。