
将扁平数组转换为嵌套树形结构:高效算法详解
本文介绍一种高效算法,用于将扁平章节数组转换为嵌套的树形结构。假设章节数组包含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号