我有一個帶childs和父節點的經典Tree結構。現在,我想收集的最低水平(即以相反的順序)開始通過深度分組的所有節點,就像這樣:如何收集樹結構的所有節點,按深度級別分組?
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");
是否'depth'引用''.length'陣列.children'的? – guest271314
@ guest271314:抱歉沒有 - 當然,這是它的根的路徑長度 – deblocker