Создать рекурсивную функцию, которая принимает плоский массив и преобразует его в древовидную структуру данных.

Question

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

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

input:

 const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];

output:

{
  id: 1,
  parent: null,
  value: 'Make Breakfast',
  children: [
     {
       id: 2,
       parent: 1,
       value: 'Brew coffee',
       children: [
          { id: 3, parent: 2, value: 'Boil water' },
          { id: 4, parent: 2, value: 'Grind coffee beans' },
          { id: 5, parent: 2, value: 'Pour water over coffee grounds'     }
       ]
     }
  ]
}


funciton toTree(data) {
  customtoTree (data, null);
}

function customToTree (data, parent) {
  const out = [];
  data.forEach((obj) => {
    if (obj.parent === parent) {
      const children = customToTree(data,obj.parent);

      if (children.length) {
        obj[children[0]] = children;
      }
      const {id,parent, ...content} = obj;
      out.push(content);
    }
  });
  return out;
}

Я быМне действительно нравится понимать правильную логику о том, как это сделать, и думать об этом, и как это сделать, не предоставляя явно родителя.

Answer 1

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

 const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];

const tasksById = Object.create(null);

// abusing filter to do the work of a forEach() 
// while also filtering the tasks down to a list with `parent: null`
const root = tasks.filter((value) => {
  const { id, parent } = value;
  
  tasksById[id] = value;
  
  if(parent == null) return true;
  
  (tasksById[parent].children || (tasksById[parent].children = [])).push(value);
});

console.log("rootNodes", root);
console.log("tasksById", tasksById);

.as-console-wrapper{top:0;max-height:100%!important}

Answer 2

У меня был такой же вопрос во время интервью, и я не смог его решить.Я также был озадачен тем, что функция должна принимать массив только в качестве первого и единственного аргумента.

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

Внутри функции вам нужно только проверить, является ли второй аргумент неопределенным, если это так, вы ищете в массиве свой корневой объект и присвойте его второму аргументу.

Итаквот мое решение, надеюсь оно будет понятнее:

function toTree(arr, item) {

        if (!item) {
            item = arr.find(item => item.parent === null)
        }

        let parent = {...item}
        parent.children = 
            arr.filter(x => x.parent === item.id)
                .sort((a, b) => a.id - b.id)
                .map(y => toTree(arr, y))

        return parent     
}

toTree(tasks)

Answer 3

Я не смог проверить больше тестовых случаев, но это то, что я быстро смог придумать, которое проходит ваш вариант использования, выглядит не очень хорошо, я бы порекомендовал использовать его в качестве исходной структуры, а затем основываться на ней,Кроме того, я предполагаю, что задачи отсортированы по возрастанию в порядке возрастания по родителю, т.е. дочерний элемент появится только после своего родителя в массиве задач

const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' },
  { id: 6, parent: 5, value: 'Pour water over coffee grounds' },
  { id: 7, parent: 5, value: 'Pour water over coffee grounds' }
];

function Tree() {
  this.root = null;
  // this function makes node root, if root is empty, otherwise delegate it to recursive function
  this.add = function(node) {
    if(this.root == null)
      this.root = new Node(node);
    else
      // lets start our processing by considering root as parent
      this.addChild(node, this.root);
  }

  this.addChild = function(node, parent) {
    // if the provided parent is actual parent, add the node to its children
    if(parent.id == node.parent) {
      parent.children[node.id] = new Node(node);
    } else if(parent.children[node.parent]) {
      // if the provided parent children contains actual parent call addChild with that node
      this.addChild(node, parent.children[node.parent])
    } else if(Object.keys(parent.children).length > 0) {
      // iterate over children and call addChild with each child to search for parent
      for(let p in parent.children) {
        this.addChild(node, parent.children[p]);
      }
    } else {
      console.log('parent was not found');
    }
  }
}

function Node (node) {
  this.id = node.id;
  this.parent = node.parent;
  this.value = node.value;
  this.children = {};
}

const tree = new Tree();

// We are assuming that tasks are sorted in ascending order by parent

for(let t of tasks) {
  tree.add(t);
}

console.log(JSON.stringify(tree.root))

Дайте мне знать, если у вас есть вопросы.Давайте взломать его вместе