深度优先构建嵌套树结构技巧

偷偷努力，悄无声息地变强，然后惊艳所有人！哈哈，小伙伴们又来学习啦~今天我将给大家介绍《深度优先构建嵌套树结构方法》，这篇文章主要会讲到等等知识点，不知道大家对其都有多少了解，下面我们就一起来看一吧！当然，非常希望大家能多多评论，给出合理的建议，我们一起学习，一起进步！

本文详细阐述了如何将一个扁平的、包含项目及其依赖关系的对象转换为一个嵌套的树形结构。通过识别具有多重父级、单一父级或无父级的节点，并结合深度优先搜索（DFS）算法，可以有效处理循环依赖并根据特定规则构建出清晰、逻辑分明的层级结构，避免常见的栈溢出问题。

在软件工程或项目管理中，我们经常会遇到需要表示模块或文件之间依赖关系的情况。一个常见的场景是，我们有一个对象，其键代表项目或模块，值是它们所依赖的其他模块列表。我们的目标是将这种扁平的依赖关系转换为一个直观的、嵌套的树形结构，类似于文件系统中的目录结构。这个过程需要遵循特定的规则来确定节点的嵌套深度，并且必须能够健壮地处理潜在的循环依赖问题，以避免无限递归或栈溢出。

核心挑战与规则

将依赖对象转换为树形结构面临的主要挑战在于如何确定每个节点的正确位置，尤其是在存在多重依赖或循环依赖时。为了确保生成的树结构符合预期，我们需要遵循以下规则：

1. 无依赖的顶层节点： 任何未被其他依赖项使用的依赖项，应作为树的顶层节点。
2. 单一依赖的嵌套： 任何仅被一个依赖项使用的依赖项，应嵌套在该依赖项之下，以此类推。
3. 多重依赖的同级处理： 任何被两个或更多依赖项使用的依赖项，应作为其最高层父节点的同级节点（即，它将成为一个独立的顶层节点，或者位于某个高层节点之下，但不会被其所有父节点重复嵌套）。

考虑以下复杂示例：

{
  'a': ['b', 'q'],
  'b': ['c', 'f'],
  'c': ['d'],
  'p': ['o'],
  'o': [],
  "d": [],
  'e': ['c'],
  "q": []
}

期望的输出结构应为：

{
  'a': {
    'b': {
      "f": {}
    },
    'q': {}
  },
  "p": {
    'o': {}
  },
  "c": { // 'c' 被 'b' 和 'e' 依赖，因此它成为顶层节点
    "d": {}
  },
  "e": {} // 'e' 依赖 'c'，但 'c' 已是顶层，所以 'e' 独立存在
}

可以看到，c 节点因为被 b 和 e 两个节点依赖，所以它不再嵌套在 b 之下，而是提升为顶层节点。

解决方案：基于分类与深度优先搜索

解决此问题的关键在于对依赖项进行分类，并结合深度优先搜索（DFS）来构建树。

1. 依赖项分类

在开始构建树之前，我们需要对所有依赖项进行预处理，将它们分为三类：

• 具有多个父级的依赖项 (withMultipleParents)： 这些是那些在整个依赖图中被多个其他节点引用的依赖项。根据规则3，它们通常会成为顶层节点或较高层级的同级节点。
• 具有单一父级的依赖项 (withSingleParents)： 这些是那些仅被一个其他节点引用的依赖项。根据规则2，它们将被嵌套在其唯一的父级之下。
• 没有父级的顶层节点 (withNoParents)： 这些是那些未被任何其他节点引用的键，或者根据规则3被提升为顶层/高层同级节点的那些具有多个父级的依赖项。

2. 深度优先搜索 (DFS)

一旦分类完成，我们就可以使用 DFS 来递归地构建树。DFS 函数的核心思想是：

• 记忆化 (Memoization)： 为了避免循环依赖导致的无限递归和重复构建，使用一个 nodes 对象来存储已构建的节点。如果一个节点已被访问并构建，直接返回其引用。
• 条件嵌套： 在遍历当前节点的子依赖时，只有当子依赖属于“具有单一父级的依赖项”时，才进行递归调用并将其嵌套在当前节点下。如果子依赖具有多个父级，则不在此处嵌套，因为它会在 withNoParents 列表中被单独处理。

