Агрегировать свойство, содержащее массив объектов, в древовидной структуре данных

Question

У меня есть древовидная структура, как показано ниже (нет ограничения по глубине, как правило, не более 6 подуровней). Каждый узел имеет свойство workItems, которое представляет собой массив объектов workItem.

Я бы хотел объединить workItems на каждом узле, чтобы узел содержал свои собственные рабочие элементы и все свои workItems потомка.

Пример структуры ниже, идентификатор узла 11 будет иметь рабочие элементы:

    [{ id: 'wi2' },
     { id: 'wi3' },
     { id: 'wi4' }, 
     { id: 'wi5' }] // aggregated from node `111`

И узел 1 будет иметь абсолютно все рабочие элементы дерева.

javascript

const traverse = (tree) => {
    const stack = [ tree ]

    while (stack.length) {
        const curr = stack.pop()

        // do something here, I guess

        stack.push(...curr.children)
    }
}

Древовидная структура

    {
        id: '1',
        title: '1',
        workItems: [
            { id: 'wi1' }
        ],
        children: [
            {
                id: '11',
                title: '11',
                workItems: [
                    { id: 'wi2' },
                    { id: 'wi3' },
                    { id: 'wi4' }           
                ],
                children: [
                    {
                        id: '111',
                        title: '111',
                        workItems: [
                            { id: 'wi5' },
                        ],
                        children: []
                    }
                ]
            },
            {
                id: '12',
                title: '12',
                workItems: [
                    { id: 'wi6' }                           
                ],
                children: [
                    {
                        id: '121',
                        title: '121',
                        workItems: [
                            { id: 'wi7' },
                            { id: 'wi8' }
                        ],
                        children: []
                    }
                ]
            }
        ]
    }

Answer 1

Вы можете выполнить поиск в глубину и передать родительский массив workItmes, чтобы просмотреть вложенные элементы.

const
    getWorkItems = ({ workItems, children = [] }) =>
        (workItems.push(...children.flatMap(getWorkItems)), workItems);

var tree = { id: '1', title: '1', workItems: [{ id: 'wi1' }], children: [{ id: '11', title: '11', workItems: [{ id: 'wi2' }, { id: 'wi3' }, { id: 'wi4' }], children: [{ id: '111', title: '111', workItems: [{ id: 'wi5' }], children: [] }] }, { id: '12', title: '12', workItems: [{ id: 'wi6' }], children: [{ id: '121', title: '121', workItems: [{ id: 'wi7' }, { id: 'wi8' }], children: [] }] }] };
  
getWorkItems(tree);

console.log(tree);

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

Answer 2

Вот версия, которая создает новое дерево, а не изменяет текущее на месте. (Я большой поклонник неизменных данных.) Обратите внимание, что workItems по-прежнему доступны по ссылке, как внутри одного дерева, так и между исходным и производным.

const addAllDecendents = (
  {workItems, children = [], ...rest}, _, __,
  kids = children .map (addAllDecendents)
) => ({
  ... rest,
  workItems: [... workItems, ... kids .flatMap (child => child .workItems)],
  children: kids,
})

const tree = {id: "1", title: "1", workItems: [{id: "wi1"}], children: [{id: "11", title: "11", workItems: [{id: "wi2"}, {id: "wi3"}, {id: "wi4"}], children: [{id: "111", title: "111", workItems: [{id: "wi5"}], children: []}]}, {id: "12", title: "12", workItems: [{id: "wi6"}], children: [{id: "121", title: "121", workItems: [{id: "wi7"}, {id: "wi8"}], children: []}]}]};

console .log ('New tree:', addAllDecendents (tree))
console .log ('Original tree:', tree)

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

Единственная необычная часть этого ответа - использование параметров _ и __. Они используются для имитации c функции заполнителя многих языков. Это просто параметры, предназначенные для указания на то, что приведенный здесь аргумент не будет использоваться. В данном случае это потому, что мы map дочерние элементы этой функции, но Array.prototype.map предоставляет два дополнительных аргумента в дополнение к значению массива: индекс и исходный массив.

Мы могли бы обработать это несколькими другие способы.

Мы могли бы передать функцию в map, которая непосредственно рекурсивирует и управляет самими аргументами:

const addAllDecendents = (
  {workItems, children = [], ...rest},
  kids = children .map (c => addAllDecendents (c))
) => // ...

Но есть проблема с этим: тогда мы не можем использовать addAllDescendents как обратный вызов к другому map вызову в другом месте. То есть что-то вроде const enhancedTrees = trees.map(addAllDescendents). Это вполне может не быть проблемой, но это ограничение.

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

const addAllDecendents = ({workItems, children = [], ...rest}) => {
  const kids = children .map (addAllDecendents)
  return {
    ... rest,
    workItems: [... workItems, ... kids .flatMap (child => child .workItems)],
    children: kids,
  }
}

Лично мне первая версия лучше, чем эта, потому что я предпочитаю работать с выражениями, а не с упорядоченными выражениями (присваивание kids, за которым следует оператор return. Но я почти уверен, что это представление с меньшинством, и любой из них работает нормально.

Обновление

Вот еще одна версия, которая пропускает все еще -не-универсальный- flatMap с map-потом- reduce эквивалентом:

const addAllDecendents = ({workItems, children = [], ...rest}) => {
  const kids = children .map (addAllDecendents)
  return {
    ... rest,
    workItems: [
      ... workItems, 
      ... kids .map (child => child .workItems).reduce((a, b) => a.concat(b), [])
      ],
    children: kids,
  }
}