当前位置：首页 > 文章列表 > 文章 > 前端 > 树结构键值向上更新父节点的递归实现

树结构键值向上更新父节点的递归实现

2025-10-06 13:09:33 0浏览收藏

在文章实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《树结构中键值向上更新父节点的递归方法》，聊聊，希望可以帮助到正在努力赚钱的你。

树形结构中基于键值向上更新父节点属性的递归实现

本文详细阐述了如何在嵌套对象数组（树形结构）中，根据指定键值查找目标节点，并将其 available 属性值递增，同时将此递增操作逐级向上应用至所有父节点直至根节点的实现方法。通过递归遍历与布尔值回溯机制，高效地解决了树形数据中特定节点及其祖先属性的同步更新问题。

1. 问题描述与数据结构

在处理复杂的层级数据时，我们经常会遇到需要根据某个特定节点的标识（如 key）来更新其自身及其所有祖先节点属性的需求。例如，在一个表示分类或分组的树形结构中，当一个子项的“可用数量”发生变化时，其所有上级分类或分组的“可用数量”也应相应更新。

考虑以下这种嵌套的 JavaScript 对象数组结构，它模拟了一个树形数据：

const data = [
  {
    "key": "group1",
    "name": "groupname1",
    "total": 65,
    "available": 34,
    "children": [
      {
        "key": "cat1",
        "name": "category1",
        "total": 5,
        "available": 2,
        "children": []
      },
      {
        "key": "cat2",
        "name": "category2",
        "total": 60,
        "available": 32,
        "children": [
          {
            "key": "cat3",
            "name": "category3",
            "total": 15,
            "available": 12,
            "children": []
          },
          {
            "key": "cat6",
            "name": "category6",
            "total": 55,
            "available": 20,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "key": "group2",
    "name": "groupname2",
    "total": 75,
    "available": 47,
    "children": [
      {
        "key": "cat4",
        "name": "category4",
        "total": 25,
        "available": 22,
        "children": []
      },
      {
        "key": "cat5",
        "name": "category5",
        "total": 50,
        "available": 25,
        "children": []
      }
    ]
  }
];

在这个结构中：

每个对象代表一个节点，包含 key、name、total、available 等属性。
key 属性在整个树中是唯一的，用于唯一标识一个节点。
children 属性是一个数组，包含当前节点的子节点。我们的目标是，给定一个 key（例如 "cat3"），找到对应的节点，将其 available 值递增 1，并且其所有父节点（cat2 和 group1）的 available 值也递增 1。

2. 期望输出示例

如果我们调用一个函数 incrementRecursively(data, "cat3")，期望的输出如下：

[
  {
    "key": "group1",
    "name": "groupname1",
    "total": 65,
    "available": 35, // 从 34 变为 35
    "children": [
      {
        "key": "cat1",
        "name": "category1",
        "total": 5,
        "available": 2,
        "children": []
      },
      {
        "key": "cat2",
        "name": "category2",
        "total": 60,
        "available": 33, // 从 32 变为 33
        "children": [
          {
            "key": "cat3",
            "name": "category3",
            "total": 15,
            "available": 13, // 从 12 变为 13
            "children": []
          },
          {
            "key": "cat6",
            "name": "category6",
            "total": 55,
            "available": 20,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "key": "group2",
    "name": "groupname2",
    "total": 75,
    "available": 47,
    "children": [
      {
        "key": "cat4",
        "name": "category4",
        "total": 25,
        "available": 22,
        "children": []
      },
      {
        "key": "cat5",
        "name": "category5",
        "total": 50,
        "available": 25,
        "children": []
      }
    ]
  }
]

可以看到，cat3、cat2 和 group1 的 available 值都增加了 1。

3. 解决方案：递归遍历与布尔值回溯

要实现这种“向上”更新的效果，最直观且高效的方法是使用递归遍历。递归函数在向下遍历树时查找目标 key，一旦找到，它会返回一个指示“已找到并更新”的信号（例如 true）。当递归调用返回 true 时，其父节点就知道自己的某个子节点发生了更新，从而也执行自己的更新操作，并将这个信号继续向上传递。

3.1 核心逻辑

递归函数签名: 定义一个函数 increment(node, key)，它接收当前节点 node 和目标 key 作为参数。
查找条件: 在每个节点内部，我们需要判断两种情况：
- 当前节点的 key 是否与目标 key 匹配 (node.key === key)。
- 当前节点的任何一个子节点是否匹配或包含匹配的子节点（通过递归调用 node.children.some(c => increment(c, key)) 实现）。
更新与回溯: 如果上述任一条件为真（即当前节点是目标节点，或者它的某个子孙节点是目标节点），则表示需要对当前节点的 available 属性进行递增。同时，函数需要返回 true，以便其父节点能够感知到这次更新。
短路逻辑: 利用 JavaScript 的逻辑运算符 || 和 && 可以优雅地实现这一逻辑。
- (node.key === key || node.children.some(c => increment(c, key)))：这部分判断当前节点是否匹配或其子节点中是否存在匹配。如果匹配，整个表达式为 true。
- && (node.available++, true)：如果前一部分为 true，则执行这部分。node.available++ 会递增 available 属性，然后 true 被返回。这种写法确保了只有在找到匹配路径时才进行递增，并且始终返回 true 来向上传播信号。

3.2 示例代码

const data = [
  {
    "key": "group1",
    "name": "groupname1",
    "total": 65,
    "available": 34,
    "children": [
      {
        "key": "cat1",
        "name": "category1",
        "total": 5,
        "available": 2,
        "children": []
      },
      {
        "key": "cat2",
        "name": "category2",
        "total": 60,
        "available": 32,
        "children": [
          {
            "key": "cat3",
            "name": "category3",
            "total": 15,
            "available": 12,
            "children": []
          },
          {
            "key": "cat6",
            "name": "category6",
            "total": 55,
            "available": 20,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "key": "group2",
    "name": "groupname2",
    "total": 75,
    "available": 47,
    "children": [
      {
        "key": "cat4",
        "name": "category4",
        "total": 25,
        "available": 22,
        "children": []
      },
      {
        "key": "cat5",
        "name": "category5",
        "total": 50,
        "available": 25,
        "children": []
      }
    ]
  }
];

/**
 * 递归函数，用于在树形结构中查找并更新指定 key 的节点及其所有祖先节点的 available 属性。
 * @param {Object} node - 当前处理的节点对象。
 * @param {string} targetKey - 要查找的目标 key。
 * @returns {boolean} - 如果当前节点或其子孙节点匹配 targetKey，则返回 true；否则返回 false。
 */
function increment(node, targetKey) {
  // 判断条件：当前节点 key 匹配 targetKey，
  // 或者当前节点的任意一个子节点（通过递归调用）匹配 targetKey
  const isMatchOrHasMatchingChild = 
    node.key === targetKey || 
    node.children.some(child => increment(child, targetKey));

  // 如果匹配或其子孙有匹配，则递增当前节点的 available 属性，并返回 true
  // (node.available++, true) 是一种常见的 JavaScript 技巧，
  // 确保递增操作执行后，整个表达式的结果是 true。
  if (isMatchOrHasMatchingChild) {
    node.available++;
    return true;
  }
  // 如果当前节点及其子孙都没有匹配，则返回 false
  return false;
}

// 对顶层数组中的每个根节点调用 increment 函数
// 这样可以确保无论目标 key 在哪个根节点下，都能被正确处理
data.forEach(rootNode => increment(rootNode, 'cat3'));

console.log("更新后的数据：", JSON.stringify(data, null, 2));

3.3 代码解析

increment(node, targetKey): 这是递归函数的核心。
node.key === targetKey: 检查当前节点是否就是我们正在寻找的目标节点。
node.children.some(child => increment(child, targetKey)): 这一部分是递归的关键。
- node.children.some(...) 会遍历当前节点的所有子节点。
- 对于每个子节点 child，它会递归调用 increment(child, targetKey)。
- 如果 increment(child, targetKey) 返回 true（意味着这个子节点或其子孙节点找到了目标 key 并进行了更新），那么 some 方法会立即停止遍历并返回 true。
isMatchOrHasMatchingChild: 这个布尔变量结合了当前节点匹配和子节点匹配两种情况。
if (isMatchOrHasMatchingChild) { node.available++; return true; }: 如果 isMatchOrHasMatchingChild 为 true，说明当前节点是目标路径的一部分（要么是目标本身，要么是目标的一个祖先）。因此，当前节点的 available 属性递增，并且函数返回 true，将这个“已更新”的信号传递给它的父节点。
return false;: 如果当前节点及其所有子孙节点都没有匹配到 targetKey，则返回 false。
data.forEach(rootNode => increment(rootNode, 'cat3')): 由于我们的 data 是一个根节点数组，我们需要对每个根节点分别调用 increment 函数，以确保整个树结构都被搜索到。

4. 注意事项与扩展

原地修改 (In-place Modification): 上述解决方案直接修改了原始 data 数组。在某些应用场景中，为了保持数据的不可变性，你可能需要创建一个新的树结构并返回，而不是修改原有的。这可以通过在递归函数中复制节点和子节点来实现，例如使用扩展运算符 { ...node, available: node.available + 1, children: newChildren }。
性能: 对于非常深的树或频繁的更新操作，递归的深度可能会导致堆栈溢出。在 JavaScript 中，默认的递归深度限制通常在几千层。对于极深的大型树，可能需要考虑迭代式的解决方案（如使用栈模拟递归）。然而，对于大多数常见的树形结构，递归方案简洁且高效。
Key 的唯一性: 本方案依赖于 key 在整个树中的唯一性。如果 key 不唯一，所有匹配的节点及其祖先都会被更新。如果只需要更新第一个找到的匹配，则需要在找到后增加一个退出机制。
错误处理: 如果 targetKey 不存在于树中，available 属性将不会有任何变化，函数最终会返回 false。可以根据需要添加额外的逻辑来处理这种情况，例如返回一个布尔值指示是否找到了目标 key。