将扁平数组转换为嵌套树形结构:高效算法详解
本文介绍一种高效算法,用于将扁平章节数组转换为嵌套的树形结构。假设章节数组包含level、content和url三个属性,分别表示章节层级、内容和URL。目标是根据level字段,将扁平数组转换为层级结构,其中level值较小的章节作为父节点,level值较大的章节作为子节点。
初始数据:
const chapters = [{ level: '1', content: '案例概况010000-170900', url: '案例概况010000-170900.html' },{ level: '2', content: '案例概况010100-170901', url: '案例概况010100-170901.html' },{ level: '2', content: '案例概况010200-170902', url: '案例概况010200-170902.html' },{ level: '3', content: '案例概况010201-170903', url: '案例概况010201-170903.html' },{ level: '1', content: '案例概况020000-170904', url: '案例概况020000-170904.html' },{ level: '1', content: '案例概况030000-170905', url: '案例概况030000-170905.html' },{ level: '2', content: '案例概况030100-170906', url: '案例概况030100-170906.html' }];
目标树形结构:
const tree = [{ level: '1', content: '案例概况010000-170900', url: '案例概况010000-170900.html', childs: [{ level: '2', content: '案例概况010100-170901', url: '案例概况010100-170901.html', childs: [] },{ level: '2', content: '案例概况010200-170902', url: '案例概况010200-170902.html', childs: [{ level: '3', content: '案例概况010201-170903', url: '案例概况010201-170903.html', childs: [] }] }] },{ level: '1', content: '案例概况020000-170904', url: '案例概况020000-170904.html', childs: [] },{ level: '1', content: '案例概况030000-170905', url: '案例概况030000-170905.html', childs: [{ level: '2', content: '案例概况030100-170906', url: '案例概况030100-170906.html', childs: [] }] }];
高效算法实现:
该算法使用递归的方式,逐层构建树形结构。它首先将扁平数组按照level排序,然后递归地处理每个章节,将其添加到合适的父节点下。 为了提高效率,它避免了多次遍历数组,而是利用Map对象快速查找父节点。
function convertToTree(chapters) { // 按照 level 排序 chapters.sort((a, b) => parseInt(a.level) - parseInt(b.level)); const tree = []; const map = new Map(); // 使用 Map 提高查找效率 chapters.forEach(chapter => { const level = parseInt(chapter.level); if (level === 1) { tree.push({ ...chapter, childs: [] }); map.set(chapter.content, tree[tree.length - 1]); } else { let parent = findParent(map, chapter); if (parent) { parent.childs.push({ ...chapter, childs: [] }); map.set(chapter.content, parent.childs[parent.childs.length - 1]); } } }); return tree; } function findParent(map, chapter) { let level = parseInt(chapter.level); let parentContent = chapter.content.substring(0, chapter.content.length - 2); // 假设父节点的content是子节点content的前缀,需要根据实际情况调整 while (level > 1) { if (map.has(parentContent)) { return map.get(parentContent); } level--; parentContent = parentContent.substring(0, parentContent.length - 2); } return null; } const tree = convertToTree(chapters); console.log(JSON.stringify(tree, null, 2));
这段代码假设父节点的content属性是子节点content属性的前缀(例如,'案例概况010200-170902' 的父节点的content可能是 '案例概况010200-170901' 或 '案例概况010000-170900'),这部分逻辑需要根据实际数据结构进行调整。 如果父子关系并非通过content的前缀来确定,则需要修改findParent函数以匹配实际的父子关系确定方式。
这个改进后的算法在处理大型数组时效率更高,因为它避免了重复的数组遍历,并利用了Map对象的快速查找能力。 记住根据你的实际数据结构调整findParent函数中的父子关系判断逻辑。
以上就是如何将扁平的章节数组转换成嵌套的树形结构?的详细内容,更多请关注php中文网其它相关文章!
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号