本文小编为大家详细介绍“javascript实现树结构转换的方法有哪些”,内容详细,步骤清晰,细节处理妥当,希望这篇“JavaScript实现树结构转换的方法有哪些”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。在
本文小编为大家详细介绍“javascript实现树结构转换的方法有哪些”,内容详细,步骤清晰,细节处理妥当,希望这篇“JavaScript实现树结构转换的方法有哪些”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。
在 JavaScript 编程中,将数组转换为树结构是一个常见的需求。本篇博客将介绍五种常用的方法来实现数组转树结构,并讨论每种方法的时间复杂度、空间复杂度和最优解。
假设有一个由对象组成的数组,每个对象包含 id
和 parentId
两个属性。其中 id
表示节点的唯一标识,parentId
表示该节点的父节点的 id
。
const nodes = [ { id: 1, parentId: null }, { id: 2, parentId: 1 }, { id: 3, parentId: 1 }, { id: 4, parentId: 2 }, { id: 5, parentId: 3 }, { id: 6, parentId: 3 }, { id: 7, parentId: 4 }, { id: 8, parentId: 4 },];
以上面的数组为例,我们将介绍以下五种方法来将其转换为树结构。
function arrayToTreeRec(nodes, parentId = null) { return nodes .filter((node) => node.parentId === parentId) .map((node) => ({ ...node, children: arrayToTreeRec(nodes, node.id) }));}const tree = arrayToTreeRec(nodes, null);
时间复杂度:O(n^2),其中 n 是节点的数量。 空间复杂度:O(n^2)。 优缺点:不适合大规模数据。
function arrayToTreeLoop(nodes) { const map = {}; const tree = []; for (const node of nodes) { map[node.id] = { ...node, children: [] }; } for (const node of Object.values(map)) { if (node.parentId === null) { tree.push(node); } else { map[node.parentId].children.push(node); } } return tree;}const tree = arrayToTreeLoop(nodes);
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 优缺点:适合大规模数据。
function arrayToTreeReduce(nodes) { const map = {}; const tree = nodes.reduce((acc, node) => { map[node.id] = { ...node, children: [] }; if (node.parentId === null) { acc.push(map[node.id]); } else { map[node.parentId].children.push(map[node.id]); } return acc; }, []); return tree;}const tree = arrayToTreeReduce(nodes);
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 优缺点:代码简洁,适合中小规模数据。
function arrayToTreeMap(nodes) { const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }])); const tree = []; for (const node of map.values()) { if (node.parentId === null) { tree.push(node); } else { map.get(node.parentId).children.push(node); } } return tree;}const tree = arrayToTreeMap(nodes);
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 优缺点:适合大规模数据,而且由于使用了 Map
,相比于方法二和方法三,能够更方便地进行节点的查找和删除。
function arrayToTreeDFS(nodes) { const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }])); const tree = []; for (const node of map.values()) { if (node.parentId === null) { dfs(node, tree); } } function dfs(node, parent) { if (parent) { parent.children.push(node); } for (const child of node.children) { dfs(map.get(child.id), node); } } return tree;}const tree = arrayToTreeDFS(nodes);
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 优缺点:相比于方法二、方法三和方法四,可以更方便地进行深度优先搜索。
读到这里,这篇“JavaScript实现树结构转换的方法有哪些”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注编程网精选频道。
--结束END--
本文标题: JavaScript实现树结构转换的方法有哪些
本文链接: https://www.lsjlt.com/news/351692.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0