从递归函数构建嵌套对象数组
从递归函数构建嵌套对象数组
提问于 2022-02-16 15:50:54
我将如何利用我的getChildren()函数来创建一个更大的函数，它使用我的两个主数组objs和objRefs，并输出一个显示它们的父/子关系的objs数组。
下面是两个主要的数据数组
const objs = [
{ name: "Kevin", age: 5, id: 1 },
{ name: "Matt", age: 53, id: 5 },
{ name: "Marry", age: 30, id: 2 },
{ name: "Leslie", age: 21, id: 3 },
{ name: "Sarah", age: 46, id: 4 },
{ name: "Heather", age: 37, id: 6 },
{ name: "Cory", age: 19, id: 7 },
]
const objRefs = [
{ parent_id: 5, obj_id: 7 }, // cory child of matt
{ parent_id: null, obj_id: 6 }, // matt root
{ parent_id: null, obj_id: 4 }, // sarah root
{ parent_id: null, obj_id: 5 }, // heather root
{ parent_id: 5, obj_id: 3 }, // leslie child of matt
{ parent_id: 4, obj_id: 2 }, // mary child of sarah
{ parent_id: 3, obj_id: 1 }, // kevin child of leslie
]我的目标是运行一个名为getFamilyTree()的函数，它将返回给我这个.
const tree = [
{
id: 5,
name: "Matt",
age: 53,
children:[
{
id: 3,
name: "Leslie",
age: 21,
children:[
{
id: 1,
name: "Kevin",
age: 5,
children:[ ]
}
]
},
{
id: 7,
name: "Cory",
age: 19,
children:[ ]
}
]
},
{
id: 6,
name: "Heather",
age: 37,
children:[ ]
},
{
id: 4,
name: "Sarah",
age: 46,
children:[
{
id: 2,
name: "Marry",
age: 30,
children:[ ]
}
]
}
]我有一个函数，它返回给定父节点id的所有子节点，但我不确定如何构造一个函数来像我的示例那样返回整个树。
function getChildren(parent_id) {
let children = []
for (var i = 0; i < objRefs.length; i++) {
const ref = objRefs[i]
if (ref.parent_id === parent_id) {
const obj = objs.find(obj => {
return obj.id === ref.obj_id
})
children.push(obj)
}
}
return children
}
function getFamilyTree() {
let result = []
... // build recursive family tree
return result
}回答 3
Stack Overflow用户
回答已采纳
发布于 2022-02-16 16:12:13
您不需要使用递归函数来构造它。
要获得合理的时间复杂度，请将所有的objs存储到由id键确定的地图或其他东西(如果id是顺序的，甚至数组也能工作)。然后，只需在objRefs上迭代并适当地构造关系：
const objs = [
{ name: "Kevin", age: 5, id: 1 },
{ name: "Matt", age: 53, id: 5 },
{ name: "Marry", age: 30, id: 2 },
{ name: "Leslie", age: 21, id: 3 },
{ name: "Sarah", age: 46, id: 4 },
{ name: "Heather", age: 37, id: 6 },
{ name: "Cory", age: 19, id: 7
},
]
const objRefs = [
{ parent_id: 5, obj_id: 7 }, // cory child of matt
{ parent_id: null, obj_id: 6 }, // matt root
{ parent_id: null, obj_id: 4 }, // sarah root
{ parent_id: null, obj_id: 5 }, // heather root
{ parent_id: 5, obj_id: 3 }, // leslie child of matt
{ parent_id: 4, obj_id: 2 }, // mary child of sarah
{ parent_id: 3, obj_id: 1 }, // kevin child of leslie
]
function getFamilyTree(objs, objRefs){
const tree = []
const map = new Map(
objs.map(e => [e.id, { ...e, children: [] }])
)
for(const {parent_id, obj_id} of objRefs){
if(parent_id === null){
tree.push(map.get(obj_id))
}else{
map.get(parent_id).children.push(map.get(obj_id))
}
}
return tree
}
const tree = getFamilyTree(objs, objRefs)
console.log(tree)
Stack Overflow用户
发布于 2022-02-16 16:06:19
我认为您甚至不需要getChildren函数来实际构建树。相反地使用Maps可能是有用的：
const objs = [
{ name: "Kevin", age: 5, id: 1 },
{ name: "Matt", age: 53, id: 5 },
{ name: "Marry", age: 30, id: 2 },
{ name: "Leslie", age: 21, id: 3 },
{ name: "Sarah", age: 46, id: 4 },
{ name: "Heather", age: 37, id: 6 },
{ name: "Cory", age: 19, id: 7 },
]
const objRefs = [
{ parent_id: 5, obj_id: 7 }, // cory child of matt
{ parent_id: null, obj_id: 6 }, // matt root
{ parent_id: null, obj_id: 4 }, // sarah root
{ parent_id: null, obj_id: 5 }, // heather root
{ parent_id: 5, obj_id: 3 }, // leslie child of matt
{ parent_id: 4, obj_id: 2 }, // mary child of sarah
{ parent_id: 3, obj_id: 1 }, // kevin child of leslie
]
function getFamillyTree(){
const nodes = new Map()
// Preparing the data nodes
objs.forEach(elt => nodes.set(elt.id, {...elt, children: [], root: false}))
// Linking the nodes to make the parent <-> children relations
objRefs.filter(rel => !!rel.parent_id).forEach(rel => {
const parent = nodes.get(rel.parent_id)
parent.children.push(nodes.get(rel.obj_id))
})
// Marking the roots
objRefs.filter(rel => rel.parent_id === null).forEach(rel => {
const obj = nodes.get(rel.obj_id)
obj.root = true
})
return Array.from(nodes.values()).filter(obj => obj.root)
}
document.write(JSON.stringify(getFamillyTree(), null, 4))
编辑:这个答案可以稍微偏离，因为正如Nina在关于这个问题的评论中所指出的，OP似乎要求一个明确的递归解决方案，将其留在这里供参考。
Stack Overflow用户
发布于 2022-02-16 16:13:33
您可以使用一些对象作为对人员及其关系的引用，并将节点与其子节点映射。
const
getChildren = parent => (references[parent] || []).map(id => ({
...nodes[id],
children: getChildren(id)
})),
people = [{ name: "Kevin", age: 5, id: 1 }, { name: "Matt", age: 53, id: 5 }, { name: "Marry", age: 30, id: 2 }, { name: "Leslie", age: 21, id: 3 }, { name: "Sarah", age: 46, id: 4 }, { name: "Heather", age: 37, id: 6 }, { name: "Cory", age: 19, id: 7 }],
children = [{ parent_id: 5, obj_id: 7 }, { parent_id: null, obj_id: 6 }, { parent_id: null, obj_id: 4 }, { parent_id: null, obj_id: 5 }, { parent_id: 5, obj_id: 3 }, { parent_id: 4, obj_id: 2 }, { parent_id: 3, obj_id: 1 }],
nodes = Object.fromEntries(people.map(o => [o.id, o])),
references = children.reduce((r, { parent_id, obj_id }) => ((r[parent_id] ??= []).push(obj_id), r), {}),
tree = getChildren(null);
console.log(tree);.as-console-wrapper { max-height: 100% !important; top: 0; }
单循环children的一种方法。
const
getTree = (people, children, root) => {
const
nodes = Object.fromEntries(people.map(o => [o.id, o])),
t = {};
children.forEach(({ parent_id: p, obj_id: id }) =>
((t[p] ??= {}).children ??= []).push(Object.assign(t[id] ??= {}, nodes[id]))
);
return t[root].children;
},
people = [{ name: "Kevin", age: 5, id: 1 }, { name: "Matt", age: 53, id: 5 }, { name: "Marry", age: 30, id: 2 }, { name: "Leslie", age: 21, id: 3 }, { name: "Sarah", age: 46, id: 4 }, { name: "Heather", age: 37, id: 6 }, { name: "Cory", age: 19, id: 7 }],
children = [{ parent_id: 5, obj_id: 7 }, { parent_id: null, obj_id: 6 }, { parent_id: null, obj_id: 4 }, { parent_id: null, obj_id: 5 }, { parent_id: 5, obj_id: 3 }, { parent_id: 4, obj_id: 2 }, { parent_id: 3, obj_id: 1 }],
tree = getTree(people, children, null);
console.log(tree);.as-console-wrapper { max-height: 100% !important; top: 0; }
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71145009
复制相关文章
相似问题
腾讯云开发者
