多级嵌套数据结构按层级统计总金额的递归实现-js教程-PHP中文网

多级嵌套数据结构按层级统计总金额的递归实现

聖光之護

发布： 2025-10-08 13:25:19

原创

508人浏览过

多级嵌套数据结构按层级统计总金额的递归实现

本教程详细介绍了如何在具有多级嵌套关系的复杂数据结构中，准确地按层级统计每个层级的总金额。通过分析常见的错误方法，并提供一个高效的递归算法，演示了如何遍历树形结构，累加每个层级的存款总额，最终生成一个表示各层级总和的数组。

引言：理解多级嵌套数据结构与层级统计需求

在许多业务场景中，我们经常会遇到具有层级关系的数据，例如组织架构、推荐系统中的用户层级、或文件系统等。这些数据通常以嵌套的结构表示，其中每个节点可能包含子节点。本教程将以一个典型的用户推荐网络为例，讲解如何准确地统计每个层级用户的存款总额。

假设我们有一个用户体系，每个用户可能推荐多个下级用户，这些下级用户又可能继续推荐他们的下级，形成一个多达五层的层级结构。每个用户都有一个 deposit（存款）属性。我们的目标是计算并返回一个数组，其中每个元素代表对应层级的用户存款总和。例如，如果第一层总存款为300，第二层总存款为300，依此类推，最终结果应为 [300, 300, 300, 300]。

数据结构示例如下（为清晰起见，已简化部分字段）：

[
    {
        "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": []
    }
]

登录后复制

在这个例子中，最外层的数组代表了第一层用户。每个用户对象可能包含一个 children 数组，代表其直接下级用户。

常见误区分析：为什么简单的递归累加不奏效？

初学者在处理此类问题时，常会尝试使用递归遍历，并直接将每个节点的存款推入一个结果数组。例如，以下代码片段展示了一个常见的错误思路：

const iterateOfChildrenDeposit = (
    children: Children[], // 这里的 children 实际上是当前层级的节点数组
    result: number[] = [],
): void => {
    children.forEach((node: Children) => {
        result.push(node.deposit); // 将每个节点的存款直接推入结果数组
        if (node.children) {
            iterateOfChildren(node.children, result); // 递归处理子节点
        }
    });
    // setUserDeposit(result); // 在 React 环境中可能这样更新状态
};

登录后复制

这段代码的问题在于，result.push(node.deposit) 操作会将所有层级的存款扁平化地添加到一个数组中。例如，如果第一层有3个用户，第二层有5个用户，它会先添加第一层的3个存款，然后递归进入第二层，再添加第二层的5个存款，最终得到的是一个包含所有用户存款的扁平数组，而不是按层级分组的总和数组，例如 [100, 100, 0, 100, 100, 100, 100, 100, 100]。这与我们期望的 [第一层总和, 第二层总和, ...] 的结果不符。

解决方案：基于广度优先思想的递归实现

要实现按层级统计总金额，我们需要一种机制来：

在处理当前层级时，累加其所有节点的存款。
同时收集当前层级所有节点的子节点，作为下一个层级进行处理。
在当前层级处理完毕后，将其总和记录下来，并递归处理收集到的下一层级节点。

这种方法本质上是一种广度优先遍历（BFS）的递归实现，确保了我们能够逐层处理数据。

以下是实现此功能的 JavaScript 递归函数：

let hierarchicalData = [
    {
        "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 levelDepositsResult = []; // 用于存储最终结果的数组

/**
 * 递归函数，按层级计算存款总额
 * @param {Array<Object>} currentLevelNodes - 当前层级的节点数组
 * @param {Array<number>} resultAccumulator - 用于累积各层级总额的结果数组
 */
function calculateLevelDeposits(currentLevelNodes, resultAccumulator) {
    let currentLevelTotal = 0; // 记录当前层级的存款总和
    let nextLevelChildren = []; // 收集所有子节点，作为下一个层级

    // 遍历当前层级的所有节点
    currentLevelNodes.forEach(node => {
        currentLevelTotal += node.deposit; // 累加当前节点的存款
        // 如果当前节点有子节点，则将其子节点添加到 nextLevelChildren 数组中
        if (node.children && node.children.length > 0) {
            nextLevelChildren = nextLevelChildren.concat(node.children);
        }
    });

    // 将当前层级的总金额添加到结果数组
    resultAccumulator.push(currentLevelTotal);

    // 如果存在下一层级的节点，则进行递归调用
    if (nextLevelChildren.length > 0) {
        calculateLevelDeposits(nextLevelChildren, resultAccumulator);
    }
    // 否则，递归结束
}

// 初始调用，传入最顶层节点数组和结果存储数组
calculateLevelDeposits(hierarchicalData, levelDepositsResult);
console.log(levelDepositsResult); // 期望输出: [200, 300, 300] (根据提供的示例数据)

登录后复制

代码详解：

BibiGPT-哔哔终结者

B站视频总结器-一键总结音视频内容

查看详情

calculateLevelDeposits(currentLevelNodes, resultAccumulator) 函数：
- currentLevelNodes：此参数接收一个数组，包含当前正在处理的所有节点。在第一次调用时，它将是整个顶层数据数组。
- resultAccumulator：这是一个引用，指向最终存储各层级总金额的数组。通过引用传递，递归调用可以在同一个数组上进行累加。
currentLevelTotal 和 nextLevelChildren：
- currentLevelTotal：在每次函数调用开始时被初始化为 0，用于累加当前 currentLevelNodes 中所有节点的 deposit 值。
- nextLevelChildren：同样在每次调用开始时初始化为空数组，用于收集 currentLevelNodes 中所有节点的子节点。这些子节点将构成下一个递归调用的 currentLevelNodes。
forEach 循环：
- 遍历 currentLevelNodes 中的每一个节点。
- currentLevelTotal += node.deposit;：将当前节点的存款累加到 currentLevelTotal。
- if (node.children && node.children.length > 0) { ... }：检查当前节点是否有子节点。如果有，则使用 concat 方法将这些子节点添加到 nextLevelChildren 数组中。concat 是为了避免直接修改 node.children 并且能将所有子节点扁平化收集。
resultAccumulator.push(currentLevelTotal);：
- 在遍历完当前层级的所有节点并计算出 currentLevelTotal 后，将其推入 resultAccumulator 数组。此时，resultAccumulator 中就多了一个层级的总金额。
递归条件与终止：
- if (nextLevelChildren.length > 0)：这是一个关键的递归条件。只有当 nextLevelChildren 数组不为空（即存在下一层级的节点）时，才进行递归调用。
- calculateLevelDeposits(nextLevelChildren, resultAccumulator);：将收集到的下一层级节点作为新的 currentLevelNodes，继续调用自身。
- 如果 nextLevelChildren 为空，说明已经到达了最底层，不再有子节点需要处理，递归自然终止。

通过上述逻辑，该函数能够精确地按层级计算并存储存款总额。对于提供的 hierarchicalData 示例，其输出将是 [200, 300, 300]，这与手动追踪数据结构所得结果一致。

注意事项与最佳实践

数据结构约定： 确保输入的数据结构符合预期，即每个节点对象包含 deposit 属性和可选的 children 数组。如果 children 属性可能缺失或为 null 而不是空数组，代码中的 if (node.children && node.children.length > 0) 判断可以很好地处理这种情况。
层级深度： 这种递归方法

以上就是多级嵌套数据结构按层级统计总金额的递归实现的详细内容，更多请关注php中文网其它相关文章！