在树数据结构中聚合包含对象数组的属性

Question

我有一个像下面的树结构(没有深度限制，一般不超过6个子级别(。每个节点都有一个workItems属性，即workItem对象的数组。

我想聚合每个节点上的workItems，以便节点包含自己的工作项及其后代的所有工作项。

下面是结构的示例，节点 id11将具有 workItems：

[{ 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; }

这个答案唯一不寻常的部分是使用参数_和__. 这些用于模仿许多语言的占位符功能。 它们只是参数，旨在指出此处提供的参数不会被使用。 在这种情况下，这是因为我们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,
}
}