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

Question

[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' }
                    .....
                }
            },
            ......
        } 
},
};

Answer 1

[0xD34F]

function createTreeFromArray(arr, key, parentKey) {
  const tree = Object.fromEntries(arr.map(n => [ n[key], { ...n } ]));

  return Object.fromEntries(Object.entries(tree).filter(([ , n ]) => {
    return !(tree[n[parentKey]] && ((tree[n[parentKey]].children ??= {})[n[key]] = n));
  }));
}


const tree = createTreeFromArray(arr, 'uid', 'parentUID');

Comments

[Siple]

Огромнейшее спасибо, выручил!

[crecker05ru]

@@0xD34F
Здравствуйте, в отрезке
tree[n[parentKey]].children ??= {}
что означает ??={}
?? оператор знаю ,что он возвращает значение правого операнда если левое undefined или null, а там получается еще и присваивание или что оно делает ?

[0xD34F]

https://developer.mozilla.org/en-US/docs/Web/JavaS...

[crecker05ru]

0xD34F, благодарю )

Answer 2

[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 удалить.