JavaScript树形结构中递归更新父子节点数据教程

1. 问题背景与数据结构

在前端开发中，我们经常会遇到需要管理层级关系的数据，例如文件系统、组织架构或分类目录。这类数据通常以嵌套的数组或对象形式表示。本教程关注的是一种特定的树形结构，其中每个节点包含一个唯一的 key、名称 name、当前值 curr、总值 total，以及一个 nodes 数组来表示其子节点。

以下是一个典型的嵌套数据结构示例：

const data = [
  {
    key: "id1",
    name: "Category 1",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 20,
        total: 30,
        nodes: [
          {
            key: "id3",
            name: "Gaming",
            curr: 5,
            total: 10,
            nodes: []
          },
          {
            key: "id4",
            name: "Operating System",
            curr: 15,
            total: 20,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id5",
    name: "Category 2",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id6",
        name: "Sub Category",
        curr: 12,
        total: 48,
        nodes: [
          {
            key: "id7",
            name: "Inside Sub",
            curr: 12,
            total: 48,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id8",
    name: "Last One",
    curr: 0,
    total: 0,
    nodes: []
  }
];

我们的目标是：给定一个 key 和上述数据数组，找到匹配 key 的节点，将其 curr 值递增1。同时，这个递增操作需要向上级联，使其所有祖先节点的 curr 值也递增1。但有一个关键限制：最顶层（根级别，即 data 数组中的直接元素）的节点不应该被更新。

例如，如果调用 incrementRecursively(data, "id4")，期望的输出如下：

const output = [
  {
    key: "id1",
    name: "Category 1",
    curr: 0, // 注意：id1 是根节点，不更新
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 21, // id2 是 id4 的祖先，更新
        total: 30,
        nodes: [
          {
            key: "id3",
            name: "Gaming",
            curr: 5,
            total: 10,
            nodes: []
          },
          {
            key: "id4",
            name: "Operating System",
            curr: 16, // id4 是目标节点，更新
            total: 20,
            nodes: []
          }
        ]
      }
    ]
  },
  // ... 其他节点保持不变
];

2. 挑战分析

传统的递归遍历方法通常是从上到下执行操作。然而，本问题要求在找到目标节点后，将更新信息从下往上传递给祖先节点。同时，还需要区分不同层级的节点，以避免更新根节点。

立即学习“Java免费学习笔记（深入）”；

一个常见的尝试是使用 forEach 结合递归：

const incrementRecursively = (nodes, key) => {
  const increment = (nodes, key) => {
    nodes.forEach((node) => {
      if (node.key === key) {
        node.curr++; // 仅更新目标节点
      }
      if (node.nodes && node.nodes.length) { // 检查 node.nodes 是否存在且有元素
        increment(node.nodes, key); // 递归调用，但没有向上级联的能力
      }
    });
  };
  increment(nodes, key);
  return nodes;
};

上述代码的问题在于：

1. 它只会找到并更新匹配 key 的节点，但不会向上更新其父节点。
2. 即使尝试在 if (node.nodes.length) 之后添加 node.curr++，也会导致所有路径上的节点都被更新，而不仅仅是目标节点的祖先，并且无法避免更新根节点。

3. 解决方案：基于布尔值返回的递归

为了解决上述挑战，我们可以设计一个递归函数，该函数在找到目标节点或其子节点包含目标节点时，返回一个布尔值 true。这个布尔值将作为信号，指示其父节点也需要执行更新操作。同时，通过引入一个 depth 参数来跟踪当前节点的层级，我们可以轻松地排除根节点的更新。

核心思路：

Mureka

Mureka是昆仑万维最新推出的一款AI音乐创作工具，输入歌词即可生成完整专属歌曲。

下载

1. 函数遍历当前层级的节点。
2. 对于每个节点，检查它是否是目标节点，或者它的子节点是否包含目标节点（通过递归调用自身并检查返回值）。
3. 如果当前节点是目标节点，或其子节点（或更深层级的子节点）被更新，则当前节点也应该更新其 curr 值。
4. 在更新 curr 值时，检查 depth 参数：只有当 depth > 0 时才执行递增操作，从而跳过根节点。
5. 如果当前节点或其子节点发生了更新，函数返回 true，向其父节点传递信号。

4. 代码实现

/**
 * 递归更新树形结构中指定key的节点及其所有祖先节点的curr值，但不更新根节点。
 * @param {Array