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

问题描述

我有一个带有子节点和父节点的经典树结构.现在，我想从最低级别(即以相反顺序)开始收集按深度分组的所有节点，如下所示:

I have a classic Tree-structure with childs and parent node. Now, i would like to collect all nodes grouped by depth starting from the lowest level (i.e. in reverse order), like this:

nodes[
  ["A4"],
  ["A3","B3"],
  ["A2","B2","C2"],
  ["A1","B1","C1"],
  ["ROOT"]
];

虽然使用递归遍历方法获取深度级别非常简单，但我想知道是否有任何方法可以在 BFS 或 DFS 搜索中的树遍历期间立即获取深度级别.

While getting the depth level by using the recursive traversal approach is very easy, i'm wonder if there is any method to get immediately the depth level during the Tree traversal in a BFS or DFS search.

我知道我可以在节点插入期间存储深度级别，但由于我正在进行大量插入和删除操作，我更愿意一次性收集按级别分组的整个结构.

I'am aware that i could store the depth level during the node insertion, but as i'm doing a lot of insertion and removals, i would prefer to collect the whole structure grouped by level just in one shot.

另外，我根本不喜欢使用 BDS 或 DFS，两者都很好.这是我的实际代码:

Also, i haven't any preference to use BDS or DFS at all, both are just fine. Here is my actual code:

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

推荐答案

就是这样 - 感谢 marvel308 指出需要一个额外的帮助程序 node.depth

That's it - thanks to marvel308 for pointing out that there is required an additional helper 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 */
};

这篇关于如何收集按深度级别分组的树结构的所有节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！