Преобразование нескольких массивов соответствующей информации в древовидную структуру классов и подклассов

Question

У меня есть три массива, содержащие различную информацию.Первый содержит список объектов, второй содержит список идентификаторов объектов (в соответствии с первым списком), последний содержит список идентификаторов родительских узлов объекта (также по порядку).

Идентификатор родительского узла каждого объекта соответствует идентификатору другого объекта из всех списков.Но если у объекта нет родительского узла, то это базовый узел (родительский идентификатор = -1, все остальные идентификаторы считаются положительно).

Сами объекты содержат массив, который может содержать другие объекты,Мне нужно найти способ вставить детей в родительские узлы.Эта проблема может стать действительно сложной, потому что дочерние элементы должны быть вставлены сверху вниз, иначе дерево сломается, то есть сначала нужно найти базовые узлы, затем вставить их дочерние элементы, затем эти дочерние элементы и т. Д. И т. Д.

Посмотрев на то, что вы только что прочитали, вы можете подумать, рекурсия !!

NOPE

Я пробовал это, но у 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

Чтобы избежать рекурсии, мы можем начать с хэширования родительских идентификаторов своих детей:

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

becomes

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

Затем начните с -1 и выполните поиск от детей к детям.

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

Answer 2

Вот решение без рекурсии, которое должно учитывать изменения в 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);