理解树形数据结构与更新需求
在前端开发或数据管理中，我们经常会遇到需要处理层级关系的数据，例如文件系统、组织架构或商品分类。这些数据通常以树形结构表示，其中每个节点可能包含子节点。一个典型的javascript树形数据结构可能如下所示：
const data = [
{
key: "id1",
name: "Category 1",
curr: 0,
total: 0,
nodes: [ /* 子节点 */ ]
},
{
key: "id5",
name: "Category 2",
curr: 0,
total: 0,
nodes: [ /* 子节点 */ ]
},
{
key: "id8",
name: "Last One",
curr: 0,
total: 0,
nodes: []
}
];在这个结构中，每个对象都有一个唯一的 key、name、curr（当前值）、total（总值）以及一个 nodes 数组来存储其子节点。我们的核心需求是：给定一个特定的 key，找到对应的节点，将其 curr 值增加1，并且将这个增量操作沿着其父节点链向上一直传播，直到遇到最顶层的父节点（即 data 数组中的直接元素）为止，最顶层父节点的 curr 值不应被修改。
例如，如果我们要更新 key 为 "id4" 的节点，那么 "id4" 节点自身的 curr 值会增加，其父节点 "id2" 的 curr 值也会增加。然而，"id2" 的父节点 "id1" 的 curr 值则不应改变。
精确控制更新的递归策略：深度追踪与状态传播
为了解决上述问题，我们需要一种更精巧的递归策略，它能够：
- 识别目标节点并更新。
- 将更新事件向上级节点传播。
- 根据节点深度决定是否执行更新。
核心思想是让递归函数返回一个布尔值，指示其子树中是否发生了更新。如果子树中发生了更新，则当前节点也需要进行更新。同时，通过引入一个 depth 参数来跟踪当前节点的层级，我们可以精确地控制哪些层级的节点应该被更新。
立即学习“Java免费学习笔记（深入）”；
下面是实现这一策略的JavaScript函数：
/**
* 递归更新树形结构中指定节点及其祖先节点的curr值，但不更新顶层节点。
* @param {Array<Object>} nodes - 当前层级的节点数组。
* @param {string} targetKey - 需要查找并更新的节点的key。
* @param {number} depth - 当前递归的深度，根节点数组的深度为0。
* @returns {boolean} 如果当前节点或其子节点被更新，则返回true；否则返回false。
*/
function updateNodeAndAncestors(nodes, targetKey, depth = 0) {
// 遍历当前层级的每一个节点
for (let node of nodes) {
// 检查当前节点是否是目标节点，或者其子节点（通过递归调用）是否被更新
// node.nodes ?? [] 用于处理节点可能没有子节点的情况，确保递归调用安全
if (node.key === targetKey || updateNodeAndAncestors(node.nodes ?? [], targetKey, depth + 1)) {
// 如果当前节点不是最顶层节点（depth > 0），则增加其curr值
if (depth > 0) {
node.curr++;
}
// 返回true，表示当前节点或其子节点发生了更新，通知其父节点
return true;
}
}
// 如果遍历完所有节点都没有找到目标或子节点未更新，则返回false
return false;
}示例与解析
让我们使用初始数据和 updateNodeAndAncestors 函数来演示其工作原理。
初始数据：
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' 节点 updateNodeAndAncestors(data, 'id4'); console.log(JSON.stringify(data, null, 2));
输出结果：
[
{
"key": "id1",
"name": "Category 1",
"curr": 0, // 未更新，因为depth为0
"total": 0,
"nodes": [
{
"key": "id2",
"name": "Applications",
"curr": 21, // 更新了 (15 + 1)
"total": 30,
"nodes": [
{
"key": "id3",
"name": "Gaming",
"curr": 5,
"total": 10,
"nodes": []
},
{ 
