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

本教程详细介绍了如何在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值。

核心思路如下：

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

1. updateNodeAndParentsRecursively(nodes, key, depth = 0)：

   

   SEO GPT

   免费的白帽SEO，PPC和网站经销商平台

   17

   查看详情
   

   • nodes: 当前正在处理的节点数组。在初始调用时，它是整个data数组。
   • key: 我们要查找并更新的节点的key。
   • depth = 0: 这是一个可选参数，用于跟踪当前节点在树中的深度。顶层节点（data数组的直接子项）的深度为0，它们的子节点深度为1，依此类推。这个参数是控制“不更新根节点”的关键。

2. for (let node of nodes)：

   • 遍历当前nodes数组中的每一个节点。

3. 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，说明在当前节点或其子树中找到了目标节点。

4. if (depth > 0) { node.curr++; }：

   • 这是实现“不更新根节点”的关键逻辑。
   • 如果depth大于0，说明当前节点不是最顶层的节点（即它有父节点），此时才递增其curr值。
   • 如果depth为0，说明当前节点是最顶层节点，即使其子树中发生了更新，它的curr值也不会被修改。

5. return true;：

   • 如果当前节点或其子树中发生了更新，函数立即返回true。这个true会向上级调用传递，告知其父节点也需要考虑更新。

6. 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)的条件即可。

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