将扁平数组转换为嵌套树形结构：高效算法详解

本文介绍一种高效算法，用于将扁平章节数组转换为嵌套的树形结构。假设章节数组包含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函数中的父子关系判断逻辑。