将对应信息的几个数组转换为类和sub类的树状结构

Question

我有三个包含不同信息的数组。第一个包含对象列表，第二个包含对象 ID 列表（与第一个列表对应的顺序），最后一个包含对象的父节点 ID 列表（顺序也相同）。

每个对象的父节点 ID 对应于所有列表中的另一个对象 ID。但是如果对象没有父节点那么它就是一个基节点（父id = -1，所有其他id都正数）。

对象本身包含一个可以容纳其他对象的数组，我需要找到一种方法将子节点插入到它们的父节点中。这个问题可能会变得非常复杂，因为子节点必须从上到下插入，否则树会折断，这意味着必须首先找到基节点，然后插入它们的子节点，然后插入那些子节点，等等

看你刚刚读到的内容，你可能会想，递归！！

没有

我试过了，但是javascript对可以完成多少递归有限制，当它们有太多的对象需要排序时，就会发生超出堆栈的错误。

对于那些对我之前如何解决它感兴趣的人，这是我的代码：

class Tree{
    constructor (indices, sorting_information){
        this.base_nodes = [];
        for (var i = 0; i < sorting_information.length; i++){
            if (!(indices.includes(sorting_information[i]))){
                var relevant_info = {
                    location: i,
                    id_num: indices[i],
                };
                var base_node = new Node(relevant_info, indices, sorting_information);
                this.base_nodes.push(base_node);
            }
        }
    }
}
class Node {
    constructor (id_info, indices, sorting_information){
        this.location = id_info.location;
        this.id = id_info.id_num;
        this.nodes = [];
        if (!(this.id == -1)){
            for (var i = 0; i < sorting_information.length; i++){
                if (sorting_information[i] == this.id){
                    var relevant_info = {
                        location: i,
                        id_num: indices[i],
                    };
                    var node = new Node(relevant_info, indices, sorting_information);
                    this.nodes.push(node);
                }
            }
        }
    }
}

为了使此代码起作用，只需要最后两个列表，因为它创建了一个可用于组织第一个列表的骨架结构。

创建了一个Tree实例，构造函数的第一个和第二个参数分别是第一个和第二个数组。构造函数找到基节点，然后在实例化基节点时找到它们的子节点，等等

预期输入：

var nodes = [node_0, node_1, node_2, node_3, node_4, node_5, node_6];
var indices = [0, 1, 2, 3, 4, 5, 6]
var sorting_information = [1, -1, 1, 0, -1, 4, 4]

预期输出：

var base_nodes = [node_1, node_4]; 
node_1.children = [node_0, node_2];
node_4.children = [node_5, node_6];
node_0.children = [node_3];

请注意，数据树不一定采用二进制形式。

我从很多角度看过这个问题，但一直头疼任何帮助将不胜感激

Answer 1

这是一个没有递归的解决方案，应该考虑 sorting_information 上的变化。

此解决方案基于您问题中的预期输入 和相应的预期输出。它产生一个数组是您预期的对象输出：

var nodes = ['node_0', 'node_1', 'node_2', 'node_3', 'node_4', 'node_5', 'node_6'];
var indices = [0, 1, 2, 3, 4, 5, 6];
var sorting_information = [1, -1, 1, 0, -1, 4, 4];
var tree = [];

var out = sorting_information
          // Create object of ordered nodes
          .map((v, idx) => {return { node: nodes[idx], order: v}})
          // Sort on the ordering
          .sort((a, b) => a.order - b.order)
// Use a set to reduce to unique values of sorting info
let sort_set = new Set(sorting_information.sort());
// Loop through sort orders
sort_set.forEach(i=>{
   let level = (i < 0)? "base" : "node_"+i+"_children";
   // Push     filtered nodes
   tree.push({[level]: out.filter((node)=>node.order === i)
   // reduced to only the node object
   .map(node=>node.node)});
});
console.log(tree);

Answer 2

为了避免递归，我们可以首先将 parent ID 散列到它们的 children:

[1, -1, 1, 0, -1, 4, 4]

becomes

{
   1: [0, 2],
  -1: [1, 4],
   etc.
}

然后从-1开始，执行从children到children的搜索。

function hash(A){
  return A.reduce((acc, x, i) => {
     acc[x] = acc[x] ? acc[x].concat(i) : [i]
     return acc
  }, {})
}

function Node(id){
  this.id = id
  this.nodes = []
}

function f(A){
  const h = hash(A) 
  const tree = new Node(-1)
  let stack = [[tree, h[-1]]]
  
  while (stack.length){
    const [parent, children] = stack.pop()
    
    for (let id of children){
      const child = new Node(id)
      parent.nodes.push(child)
      stack.push([child, h[id] || []])
    }
  }
  
  return tree
}

var A = [1, -1, 1, 0, -1, 4, 4]

console.log(JSON.stringify(f(A)))

将对应信息的几个数组转换为类和sub类的树状结构

Converting several arrays of corresponding information to tree-like structure of classes and subclasses

javascript

algorithm

tree

recursion

conceptual