实现步骤

下面是具体的 JavaScript 实现代码及其解释：

/**
 * 从数组中排除指定集合中的值
 * @param {Array} arr - 原始数组
 * @param {Set} omitSet - 包含要排除值的集合
 * @returns {Array} - 过滤后的数组
 */
const exclude = (arr, omitSet) => arr.filter(val => !omitSet.has(val));

/**
 * 找出数组中重复的元素，并返回一个包含这些重复元素的集合
 * @param {Array} arr - 原始数组
 * @returns {Set} - 包含重复元素的集合
 */
const duplicateSet = (arr) =>
    new Set(arr.filter(function (val) {
        // 使用一个临时的Set来跟踪元素是否是第一次出现
        // 如果delete成功（说明之前存在），则表示当前val是重复的
        return !this.delete(val);
    }, new Set(arr))); // 初始Set包含所有元素，用于后续的delete操作

/**
 * 将扁平的依赖对象转换为嵌套的树形结构
 * @param {Object} data - 依赖对象，键为项目，值为其依赖列表
 * @returns {Object} - 嵌套的树形结构
 */
function toNested(data) {
    // nodes 用于存储已构建的节点，防止循环依赖和重复构建
    const nodes = {};
    // 收集所有子依赖项
    const descendants = Object.values(data).flat();

    // 1. 识别具有多个父级的依赖项
    const withMultipleParents = duplicateSet(descendants);

    // 2. 识别具有单一父级的依赖项
    // 它们是所有子依赖项中，排除了那些具有多个父级的项
    const withSingleParents = new Set(exclude(descendants, withMultipleParents));

    // 3. 识别顶层键 (withNoParents)
    // 包括：
    //   a) 那些在data的键中，但没有作为任何单一父级依赖项出现的键（即没有父级）
    //   b) 所有具有多个父级的依赖项（根据规则3，它们成为顶层或高层同级）
    const withNoParents = [
        ...exclude(Object.keys(data), withSingleParents),
        ...withMultipleParents
    ];

    /**
     * 深度优先搜索函数，递归构建节点
     * @param {string} key - 当前要构建的节点键
     * @returns {Object} - 构建好的节点对象
     */
    function dfs(key) {
        // 如果节点已存在（已被访问并构建），直接返回，避免循环依赖和重复工作
        if (nodes[key]) return nodes[key];

        // 初始化当前节点为空对象
        nodes[key] = {};

        // 遍历当前节点的所有子依赖
        // data[key] ?? [] 处理 key 不存在或其值为 undefined/null 的情况
        for (const child of data[key] ?? []) {
            // 只有当子依赖是“单一父级依赖”时，才进行嵌套递归
            // 具有多个父级的子依赖会在 withNoParents 列表中被处理，不在此处嵌套
            if (withSingleParents.has(child)) {
                nodes[key][child] = dfs(child);
            }
        }
        return nodes[key];
    }

    // 从所有顶层键开始，调用 DFS 构建完整的树
    // Object.fromEntries 将 [key, value] 对数组转换为对象
    return Object.fromEntries(withNoParents.map(key => [key, dfs(key)]));
}

// 示例数据
const data = {
    'a': ['b', 'q'],
    'b': ['c', 'f'],
    'c': ['d'],
    'p': ['o'],
    'o': [],
    "d": [],
    'e': ['c'],
    "q": []
};

console.log(toNested(data));

示例解析

让我们使用提供的复杂示例来逐步理解代码的执行：

1. descendants 会是 ['b', 'q', 'c', 'f', 'd', 'o', 'c']。
2. withMultipleParents: duplicateSet 会识别出 c 是重复的，所以 withMultipleParents 为 Set({'c'})。
3. withSingleParents: exclude(descendants, withMultipleParents) 会得到 ['b', 'q', 'f', 'd', 'o']，所以 withSingleParents 为 Set({'b', 'q', 'f', 'd', 'o'})。
4. Object.keys(data) 为 ['a', 'b', 'c', 'p', 'o', 'd', 'e', 'q']。
5. exclude(Object.keys(data), withSingleParents)：
   • 'a' 不在 withSingleParents 中，保留。
   • 'b' 在 withSingleParents 中，排除。
   • 'c' 不在 withSingleParents 中，保留。
   • 'p' 不在 withSingleParents 中，保留。
   • 'o' 在 withSingleParents 中，排除。
   • 'd' 在 withSingleParents 中，排除。
   • 'e' 不在 withSingleParents 中，保留。
   • 'q' 在 withSingleParents 中，排除。
   • 结果为 ['a', 'c', 'p', 'e']。
