多层级数据结构：递归计算存款总额方法

哈喽！大家好，很高兴又见面了，我是golang学习网的一名作者，今天由我给大家带来一篇《多层级数据结构：递归汇总存款金额方法》，本文主要会讲到等等知识点，希望大家一起学习进步，也欢迎大家关注、点赞、收藏、转发! 下面就一起来看看吧！

本教程旨在解决如何从多层级嵌套数据结构中，按层级精确汇总用户存款金额的问题。通过引入递归遍历策略，我们展示了如何有效地处理父子关系链，确保每个层级的总金额被独立计算并存储，从而避免了传统扁平化处理导致的数据混淆，实现清晰、准确的层级数据统计。

1. 问题背景与数据结构

在许多业务场景中，我们经常会遇到具有层级关系的数据，例如组织架构、推荐系统中的用户层级、文件目录结构等。本教程关注的是一个典型的推荐系统场景，其中用户可以有下级，下级也可以有自己的下级，形成一个多达五层的嵌套结构。每个用户节点都包含一个deposit（存款）字段。

我们的目标是计算并获取每个层级的用户总存款金额。例如，如果第一层有总计300的存款，第二层也有总计300的存款，以此类推，最终结果应为一个数组，如 [300, 300, 300, 300]。

以下是简化的数据结构示例：

let hierarchicalData = [
    {
        "id": "ddf86d60-a607-4a4e-a7f9-d96013ee7070",
        "name": "Rick Rich",
        "deposit": 100,
        "children": [
            {
                "id": "25de2e98-eb2d-41f4-b225-3069f942b284",
                "name": "Rick Rich",
                "deposit": 100,
                "children": [
                    {
                        "id": "376b202e-d44f-4402-9560-8498c855d05e",
                        "name": "Rick Rich",
                        "deposit": 100,
                        "children": [
                            { "deposit": 100 },
                            { "deposit": 100 },
                            { "deposit": 100 }
                        ]
                    },
                    { "deposit": 100, "children": [] },
                    { "deposit": 100, "children": [] }
                ]
            },
            { "deposit": 100, "children": [] },
            { "deposit": 100, "children": [] }
        ]
    },
    { "deposit": 100, "children": [] },
    { "deposit": 0, "children": [] }
];

在这个结构中，最外层的数组代表第一层用户。每个用户对象中的 children 数组则代表其下一层级的用户。

2. 常见误区：扁平化处理的局限性

初学者在处理这类问题时，常会尝试使用简单的遍历和递归来收集所有存款，但这种方法往往会导致数据扁平化，无法区分不同层级的金额。

例如，以下代码片段展示了一种常见的错误尝试：

// 错误的尝试示例
const iterateOfChildrenDepositIncorrect = (
    children: any[], // 假设 Children 类型包含 deposit 和 children
    result: number[] = [],
): void => {
    children.forEach((node: any) => {
        result.push(node.deposit); // 直接将存款添加到结果数组
        if (node.children && node.children.length > 0) {
            iterateOfChildrenDepositIncorrect(node.children, result); // 递归处理子节点
        }
    });
    // 在实际应用中，result 会被更新到状态或返回
    // setUserDeposit(result);
};

let incorrectResult = [];
iterateOfChildrenDepositIncorrect(hierarchicalData, incorrectResult);
console.log(incorrectResult); // 输出所有存款的扁平列表，如 [100, 100, 100, 100, 100, 100, ...]

这段代码的问题在于，它将所有层级的 deposit 值都简单地添加到同一个 result 数组中。虽然它能收集所有存款，但无法提供每个层级的总和，因为 result 数组中的元素没有层级信息。我们需要的是一个表示每个层级总和的数组，而不是所有个体存款的列表。

3. 正确方法：基于递归的层级遍历

要实现按层级汇总，我们需要一种机制来在处理当前层级时，收集所有子节点以便在下一轮递归中处理，同时计算当前层级的总和。这可以通过一种类似于广度优先搜索（BFS）的递归方法来实现。

核心思想是：

1. 在每次递归调用中，处理“当前层级”的所有节点。
2. 计算这些节点的存款总和，并将其添加到最终结果数组中。
3. 收集“当前层级”所有节点的子节点，将它们合并成一个列表，作为“下一层级”的数据。
4. 如果“下一层级”有数据，则用它进行下一次递归调用。

3.1 递归函数实现

以下是实现按层级汇总存款的递归函数：

let hierarchicalDataSimplified = [
    {
        "deposit": 100,
        "children": [
            {
                "deposit": 100,
                "children": [
                    {
                        "deposit": 100,
                        "children": [
                            { "deposit": 100 },
                            { "deposit": 100 },
                            { "deposit": 100 }
                        ]
                    },
                    { "deposit": 100, "children": [] },
                    { "deposit": 100, "children": [] }
                ]
            },
            { "deposit": 100, "children": [] },
            { "deposit": 100, "children": [] }
        ]
    },
    { "deposit": 100, "children": [] },
    { "deposit": 0, "children": [] }
];

