typescript - 算法 - 节点 - 树 - 打字稿
问题描述
我有一个未排序的原始数据中的 json,如下所示:
[
{
"level": 1,
"id": 34,
"name": "example-name",
"father_id": 10
},
{
"level": 3,
"id": 48521,
"name": "example-name",
"father_id": 684
},
{
"level": 5,
"id": 12138,
"name": "example-name",
"father_id": 213
},
{
"level": 4,
"id": 5679,
"name": "example-name",
"father_id": 12138
},
{
"level": 5,
"id": 4789,
"name": "example-name",
"father_id": 10769
},
{
"level": 3,
"id": 998797988,
"name": "example-name",
"father_id": 5679
},
{
"level": 3,
"id": 987987777,
"name": "example-name",
"father_id": 5679
},
{
"level": 4,
"id": 4417,
"name": "example-name",
"father_id": 4789
},
{
"level": 3,
"id": 12138,
"name": "example-name",
"father_id": 4417
},
{
"level": 4,
"id": 5678,
"name": "example-name",
"father_id": 12138
},
{
"level": 3,
"id": 998797987,
"name": "example-name",
"father_id": 5678
},
{
"level": 5,
"id": 326,
"name": "example-name",
"father_id": 20
},
{
"level": 4,
"id": 684,
"name": "example-name",
"father_id": 326
},
{
"level": 2,
"id": 54444,
"name": "example-name",
"father_id": 26580
}
]
我的最终目标是能够得到这个结果:
[
{
"parent": {
"level": 5,
"id": 12138,
"name": "example-name",
"father_id": 213
},
"children": [
{
"level": 3,
"id": 998797987,
"name": "example-name",
"father_id": 5678
},
{
"level": 3,
"id": 998797988,
"name": "example-name",
"father_id": 5679
},
{
"level": 3,
"id": 987987777,
"name": "example-name",
"father_id": 5679
}
]
},
{
"parent": {
"level": 5,
"id": 326,
"name": "example-name",
"father_id": 20
},
"children": [
{
"level": 3,
"id": 48521,
"name": "example-name",
"father_id": 684
}
]
},
{
"parent" : {
"level": 5,
"id": 4789,
"name": "example-name",
"father_id": 10769
},
"children": [
{
"level": 3,
"id": 12138,
"name": "example-name",
"father_id": 4417
}
]
}
]
为了让您了解它是如何工作的,我创建了这个中间 json :
[
{
"parent": {
"level": 5,
"id": 12138,
"name": "example-name",
"father_id": 213
},
"children": [
{
"parent": {
"level": 4,
"id": 5678,
"name": "example-name",
"father_id": 12138
},
"children": [
{
"level": 3,
"id": 998797987,
"name": "example-name",
"father_id": 5678
}
]
},
{
"parent": {
"level": 4,
"id": 5679,
"name": "example-name",
"father_id": 12138
},
"children": [
{
"level": 3,
"id": 998797988,
"name": "example-name",
"father_id": 5679
},
{
"level": 3,
"id": 987987777,
"name": "example-name",
"father_id": 5679
}
]
}
]
},
{
"parent": {
"level": 5,
"id": 326,
"name": "example-name",
"father_id": 20
},
"children": [
{
"parent": {
"level": 4,
"id": 684,
"name": "example-name",
"father_id": 326
},
"children": [{
"level": 3,
"id": 48521,
"name": "example-name",
"father_id": 684
}]
}
]
},
{
"parent" : {
"level": 5,
"id": 4789,
"name": "example-name",
"father_id": 10769
},
"children": [
{
"parent": {
"level": 4,
"id": 4417,
"name": "example-name",
"father_id": 4789
},
"children": [
{
"level": 3,
"id": 12138,
"name": "example-name",
"father_id": 4417
}
]
}
]
}
]
在前面的 json 中,每个father_id
都链接到id
他的父级。
我在我的 json 中有不同的level
(6 比 1)。我对level 5
和之间的关系很感兴趣level 3
。
这是我在打字稿中所做的:
const families: { parent: Treeview; children: Treeview[] }[] = []
arrayTreeViews.forEach(node => {
// keep level between 3 to 5
if ( node.level < 3 || node.level > 5 ) return
// get root parent
if ( node.level === 4 ) families.push({parent: node, children: []})
// issue with the following line is :
// as the array is not sorted the node itself might not has any parent yet...
const parentIndex = families.findIndex(el => el.parent.id === node.fatherId)
if ( parentIndex !== -1 ) {
families[parentIndex].children.push(node)
return
}
})
如何在 typescript 中以最有效的方式实现预期的 json 结果?
我考虑过首先在属性级别对数组进行排序,但我不知道如何直接获得level 5
与level 3
谢谢你的帮助 !
编辑 :
消息已删除,因为它是错误的解决方案:/
编辑 2: 找到解决方案:和之前的问题一样吗?这是最好的方法/最有效的方法吗?感谢您的帮助/建议
const rootLevel: { parent: Treeview; children: Treeview[] }[] = []
const subLevel: Treeview[] = []
const lowerLevel: Treeview[] = []
arrayTreeViews.forEach(node => {
if ( node.level === 4 ) rootLevel.push({parent: node, children: []})
if ( node.level === 3 ) subLevel.push(node)
if ( node.level === 2 ) lowerLevel.push(node)
})
subLevel.forEach(node => {
const parentIndex = rootLevel.findIndex(el => el.parent.id === node.fatherId)
const familyTreeView = lowerLevel.filter(el => el.fatherId === node.id)
if ( familyTreeView && parentIndex !== -1) {
rootLevel[parentIndex].children.push(...familyTreeView)
}
})
res.json(rootLevel)
解决方案
编辑:由于问题已经改变,我不得不写一个新的答案
const findChildren = (tree: Treeview[], node: Treeview) =>
tree.filter(
(treeNode) =>
treeNode.level === node.level - 1 && treeNode.father_id === node.id
);
const findGrandchildren = (tree: Treeview[], node: Treeview) =>
findChildren(tree, node).flatMap((child) => findChildren(tree, child));
const families = arrayTreeViews
.filter((view) => view.level === 5)
.map((view) => ({
parent: view,
children: findGrandchildren(arrayTreeViews, view),
}));
原答案:
我会在这里使用递归函数:
const getRelation = (
tree: Treeview[],
lowerLevelBound: number,
level: number,
fatherId?: number
) => {
// Find nodes with the given level
const currentLevelNodes = tree.filter(
(node) =>
node.level === level &&
// If fatherId is not null, filter nodes with wanted father_id
(fatherId == null ? true : node.father_id === fatherId)
);
// We hit the lower level bound -- exit algorithm
if (level === lowerLevelBound) return currentLevelNodes;
return currentLevelNodes.map((node) => ({
parent: node,
children: getRelation(tree, lowerLevelBound, level - 1, node.id),
}));
};
const lowerLevelBound = 3;
const upperLevelBound = 5;
const families = getRelation(arrayTreeViews, lowerLevelBound, upperLevelBound);
它的工作原理是仅过滤级别 5 的节点,然后递归地将它们映射到父子关系
推荐阅读
- java - Java FormData 请求为空
- java - 如何更改特定 maven 模块的 junit 相对资源路径?
- c++ - GCC 编译器对类型转换做了什么?为什么mac和linux上的输出不一样?
- python - 查找图像的最小值和最大值
- java - 使用 ScheduledExecutorService 查看不会更新
- bash - 双引号不能帮助我传递带空格的字符串参数
- javascript - 当 popup.html 打开时,不调用 Firebase messings().onMessage()
- python - 如何在导入 keras 时修复“无法导入名称 np_utils”错误
- java - Android项目连接WampServer的IP地址是什么?
- angular - 为什么 ASP.NET Core 不接受以纯文本/文本形式发送 PUT 请求?