Quartz 4

查询该节点的所有父级节点

5 min read

查询树结构中节点的所有父级节点

功能说明

该函数用于在树形结构数据中，根据指定节点的ID查找该节点及其所有父级节点，并将它们以数组形式返回。这在处理导航菜单、组织架构图、文件目录等树形数据结构时非常有用。

参数说明

  • list：树形结构数据数组，每个节点至少包含 id 属性，子节点存储在 children 数组中
  • id：要查找的节点ID

返回值

  • 如果找到目标节点，返回一个数组，包含目标节点及其所有父级节点
  • 如果未找到目标节点，返回 undefined

实现代码

/**
 * 根据节点ID查找节点及其所有父级节点
 * @param {Array} list - 树形结构数据
 * @param {string|number} id - 要查找的节点ID
 * @returns {Array|undefined} - 返回包含目标节点及其所有父级节点的数组，未找到则返回undefined
 */
function getParentId(list, id) {
  // 遍历当前层级的节点
  for (let i in list) {
    // 如果找到目标节点，返回包含该节点的数组
    if (list[i].id == id) {
      return [list[i]]
    }
    // 如果当前节点有子节点，则递归查找
    if (list[i].children) {
      // 在子节点中查找目标节点
      let node = getParentId(list[i].children, id);
      // 如果在子节点中找到了目标节点
      if (node !== undefined) {
        // 将当前节点添加到结果数组中，形成一条从目标节点到当前节点的路径
        return node.concat(list[i])
      }
    }
  }
  // 如果遍历完当前层级仍未找到目标节点，返回undefined
  return undefined;
}

实现原理

该函数使用深度优先搜索（DFS）和递归的方式遍历树结构：

  1. 遍历当前层级的每个节点
  2. 如果当前节点的ID与目标ID匹配，则返回包含该节点的数组
  3. 如果当前节点有子节点，则递归查找子节点
  4. 如果在子节点中找到目标节点，则将当前节点添加到结果数组中，并返回
  5. 如果遍历完当前层级仍未找到目标节点，返回undefined

递归过程中，通过 concat() 方法将父节点不断添加到结果数组中，最终得到从目标节点到根节点的路径。

使用示例

// 示例树形数据
const treeData = [
  {
    id: '1',
    name: '父节点1',
    children: [
      {
        id: '1-1',
        name: '子节点1-1',
        children: [
          {
            id: '1-1-1',
            name: '子节点1-1-1'
          }
        ]
      },
      {
        id: '1-2',
        name: '子节点1-2'
      }
    ]
  },
  {
    id: '2',
    name: '父节点2',
    children: [
      {
        id: '2-1',
        name: '子节点2-1'
      }
    ]
  }
];
 
// 查找ID为'1-1-1'的节点及其所有父级节点
const result = getParentId(treeData, '1-1-1');
console.log(result);
/* 输出结果：
[
  { id: '1-1-1', name: '子节点1-1-1' },
  { id: '1-1', name: '子节点1-1', children: [...] },
  { id: '1', name: '父节点1', children: [...] }
]
*/

注意事项

  1. 返回的数组中，第一个元素是目标节点本身，最后一个元素是最顶层的父节点
  2. 如果树中有多个ID相同的节点，函数会返回第一个匹配到的节点路径
  3. 该函数适用于任何符合指定结构的树形数据，不限于特定的业务场景
  4. 为了提高性能，可以在找到目标节点后立即终止搜索

优化建议

  1. 对于大型树结构，可以考虑使用迭代而非递归的方式实现，以避免潜在的栈溢出问题
  2. 可以添加缓存机制，避免重复查询相同的节点
  3. 可以扩展函数，支持通过其他属性（而非仅ID）查找节点

Graph View

Backlinks