如何从组织架构数据中快速查找父级和祖父级信息在日常开发中，处理层级关系复杂的数据结构是非常常见的场景，比如组织架构树。通

在日常开发中，处理层级关系复杂的数据结构是非常常见的场景，比如组织架构树。通常，我们需要从某个子节点出发，查找其对应的父节点或祖父节点，甚至是根据多个节点批量查找。本文将介绍如何高效地处理这种需求，尤其是在面对上万条数据时，确保性能和准确性。

问题背景

假设我们有一个公司的组织架构树，树中的每个节点代表一个部门，且每个部门都有唯一的 code，如下所示：

{
  "name": "公司总部",
  "code": "001",
  "children": [
    {
      "name": "市场部",
      "code": "002",
      "children": [
        {
          "name": "国内市场",
          "code": "0021",
          "children": []
        },
        {
          "name": "国际市场",
          "code": "0022",
          "children": []
        }
      ]
    },
    {
      "name": "研发部",
      "code": "003",
      "children": [
        {
          "name": "前端组",
          "code": "0031",
          "children": []
        },
        {
          "name": "后端组",
          "code": "0032",
          "children": [
            {
              "name": "数据库组",
              "code": "00321",
              "children": []
            }
          ]
        }
      ]
    }
  ]
}

现在，如果我们要查找某些部门的父级或祖父级，比如 国内市场（code: 0021） 和 国际市场（code: 0022），并且还想根据多个部门的 code 同时查找，这时候我们需要一种高效的方式。

递归的基础查找方法

首先可以通过递归方法遍历整个组织架构树，找到目标部门的父级和祖父级。这种方法的思路简单：每个节点都检查自己是否是目标节点，如果是，则返回当前节点的父级和祖父级；否则继续遍历子节点。

function findParentByCode(tree, targetCode, parent = null, grandparent = null) {
  if (tree.code === targetCode) {
    return {
      code: targetCode,
      parent: parent ? parent.code : null,
      grandparent: grandparent ? grandparent.code : null
    };
  }

  if (tree.children && tree.children.length > 0) {
    for (let child of tree.children) {
      const result = findParentByCode(child, targetCode, tree, parent);
      if (result) {
        return result;
      }
    }
  }

  return null;
}

递归查找方式在节点数量较少时能够很好地工作，但当组织架构树中有成千上万条数据时，递归带来的性能问题逐渐显现：

1. 递归深度限制：JavaScript 的递归调用有栈深度限制，遇到深层级的树结构时，可能会导致栈溢出。
2. 性能瓶颈：每次查找一个 code，都需要遍历整个树，时间复杂度为 O(n)，如果需要查找多个 code，总时间复杂度为 O(n * m)，其中 n 是树的节点数，m 是 codes 数组的长度。在大数据量时，这样的性能是不可接受的。

性能优化：构建映射表

为了应对上万条数据的组织架构，递归查找的效率不足。为了提高性能，我们可以在初始加载数据时，构建一个映射表。映射表会将每个节点的 code 与其父级和祖父级信息关联起来。映射表将每个节点的 code 映射到它的父级和祖父级，查找时只需通过键值对的形式进行查询，时间复杂度大幅降低到 O(1)。后续查找时就可以直接通过 code 进行查询，而不需要递归遍历整个树。

// 构建映射表
function buildCodeMap(tree, parent = null, grandparent = null, map = {}) {
  map[tree.code] = {
    parent: parent ? parent.code : null,
    grandparent: grandparent ? grandparent.code : null
  };

  if (tree.children && tree.children.length > 0) {
    tree.children.forEach(child => {
      buildCodeMap(child, tree, parent, map);
    });
  }

  return map;
}

通过这段代码，我们可以将树状结构“平面化”，得到一个 code 到其父级和祖父级的映射表。比如，对应的 map 可能会是这样的结构：

{
  "001": { "parent": null, "grandparent": null },
  "002": { "parent": "001", "grandparent": null },
  "0021": { "parent": "002", "grandparent": "001" },
  "0022": { "parent": "002", "grandparent": "001" },
  "00321": { "parent": "0032", "grandparent": "003" }
}

查找多个节点并去重

当我们需要查找多个节点的父级和祖父级时，可以利用映射表快速找到对应信息。同时，如果多个节点的父级和祖父级相同，我们还希望对这些结果进行去重，确保最终的结果不包含重复项。

// 查找多个 code 的父级和祖父级
function findParentsByCodesUsingMap(codeMap, codes) {
  const results = [];
  const uniqueResults = new Set();

  codes.forEach(code => {
    const result = codeMap[code];
    if (result) {
      const identifier = `${result.parent}-${result.grandparent}`;
      if (!uniqueResults.has(identifier)) {
        uniqueResults.add(identifier);
        results.push({ code, ...result });
      }
    }
  });

  return results;
}

这样，假如我们查找 ['0021', '0022', '00321']，并且 0021 和 0022 的父级和祖父级相同，最终我们只会返回一次 002 和 001 组合。

扩展功能：递归添加父级和祖父级到 codes

有时我们不仅需要查找原始 codes 中的父级和祖父级，还需要将这些父级和祖父级也添加到 codes 中并去重。这时，我们可以将查找到的父级和祖父级不断加入到一个集合中，直到所有相关信息都被处理完。

// 获取所有 parent 和 grandparent，并去重
function extractUniqueParentsAndGrandparents(results) {
  const uniqueCodes = new Set();

  results.forEach(item => {
    if (item.parent) uniqueCodes.add(item.parent);
    if (item.grandparent) uniqueCodes.add(item.grandparent);
  });

  return Array.from(uniqueCodes);
}

// 查找多个 code 对应的父级和祖父级并去重
const codes = ['0021', '0022'];
const codeMap = buildCodeMap(orgTree);
console.log(codeMap, 'codeMap');
const results = findParentsByCodesUsingMap(codeMap, codes);
console.log(results, 'results');

// 提取所有的 parent 和 grandparent，并去重
const uniqueParentsAndGrandparents =
  extractUniqueParentsAndGrandparents(results);

// 将 uniqueParentsAndGrandparents 添加到 codes 中并去重
const finalCodes = new Set([...codes, ...uniqueParentsAndGrandparents]);

console.log(Array.from(finalCodes), 'finalCodes');

总结

处理复杂的组织架构树数据时，直接使用递归方法虽然简单，但在大规模数据下可能性能不足。通过构建映射表，可以显著提高查询效率，并通过集合 (Set) 来去重，确保结果的唯一性。

使用这些优化手段，我们可以在面对成千上万条数据时，依然保持高效、可靠地查找和处理节点的层级关系。这种方法不仅适用于组织架构树，在其他类似的层级数据结构中同样适用。