let resultByLevel = []; // 用于存储每个层级总存款的数组

/**
 * 递归函数，用于按层级汇总存款金额
 * @param {Array<Object>} children - 当前层级的节点数组
 * @param {Array<number>} result - 存储各层级总金额的数组
 */
function iterateOfChildrenDeposit(children, result) {
    let nextLevelChildren = []; // 存储下一层级的所有子节点
    let currentLevelDepositSum = 0; // 当前层级的存款总和

    // 遍历当前层级的所有节点
    children.forEach((node) => {
        currentLevelDepositSum += node.deposit; // 累加当前节点的存款
        // 如果当前节点有子节点，则将它们添加到下一层级的集合中
        if (node.children && node.children.length > 0) {
            nextLevelChildren = nextLevelChildren.concat(node.children);
        }
    });

    // 将当前层级的总存款添加到结果数组
    result.push(currentLevelDepositSum);

    // 如果下一层级有节点，则进行递归调用
    if (nextLevelChildren.length > 0) {
        return iterateOfChildrenDeposit(nextLevelChildren, result);
    }

    // 递归终止条件：没有下一层级节点
    return;
}

// 调用函数开始处理
iterateOfChildrenDeposit(hierarchicalDataSimplified, resultByLevel);
console.log(resultByLevel); // 预期输出: [300, 300, 300, 300]

3.2 代码解析

1. resultByLevel = []: 这是一个全局或外部数组，用于收集每一层计算出的总存款。
2. iterateOfChildrenDeposit(children, result): 这是核心递归函数。
   • children: 代表当前正在处理的层级中的所有节点。
   • result: 引用外部的 resultByLevel 数组，用于累积结果。
3. let nextLevelChildren = [];: 在每次函数调用（即处理一个新层级）开始时，初始化一个空数组，用于临时存储当前层级所有节点的子节点。这些子节点将构成下一层级。
4. let currentLevelDepositSum = 0;: 初始化当前层级的存款总和。
5. children.forEach((node) => { ... });: 遍历 children 数组中的每一个节点。
   • currentLevelDepositSum += node.deposit;: 将当前节点的 deposit 值累加到 currentLevelDepositSum 中。
   • if (node.children && node.children.length > 0) { nextLevelChildren = nextLevelChildren.concat(node.children); }: 检查当前节点是否有子节点。如果有，则使用 concat 方法将这些子节点添加到 nextLevelChildren 数组中。concat 确保了所有子节点都被收集，无论它们属于哪个父节点。
6. result.push(currentLevelDepositSum);: 在遍历完当前层级的所有节点并计算出总和后，将 currentLevelDepositSum 添加到 result 数组中。这保证了 result 数组的每个元素对应一个层级的总和。
7. if (nextLevelChildren.length > 0) { return iterateOfChildrenDeposit(nextLevelChildren, result); }: 这是一个关键的递归步骤。如果 nextLevelChildren 数组不为空（即存在下一层级），则以 nextLevelChildren 作为新的 children 参数，递归调用 iterateOfChildrenDeposit 函数，继续处理下一层级。
8. return;: 当 nextLevelChildren 为空时，表示已经没有更深层级的节点，递归终止。

4. 注意事项与扩展

• 最大层级限制: 题目中提到最大5层，这种递归方法能自然地处理任意深度的层级（只要不超过JavaScript引擎的递归深度限制，通常远大于5层）。
• 性能考量: 对于非常深或非常宽的层级结构，递归可能会导致栈溢出。在这种情况下，可以考虑使用迭代式的广度优先搜索（BFS）算法，它使用队列来管理待处理的节点，避免了深层递归。
• 数据完整性: 确保 deposit 字段始终存在且为数字类型，children 字段如果不存在或为空数组，代码也能正确处理。
• TypeScript 类型: 如果在 TypeScript 环境中使用，可以定义 Children 接口来增强类型安全性，例如：

  interface ChildNode {
      id?: string;
      name?: string;
      deposit: number;
      bonus?: number;
      referralChildDeposit?: number;
      children?: ChildNode[];
  }

5. 总结

通过本教程，我们学习了如何利用递归函数有效地处理多层级嵌套数据结构，并按层级汇总特定数据（如存款金额）。关键在于在每次递归调用中，不仅要计算当前层级的数据，还要收集下一层级的全部节点，作为下一次递归的输入。这种方法确保了层级信息的独立性，避免了数据扁平化带来的混淆，是处理树形或图状数据结构的强大工具。理解并掌握这种递归模式，对于开发涉及复杂数据关系的应用程序至关重要。

本篇关于《多层级数据结构：递归计算存款总额方法》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！