提问人：JimminyCricket 提问时间：11/21/2022 最后编辑：JimminyCricket 更新时间：11/21/2022 访问量：45
具有多个顶级父项和索引的反向嵌套树
Reverse Nested Tree with Multiple Top Level Parents & Index
问：
我有以下数据结构
[
{
id: 1,
name: 'Top Level Topic 1',
parentTopic: undefined
},
{
id: 2,
name: 'Some topic internally',
parentTopic: 1
},
{
id: 3,
name: 'Another topic',
parentTopic: 2
},
{ id: 4, name: 'Just another topic', parentTopic: 2 },
{
id: 5,
name: 'Another topic',
parentTopic: 1
},
{
id: 6,
name: 'Another topic',
parentTopic: 5
},
{
id: 7,
name: 'Another topic',
parentTopic: 5
},
{ id: 8, name: 'Another topic', parentTopic: 1 },
{
id: 9,
name: 'Another topic',
parentTopic: 8
},
{
id: 10,
name: 'Another topic',
parentTopic: 9
},
{
id: 11,
name: 'Another topic',
parentTopic: 10
},
{
id: 12,
name: 'Another Top Level Topic',
parentTopic: undefined
},
{ id: 13, name: 'Another Important Topic', parentTopic: 12 }]我正在尝试以下方式转换和构建它
[
{
id: 1,
name: 'Top Level Topic 1',
parentTopic: undefined,
index: 1,
children: [
{
id: 2,
name: 'Some topic internally',
parentTopic: 1,
index: 1.1,
children: [
{
id: 3,
name: 'Another topic',
parentTopic: 2,
index: 1.1.1,
children: []
},
{
id: 4,
name: 'Just another topic',
parentTopic: 2,
index: 1.1.2,
children: []
},
]
},
{
id: 5,
name: 'Another topic',
parentTopic: 1,
index: 1.2,
children: [
{
id: 6,
name: 'Another topic',
parentTopic: 5,
index: 1.2.1,
children: []
},
{
id: 7,
name: 'Another topic',
parentTopic: 5,
index: 1.2.2,
children: []
},
]
},
{
id: 8,
name: 'Another topic',
parentTopic: 1,
index: 1.3,
children: [
{
id: 9,
name: 'Another topic',
parentTopic: 8,
index: 1.3.1,
children: [
{
id: 10,
name: 'Another topic',
parentTopic: 9,
index: 1.3.1.1,
children: []
},
]
},
]
},
]
},
{
id: 12,
name: 'Another Top Level Topic',
parentTopic: undefined,
index: 2
children: [
{
id: 13,
name: 'Another Important Topic',
parentTopic: 12,
index: 2.1,
children: []
},
]
},
]我的挑战是我不确定如何递归地执行此操作。同样在输出中，您会注意到一个索引，它可以在迭代时生成，或者它可能只是来自数据库，这意味着我的原始数据结构已经拥有它。
如果有人能帮助我解决这个:)，我将不胜感激
这是我的代码，它可以工作，但在顶层，它是一个字典，而不是字典列表
const invertHierarchy = (arr) => {
const map = {};
let root;
for (const ele of arr) {
map[ele.id] = ele;
ele.topics = [];
}
for (const ele of arr) {
if (map[ele.parentTopic] != null) map[ele.parentTopic].topics.push(ele);
else root = ele;
}
return root;
};
答：
2赞
Andrew Parks
11/21/2022
#1
const data = [{"id":1,"name":"Top Level Topic 1"},{"id":2,"name":"Some topic internally","parentTopic":1},{"id":3,"name":"Another topic","parentTopic":2},{"id":4,"name":"Just another topic","parentTopic":2},{"id":5,"name":"Another topic","parentTopic":1},{"id":6,"name":"Another topic","parentTopic":5},{"id":7,"name":"Another topic","parentTopic":5},{"id":8,"name":"Another topic","parentTopic":1},{"id":9,"name":"Another topic","parentTopic":8},{"id":10,"name":"Another topic","parentTopic":9},{"id":11,"name":"Another topic","parentTopic":10},{"id":12,"name":"Another Top Level Topic"},{"id":13,"name":"Another Important Topic","parentTopic":12}];
const getPrefix = (prefix, i) => prefix ? `${prefix}.${i+1}` : `${i+1}`
const f = (arr, parentTopic, prefix) =>
arr.filter(e=>e.parentTopic===parentTopic).map((e,i)=>({
...e,
index: getPrefix(prefix,i),
children: f(arr, e.id, getPrefix(prefix,i))
}))
console.log(f(data))评论
0赞
Scott Sauyet
11/21/2022
我一直在使用类似的技术，但我们应该注意，这是因为对每个节点的调用，而执行初始传递以创建用于树构建的索引的技术是 。对于较小尺寸的输入，这可能根本无关紧要，但在较大尺寸下可能会有很大的时间差。O(n^2)filterO (n)
0赞
Nina Scholz
11/21/2022
#2
您可以采用另一种方法，将所有节点及其父节点存储在一个对象中，并仅采用没有父节点的数组作为结果。
通过使用单个循环，它还可以动态构建索引。
const
data = [{ id: 1, name: 'Top Level Topic 1', parentTopic: undefined }, { id: 2, name: 'Some topic internally', parentTopic: 1 }, { id: 3, name: 'Another topic', parentTopic: 2 }, { id: 4, name: 'Just another topic', parentTopic: 2 }, { id: 5, name: 'Another topic', parentTopic: 1 }, { id: 6, name: 'Another topic', parentTopic: 5 }, { id: 7, name: 'Another topic', parentTopic: 5 }, { id: 8, name: 'Another topic', parentTopic: 1 }, { id: 9, name: 'Another topic', parentTopic: 8 }, { id: 10, name: 'Another topic', parentTopic: 9 }, { id: 11, name: 'Another topic', parentTopic: 10 }, { id: 12, name: 'Another Top Level Topic', parentTopic: undefined }, { id: 13, name: 'Another Important Topic', parentTopic: 12 }],
tree = function(data, root) {
const t = {};
data.forEach(o => {
Object.assign(t[o.id] ??= {}, { ...o });
((t[o.parentTopic] ??= {}).children ??= []).push(t[o.id]);
const index = t[o.parentTopic].index || '';
t[o.id].index = index + (index && '.') + t[o.parentTopic].children.length;
});
return t[root].children;
}(data, undefined);
console.log(tree);.as-console-wrapper { max-height: 100% !important; top: 0; }
评论