JS数组树形结构转换全解析

本文深入探讨了使用JavaScript将扁平数组转换为树形结构的实用方法。核心思想在于利用id和parentId建立清晰的父子关系，并通过map数据结构实现快速查找，优化性能。针对可能出现的循环引用问题，文章提出了使用visited集合进行检测的有效策略，避免程序陷入无限循环。此外，还详细介绍了如何满足排序需求，通过递归调用sortChildren函数，可按照指定规则对树形结构中的每个节点的children属性进行排序，从而构建出符合特定业务需求的完整树结构。掌握这些技巧，能更高效地处理复杂数据，提升前端开发效率。

转换核心是通过id和parentId建立父子关系，使用map实现快速查找；2. 循环引用可通过visited集合检测，发现重复访问节点时跳过以避免无限循环；3. 排序需求可在构建树后递归调用sortChildren函数，按指定规则对每个节点的children进行排序，最终返回完整树结构。

将一个扁平的数组结构转换成树形结构，核心在于找到每个节点的父节点，并将它们正确地关联起来。这通常涉及遍历数组，并根据特定的父子关系标识（例如id和parentId）来构建树。

解决方案：

首先，我们需要一个函数来完成这个转换。这个函数接收一个数组作为输入，并返回一个树形结构的数组。

function arrayToTree(arr) {
  const tree = [];
  const map = {};

  // 首先，将数组中的每个元素放入一个 map 中，方便后续查找
  arr.forEach(item => {
    map[item.id] = item;
    item.children = []; // 初始化 children 属性，即使当前节点没有子节点
  });

  arr.forEach(item => {
    const parent = map[item.parentId];
    if (parent) {
      parent.children.push(item);
    } else {
      tree.push(item); // 如果没有父节点，说明是根节点
    }
  });

  return tree;
}

这段代码首先创建一个 map 对象，用于存储数组中的每个元素，键为元素的 id。这样做的好处是可以快速地通过 id 找到对应的元素，避免了重复遍历数组。然后，再次遍历数组，找到每个元素的父节点，并将元素添加到父节点的 children 数组中。如果元素没有父节点，说明它是根节点，直接添加到 tree 数组中。

如何处理循环引用？

循环引用是指两个或多个节点互相引用，导致无限循环。在树形结构中，这通常是不允许的。检测和处理循环引用是复杂树形结构转换中一个需要考虑的点。

一种简单的处理方式是在转换过程中记录已经访问过的节点，如果再次访问到相同的节点，则停止递归或抛出错误。另一种方式是在数据结构上避免循环引用，例如通过限制节点的深度或使用更复杂的数据结构。

function arrayToTreeWithCycleDetection(arr) {
  const tree = [];
  const map = {};
  const visited = new Set(); // 用于记录已经访问过的节点

  arr.forEach(item => {
    map[item.id] = item;
    item.children = [];
  });

  arr.forEach(item => {
    const parent = map[item.parentId];

    if (visited.has(item.id)) {
      console.warn(`Detected cycle involving node with id: ${item.id}. Skipping.`);
      return; // 跳过当前节点，避免无限循环
    }

    visited.add(item.id); // 标记当前节点为已访问

    if (parent) {
      parent.children.push(item);
    } else {
      tree.push(item);
    }
  });

  return tree;
}

这个版本增加了一个 visited Set，用于记录已经访问过的节点。在每次访问一个节点之前，先检查它是否已经被访问过。如果已经被访问过，则说明存在循环引用，跳过当前节点，避免无限循环。

如何处理排序需求？

有时，我们可能需要对树形结构中的节点进行排序，例如按照节点的名称或创建时间排序。这可以在 arrayToTree 函数中添加排序逻辑。

一种常见的做法是在将子节点添加到父节点之后，对子节点进行排序。可以使用 JavaScript 的 sort 方法来实现排序。

function arrayToTreeWithSorting(arr, sortFn) {
  const tree = [];
  const map = {};

  arr.forEach(item => {
    map[item.id] = item;
    item.children = [];
  });

  arr.forEach(item => {
    const parent = map[item.parentId];
    if (parent) {
      parent.children.push(item);
    } else {
      tree.push(item);
    }
  });

  // 对每个节点的 children 数组进行排序
  function sortChildren(node) {
    if (node.children && node.children.length > 0) {
      node.children.sort(sortFn);
      node.children.forEach(sortChildren); // 递归排序子节点的 children
    }
  }

  tree.forEach(sortChildren); // 对根节点进行排序

  return tree;
}

// 示例排序函数，按照 name 属性排序
function sortByName(a, b) {
  return a.name.localeCompare(b.name);
}

// 使用示例
// const tree = arrayToTreeWithSorting(data, sortByName);

这个版本增加了一个 sortFn 参数，用于指定排序函数。在将子节点添加到父节点之后，调用 sort 方法对子节点进行排序。为了保证所有节点都被排序，需要递归地对每个节点的 children 数组进行排序。

好了，本文到此结束，带大家了解了《JS数组树形结构转换全解析》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！