按级别顺序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: [ ... ] }, ... ] }
使用队列来存储每个级别的节点。 使用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。