如何收集按深度级别分组的树结构的所有节点?
How to collect all nodes of a Tree structure, grouped by depth level?
我有一个带有子节点和父节点的经典树结构。现在,我想收集从最低级别开始按深度分组的所有节点(即以相反的顺序),如下所示:
nodes[
["A4"],
["A3","B3"],
["A2","B2","C2"],
["A1","B1","C1"],
["ROOT"]
];
虽然使用递归遍历方法获取深度级别非常容易,但我想知道是否有任何方法可以在 BFS 或 DFS 搜索中的树遍历过程中立即获取深度级别。
我知道我可以在节点插入期间存储深度级别,但由于我正在进行大量插入和删除操作,我更愿意一次收集按级别分组的整个结构。
此外,我根本不喜欢使用 BDS 或 DFS,两者都很好。这是我的实际代码:
function Node(code, parent) {
this.code = code;
this.children = [];
this.parentNode = parent;
}
Node.prototype.addNode = function (code) {
var l = this.children.push(new Node(code, this));
return this.children[l-1];
};
Node.prototype.dfs = function (leafCallback) {
var stack=[this], n, depth = 0;
while(stack.length > 0) {
n = stack.pop();
if(n.children.length == 0) {
if(leafCallback) leafCallback(n, this);
continue;
}
for(var i=n.children.length-1; i>=0; i--) {
stack.push(n.children[i]);
}
depth++; // ???
}
};
var tree = new Node("ROOT");
tree.addNode("A1").addNode("A2").addNode("A3").addNode("A4");
tree.addNode("B1").addNode("B2").addNode("B3");
tree.addNode("C1").addNode("C2");
您可以使用递归并传递节点和深度作为参数
function Node(code, parent) {
this.code = code;
this.children = [];
this.parentNode = parent;
}
Node.prototype.addNode = function (code) {
var l = this.children.push(new Node(code, this));
return this.children[l-1];
};
let result = [], depth = {};
function dfs(node){
node.depth = 0;
let stack = [node];
while(stack.length > 0){
let root = stack[stack.length - 1];
let d = root.depth;
result[d] = result[d] || [];
result[d].push(root.code);
stack.length--;
for(let element of root.children){
element.depth = root.depth + 1;
stack.push(element);
}
}
}
var tree = new Node("ROOT");
tree.addNode("A1").addNode("A2").addNode("A3").addNode("A4");
tree.addNode("B1").addNode("B2").addNode("B3");
tree.addNode("C1").addNode("C2");
dfs(tree);
console.log(result.reverse());
可以以递归方式编写,这将受益于尾部优化
function reduceTree(tree) {
const getCode = n => n.code;
const _reduce = (level = [tree], acc = [[getCode(tree)]], depth = 1) => {
const children = level.reduce((a, e) => a.concat(e.children), []);
if (!children.length) {
return acc;
}
acc[depth] = children.map(getCode);
return _reduce(children, acc, depth + 1);
};
return _reduce().reverse();
}
reduceTree(tree);
/*
[
["A4"],
["A3", "B3"],
["A2", "B2", "C2"],
["A1", "B1", "C1"],
["ROOT"]
]
*/
就是这样 - 感谢 marvel308 指出需要额外的助手 node.depth
function Node(code, parent) {
this.code = code;
this.depth = -1;
this.children = [];
this.parentNode = parent;
}
Node.prototype.dfs= function() {
var result = [], stack = [];
this.depth = 0;
stack.push(this);
while(stack.length > 0) {
var n = stack[stack.length - 1], i = n.depth;
if(!result[i]) result.push([]);
result[i].push(n); /* get node or node.code, doesn't matter */
stack.length--;
var children = n.children;
/* keep the original node insertion order, by looping backward */
for(var j = n.children.length - 1; j >= 0; j--) {
var c = children[j];
c.depth = n.depth + 1;
stack.push(c);
}
}
return result.reverse(); /* return an array */
};
我有一个带有子节点和父节点的经典树结构。现在,我想收集从最低级别开始按深度分组的所有节点(即以相反的顺序),如下所示:
nodes[
["A4"],
["A3","B3"],
["A2","B2","C2"],
["A1","B1","C1"],
["ROOT"]
];
虽然使用递归遍历方法获取深度级别非常容易,但我想知道是否有任何方法可以在 BFS 或 DFS 搜索中的树遍历过程中立即获取深度级别。
我知道我可以在节点插入期间存储深度级别,但由于我正在进行大量插入和删除操作,我更愿意一次收集按级别分组的整个结构。
此外,我根本不喜欢使用 BDS 或 DFS,两者都很好。这是我的实际代码:
function Node(code, parent) {
this.code = code;
this.children = [];
this.parentNode = parent;
}
Node.prototype.addNode = function (code) {
var l = this.children.push(new Node(code, this));
return this.children[l-1];
};
Node.prototype.dfs = function (leafCallback) {
var stack=[this], n, depth = 0;
while(stack.length > 0) {
n = stack.pop();
if(n.children.length == 0) {
if(leafCallback) leafCallback(n, this);
continue;
}
for(var i=n.children.length-1; i>=0; i--) {
stack.push(n.children[i]);
}
depth++; // ???
}
};
var tree = new Node("ROOT");
tree.addNode("A1").addNode("A2").addNode("A3").addNode("A4");
tree.addNode("B1").addNode("B2").addNode("B3");
tree.addNode("C1").addNode("C2");
您可以使用递归并传递节点和深度作为参数
function Node(code, parent) {
this.code = code;
this.children = [];
this.parentNode = parent;
}
Node.prototype.addNode = function (code) {
var l = this.children.push(new Node(code, this));
return this.children[l-1];
};
let result = [], depth = {};
function dfs(node){
node.depth = 0;
let stack = [node];
while(stack.length > 0){
let root = stack[stack.length - 1];
let d = root.depth;
result[d] = result[d] || [];
result[d].push(root.code);
stack.length--;
for(let element of root.children){
element.depth = root.depth + 1;
stack.push(element);
}
}
}
var tree = new Node("ROOT");
tree.addNode("A1").addNode("A2").addNode("A3").addNode("A4");
tree.addNode("B1").addNode("B2").addNode("B3");
tree.addNode("C1").addNode("C2");
dfs(tree);
console.log(result.reverse());
可以以递归方式编写,这将受益于尾部优化
function reduceTree(tree) {
const getCode = n => n.code;
const _reduce = (level = [tree], acc = [[getCode(tree)]], depth = 1) => {
const children = level.reduce((a, e) => a.concat(e.children), []);
if (!children.length) {
return acc;
}
acc[depth] = children.map(getCode);
return _reduce(children, acc, depth + 1);
};
return _reduce().reverse();
}
reduceTree(tree);
/*
[
["A4"],
["A3", "B3"],
["A2", "B2", "C2"],
["A1", "B1", "C1"],
["ROOT"]
]
*/
就是这样 - 感谢 marvel308 指出需要额外的助手 node.depth
function Node(code, parent) {
this.code = code;
this.depth = -1;
this.children = [];
this.parentNode = parent;
}
Node.prototype.dfs= function() {
var result = [], stack = [];
this.depth = 0;
stack.push(this);
while(stack.length > 0) {
var n = stack[stack.length - 1], i = n.depth;
if(!result[i]) result.push([]);
result[i].push(n); /* get node or node.code, doesn't matter */
stack.length--;
var children = n.children;
/* keep the original node insertion order, by looping backward */
for(var j = n.children.length - 1; j >= 0; j--) {
var c = children[j];
c.depth = n.depth + 1;
stack.push(c);
}
}
return result.reverse(); /* return an array */
};