如何收集树结构的所有节点，按深度级别分组？

我有一个带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");

来源

2017-09-24 deblocker

是否'depth'引用''.length'阵列.children'的？ – guest271314

@ guest271314：抱歉没有 - 当然，这是它的根的路径长度 – deblocker

这就是它 - 感谢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 */ 
};

来源

2017-09-24 11:59:31 deblocker

您可以使用递归并通过节点和深度参数

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());

来源

2017-09-24 08:42:52 marvel308

有可能在写这一个递归的方式，将受益于尾部优化

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"] 
] 
*/

来源

2017-09-24 10:46:23

如何收集树结构的所有节点，按深度级别分组？

回答

相关问题