@Siple

Как сделать дерево объектов из массива?

Есть массив данных:

const arr = [
    { uid: '110', parentUID: '3' },
    { uid: '120', parentUID: '3' },
    { uid: '2', parentUID: '5' },
    { uid: '12', parentUID: '11'  },
    { uid: '1', parentUID: '5' },
    { uid: '11', parentUID: null },
    { uid: '3', parentUID: '5' },
    { uid: '4', parentUID: '5' },
    { uid: '6', parentUID: '5' },
    { uid: '7', parentUID: '5' },
    { uid: '13', parentUID: '11' },
    { uid: '8', parentUID: '5' },
    { uid: '100', parentUID: '3' },
    { uid: '101', parentUID: '3' },
    { uid: '102', parentUID: '3' },
    { uid: '103', parentUID: '3' },
    { uid: '5', parentUID: null },
];


из этого массива нужно превратить в дерево (пример):
const obj = {
'5': { 
        uid: '5', 
        parentUID: null, 
        children: {
            "3": {
                uid: '3', 
                parentUID: '5',
                children: {
                    '110': { uid: '110', parentUID: '3' }
                    .....
                }
            },
            ......
        } 
},
};
  • Вопрос задан
  • 117 просмотров
Решения вопроса 1
0xD34F
@0xD34F Куратор тега JavaScript
function createTreeFromArray(arr, key, parentKey) {
  const tree = Object.fromEntries(arr.map(n => [ n[key], { ...n } ]));
  return Object.fromEntries(Object
    .entries(tree)
    .filter(([ , n ]) => !(tree[n[parentKey]] && ((tree[n[parentKey]].children ??= {})[n[key]] = n)))
  );
}


const tree = createTreeFromArray(arr, 'uid', 'parentUID');
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Не специалист по JS, но похоже там можно сделать проще чем стандартный обход графа в ширину/глубину.

Заведите мап объектов, которые будете собирать. Ключи будудт айдишники, а значения - объекты. У объектов заполните uid, parentUID, пустой Map children и пустой список children_list. Так же запомните куда-то id, у которого null отец.

Потом еще одним проходом по списку всех элементов заполните children_list у всех обхектов в Map из прошлого шага (кладите текущий id в список для parentUID).

Потом еще одним проходом по всем элементам этого Map соберите дерево: обойдите список детей и в Map children кладите 'id' => объект из внешнего Map'а по данному ключу. После прохода можно children_list удалить.

Если я правильно понимаю, как работает JS, то у вас будет не копироваться объект а его ссылка. В итоге в Map будут осодержаться вообще все поддеревья ссылыющееся друг на друга. Можно потом вырвать оттуда объект по ключу id корня и Map удалить.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы