Алгоритм построения дерева JSON, зная id и parent id?

199

13 января 2018, 03:01

Есть массив объектов со значениями id и parent_id.

var obj = [{
        id : 1,
        parent_id : 1,
        text: 'Корень'
    },{
        id : 2,
        parent_id : 1,
        text: 'Первый уровень 1'
    },{
        id : 3,
        parent_id : 1,
        text: 'Первый уровень 2'
    },{
        id : 4,
        parent_id : 2,
        text: 'Второй уровень'
    },{
        id : 5,
        parent_id : 4,
        text: 'Третий уровень уровень 1'
    },{
        id : 6,
        parent_id : 4,
        text: 'Третий уровень уровень 2'
    }];

Ищу алгоритм построения дерева такого типа: Где дети вложены в родитель в JSON формате.

var data = [{
        name: 'Корень',
        id: 1,
        parent_id : 1,
        children: [{
            name: 'Первый уровень 1',
            id: 2,
            parent_id : 1,
            children: [{
                name: 'Второй уровень',
                id: 4,
                parent_id : 2
                children: [{
                    name: 'Третий уровень уровень 1',
                    parent_id : 4,
                    id: 5
                },{
                    name: 'Третий уровень уровень 2',
                    parent_id : 4,
                    id: 6
                }]
            }]
        }, {
            name: 'Первый уровень 2',
            id: 3,
            parent_id : 1
        }]
    }];

Как это сделать?

Answer 1

const input = [{ 
        id : 1, 
        parent_id : 1, 
        text: 'Корень' 
    },{ 
        id : 2, 
        parent_id : 1, 
        text: 'Первый уровень 1' 
    },{ 
        id : 3, 
        parent_id : 1, 
        text: 'Первый уровень 2' 
    },{ 
        id : 4, 
        parent_id : 2, 
        text: 'Второй уровень' 
    },{ 
        id : 5, 
        parent_id : 4, 
        text: 'Третий уровень уровень 1' 
    },{ 
        id : 6, 
        parent_id : 4, 
        text: 'Третий уровень уровень 2' 
    }]; 
 
// сначала приведём в соответствие позицию объекта и его id 
// но, что бы не изменять исходный объект, мы создадим другой 
const output = []; 
 
for (const item of input) { 
  // т.к. минимальный идентификатор элемента равен 1, 
  // вычтем из идентификатора единицу, что бы задействовать 
  // индекс 0 (но можно этого и не делать) 
  output[item.id - 1] = item; 
} 
 
// теперь, в массиве output идентификатор каждого элемента 
// соответствует его позии в массиве 
 
// далее, присвоим каждому родителю его детей 
for (const item of output) { 
  if (item.id !== item.parent_id) { 
    // не забываем, что мы вычитали из каждого идентификатора 
    // единицу по этому и здесь тоже вычитаем 
    const parent = output[item.parent_id - 1]; 
 
    // убедимся, что родительский элемент  
    // имеет свойство children 
    if (!Array.isArray(parent.children)) { 
      parent.children = []; 
    } 
 
    // добавляем текущий элемент родителю 
    parent.children.push(item); 
  } 
} 
 
// в итоге, элемент с индексом 0 всегда будет представлять 
// из себя полное дерево 
console.log(output[0]);