递归更新树形结构中特定节点及其祖先的数值-js教程-PHP中文网

递归更新树形结构中特定节点及其祖先的数值

本教程详细介绍了如何在JavaScript中实现一个递归函数，用于更新树形数据结构中指定节点及其所有上级祖先（但不包括根节点）的curr属性值。通过深度参数和布尔返回值，该方法能够精确地定位目标节点，并沿路径向上逐级递增相关数值，确保数据的一致性更新。

1. 问题背景与数据结构

在许多应用场景中，我们经常会遇到需要处理树形或层级结构的数据。例如，一个多级分类系统、组织架构或文件目录。本教程关注的是一个典型的JavaScript对象数组表示的树形结构，其每个节点都包含以下关键属性：

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值，还要沿着其父节点链向上，递增所有祖先节点的curr值，但不包括最顶层（根级别，即data数组中的直接元素）的节点。

例如，如果传入key为 "id4"，那么"id4"节点及其父节点"id2"的curr值都应该递增1。而"id1"作为根级别节点，其curr值不应改变。

2. 解决方案：递归遍历与状态回溯

要实现上述功能，我们需要一个能够深度遍历树结构，并在找到目标节点后，将“更新”状态回溯给其父节点的机制。同时，还需要一个方法来区分根节点和其他节点，以避免更新根节点的curr值。

核心思路如下：

递归函数设计：创建一个递归函数，接收当前节点数组、目标key和当前节点的深度（或层级）。
深度参数：使用一个depth参数来跟踪当前遍历到的节点所处的层级。根节点（data数组中的元素）的depth为0，其子节点的depth为1，依此类推。
状态回溯：递归函数在遍历时，如果发现当前节点是目标节点，或者其任何子节点（通过递归调用）是目标节点，则返回true，表示“更新已发生或将在当前子树中发生”。
条件递增：当一个节点被告知其子树中发生了更新（即子递归调用返回true）时，它会检查自己的depth。如果depth > 0（即不是根节点），则递增自己的curr值。

3. 实现代码

以下是实现上述逻辑的JavaScript函数：

/**
 * 递归更新树形结构中指定节点及其祖先的curr值。
 *
 * @param {Array<Object>} nodes 当前层级的节点数组。
 * @param {string} key 目标节点的唯一标识符。
 * @param {number} depth 当前递归的深度，根节点为0。
 * @returns {boolean} 如果当前节点或其子节点被更新，则返回true；否则返回false。
 */
function updateNodeAndParentsRecursively(nodes, key, depth = 0) {
    // 遍历当前层级的所有节点
    for (let node of nodes) {
        // 检查当前节点是否是目标节点，或者其子节点（通过递归调用）是否是目标节点
        // 使用 ?? [] 确保即使 node.nodes 为 null/undefined 也能安全调用
        if (node.key === key || updateNodeAndParentsRecursively(node.nodes ?? [], key, depth + 1)) {
            // 如果当前节点或其子树中发生了更新
            // 并且当前节点不是根级别节点（depth > 0），则递增其curr值
            if (depth > 0) {
                node.curr++;
            }
            // 返回 true，向上级节点传递更新状态
            return true;
        }
    }
    // 如果遍历完当前层级所有节点及其子树，都没有找到目标节点或发生更新，则返回 false
    return false;
}

登录后复制

4. 代码解析

updateNodeAndParentsRecursively(nodes, key, depth = 0)：

即构数智人
即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

36

查看详情
- nodes: 当前正在处理的节点数组。在初始调用时，它是整个data数组。
- key: 我们要查找并更新的节点的key。
- depth = 0: 这是一个可选参数，用于跟踪当前节点在树中的深度。顶层节点（data数组的直接子项）的深度为0，它们的子节点深度为1，依此类推。这个参数是控制“不更新根节点”的关键。
for (let node of nodes)：
- 遍历当前nodes数组中的每一个节点。
if (node.key === key || updateNodeAndParentsRecursively(node.nodes ?? [], key, depth + 1))：
- 这是判断是否需要更新的关键条件。它包含两部分，用逻辑或||连接：
  - node.key === key: 检查当前节点是否就是我们要找的目标节点。如果是，那么这个条件为true。
  - updateNodeAndParentsRecursively(node.nodes ?? [], key, depth + 1): 递归调用自身，处理当前节点的子节点。
    - node.nodes ?? []: 使用空值合并运算符??，确保如果node.nodes是null或undefined，它会退化为空数组[]，防止在没有子节点时出错。
    - depth + 1: 在递归调用时，深度加1，表示进入下一层级。
    - 这个递归调用的返回值（true或false）表示在当前节点的子树中是否找到了目标节点并进行了更新。