6. withNoParents: [...['a', 'c', 'p', 'e'], ...['c']] 最终合并并去重后得到 ['a', 'c', 'p', 'e']。
   • 注意：虽然 c 在两个列表中都出现，但作为 Set 元素或数组元素时，其唯一性会被处理，最终 withNoParents 包含 a, c, p, e 这些将作为顶层键的元素。

现在，toNested 函数会遍历 withNoParents 中的每个键，并调用 dfs：

• dfs('a'):

  • nodes['a'] = {}。
  • 遍历 data['a'] -> ['b', 'q']。
  • 'b' 在 withSingleParents 中，调用 dfs('b')。
    • dfs('b'):
      • nodes['b'] = {}。
      • 遍历 data['b'] -> ['c', 'f']。
      • 'c' 不在 withSingleParents 中（因为它在 withMultipleParents 中），跳过嵌套。
      • 'f' 在 withSingleParents 中，调用 dfs('f')。
        • dfs('f'): nodes['f'] = {}。data['f'] 为 undefined，无子项。返回 {}。
      • nodes['b']['f'] = {}。
      • 返回 {'f': {}}。
    • nodes['a']['b'] = {'f': {}}。
  • 'q' 在 withSingleParents 中，调用 dfs('q')。
    • dfs('q'): nodes['q'] = {}。data['q'] 为 []，无子项。返回 {}。
  • nodes['a']['q'] = {}。
  • 返回 {'b': {'f': {}}, 'q': {}}。

• dfs('c'):

  • nodes['c'] = {}。
  • 遍历 data['c'] -> ['d']。
  • 'd' 在 withSingleParents 中，调用 dfs('d')。
    • dfs('d'): nodes['d'] = {}。data['d'] 为 []，无子项。返回 {}。
  • nodes['c']['d'] = {}。
  • 返回 {'d': {}}。

• dfs('p'):

  • nodes['p'] = {}。
  • 遍历 data['p'] -> ['o']。
  • 'o' 在 withSingleParents 中，调用 dfs('o')。
    • dfs('o'): nodes['o'] = {}。data['o'] 为 []，无子项。返回 {}。
  • nodes['p']['o'] = {}。
  • 返回 {'o': {}}。

• dfs('e'):

  • nodes['e'] = {}。
  • 遍历 data['e'] -> ['c']。
  • 'c' 不在 withSingleParents 中，跳过嵌套。
  • 返回 {}。

最终，Object.fromEntries 将这些顶层键及其对应的构建结果组合起来，形成最终的树形结构。

注意事项与总结

• 循环依赖处理： dfs 函数中的 if (nodes[key]) return nodes[key]; 这一行是处理循环依赖的关键。它通过记忆化确保每个节点只被构建一次。如果遇到循环，它会直接返回已存在的节点，而不是陷入无限递归。
• 规则3的体现： withMultipleParents 的识别以及只对 withSingleParents 进行递归嵌套的逻辑，是实现“多重依赖的同级处理”规则的核心。被多个父级依赖的节点会被提升到顶层或更高层级，而不是被重复嵌套。
• 代码健壮性： data[key] ?? [] 的用法确保了即使 data 对象中某个键没有对应的依赖列表（或为 null/undefined），代码也能正常运行，不会抛出错误。
• 性能考量： 对于非常大的依赖图，这种方法需要对所有依赖进行一次扁平化和分类，然后进行 DFS。虽然 DFS 本身是高效的（每个节点和边最多访问一次），但预处理步骤的性能取决于 flat() 和 filter() 等操作的效率。通常情况下，对于中等规模的依赖图，性能表现良好。

通过这种分类和深度优先搜索相结合的方法，我们能够优雅地将复杂的依赖对象转换为清晰、符合特定规则的树形结构，同时有效地避免了循环依赖带来的问题。

好了，本文到此结束，带大家了解了《深度优先构建嵌套树结构技巧》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！