如何高效地将扁平数组对象转换为嵌套树形结构？

高效实现扁平数组对象到嵌套树形结构的转换

在软件开发中，经常需要处理数据结构的转换，例如将扁平数组对象根据特定字段（比如层级 level）转换为嵌套树形结构。本文将详细讲解如何将一个线性数组对象，基于 level 字段，转化为嵌套树状结构。

假设我们有一个扁平的数组对象 chapters：

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' },
];

我们的目标是将其转换为如下的嵌套结构：

WowTo

用AI建立视频知识库

下载

const treeChapters = [
  // ... (嵌套结构，与原文相同)
];

由于输入数组已按 level 排序，我们可以使用迭代方法，避免递归带来的性能问题。以下代码实现了这个转换：

function createTreeByList(arr) {
  const tree = [];
  const stack = [];

  arr.forEach(item => {
    while (stack.length > 0 && +stack[stack.length - 1].level >= +item.level) {
      stack.pop();
    }

    if (stack.length === 0) {
      item.childs = [];
      tree.push(item);
      stack.push(item);
    } else {
      const parent = stack[stack.length - 1];
      item.childs = [];
      parent.childs.push(item);
      stack.push(item);
    }
  });

  return tree;
}

const treeChapters = createTreeByList(chapters);
console.log(JSON.stringify(treeChapters, null, 2));

这段代码利用栈 stack 来跟踪当前处理的父节点，通过比较 level 值来确定父子关系，从而高效构建嵌套树形结构。 避免了递归，提高了代码效率。