- 如果上述任一条件为true，说明在当前节点或其子树中找到了目标节点。
if (depth > 0) { node.curr++; }：
- 这是实现“不更新根节点”的关键逻辑。
- 如果depth大于0，说明当前节点不是最顶层的节点（即它有父节点），此时才递增其curr值。
- 如果depth为0，说明当前节点是最顶层节点，即使其子树中发生了更新，它的curr值也不会被修改。
return true;：
- 如果当前节点或其子树中发生了更新，函数立即返回true。这个true会向上级调用传递，告知其父节点也需要考虑更新。
return false;：
- 如果for循环结束后，没有找到目标节点，也没有任何子节点返回true，则说明在当前节点及其整个子树中都没有发生更新，函数返回false。

5. 使用示例

现在我们来演示如何使用这个函数。

// 原始数据
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: []
  }
];

// 调用函数更新 'id4'
console.log("--- 更新 'id4' 之前 ---");
console.log(JSON.stringify(data, null, 2));

updateNodeAndParentsRecursively(data, 'id4');

console.log("\n--- 更新 'id4' 之后 ---");
console.log(JSON.stringify(data, null, 2));

/*
预期输出（部分关键节点）：
...
  {
    key: "id1",
    name: "Category 1",
    curr: 0, // 保持不变，因为是根节点
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 21, // 从20递增到21
        total: 30,
        nodes: [
          // ...
          {
            key: "id4",
            name: "Operating System",
            curr: 16, // 从15递增到16
            total: 20,
            nodes: []
          }
        ]
      }
    ]
  },
...
*/

// 再次调用函数更新 'id7'
console.log("\n--- 再次更新 'id7' 之前 ---");
console.log(JSON.stringify(data, null, 2));

updateNodeAndParentsRecursively(data, 'id7');

console.log("\n--- 再次更新 'id7' 之后 ---");
console.log(JSON.stringify(data, null, 2));

/*
预期输出（部分关键节点）：
...
  {
    key: "id5",
    name: "Category 2",
    curr: 0, // 保持不变，因为是根节点
    total: 0,
    nodes: [
      {
        key: "id6",
        name: "Sub Category",
        curr: 13, // 从12递增到13
        total: 48,
        nodes: [
          {
            key: "id7",
            name: "Inside Sub",
            curr: 13, // 从12递增到13
            total: 48,
            nodes: []
          }
        ]
      }
    ]
  },
...
*/

登录后复制

6. 注意事项与总结

原地修改：此函数会直接修改传入的data数组。如果需要保留原始数据，应在调用前对数据进行深拷贝。
性能：对于非常深或非常宽的树结构，递归调用可能会导致栈溢出。在JavaScript中，通常递归深度限制在几千层。对于极大的树，可能需要考虑迭代实现。
错误处理：本实现假设key是唯一的且一定能找到。如果key可能不存在，函数会返回false，但不会抛出错误。可以根据需求添加更健壮的错误处理机制。
灵活性：通过调整depth参数的判断条件，可以轻松修改哪些层级的节点应该被更新。例如，如果想更新所有层级（包括根节点），只需移除if (depth > 0)的条件即可。

通过这种递归与状态回溯结合的方法，我们能够优雅且高效地解决在树形结构中，根据特定节点更新其自身及其所有指定祖先节点属性的问题，同时灵活控制更新的范围。

以上就是递归更新树形结构中特定节点及其祖先的数值的详细内容，更多请关注php中文网其它相关文章！