js树形结构查找节点

一、树形结构的定义与遍历

树形结构是一种具有层级关系的数据结构，由节点和边组成，每个节点最多有一个父节点和多个子节点，最上方的节点称为根节点，最下方的节点称为叶子节点。遍历树形结构是指按照一定的规则对所有节点进行访问。树形结构可以用对象或数组实现，其中对象方式会占用较小的内存，但是需要扁平化数据结构后才能进行遍历。

// 以对象方式实现一棵树
const tree = {
  name: 'root',
  children: [
    {
      name: 'child1',
      children: [
        { name: 'grandchild1' },
        { name: 'grandchild2' }
      ]
    },
    { name: 'child2' }
  ]
}

// 扁平化后的数组结构
const flatTree = [
  { name: 'root', parent: null },
  { name: 'child1', parent: 'root' },
  { name: 'grandchild1', parent: 'child1' },
  { name: 'grandchild2', parent: 'child1' },
  { name: 'child2', parent: 'root' }
]

// 遍历树形结构的方法
function traverseTree(node, callback) {
  callback(node)
  if (node.children && node.children.length) {
    node.children.forEach(child => {
      traverseTree(child, callback)
    })
  }
}

二、js查找节点的实现方法

查找树形结构的节点是指在整个树中寻找符合某一条件的节点，这里提供两种实现方法，一种基于深度优先搜索DFS，另一种基于广度优先搜索BFS。深度优先搜索先访问根节点，然后分别访问所有子节点，直到找到满足条件的节点，或访问到叶子节点为止。广度优先搜索按照层次逐层遍历所有节点，直到找到满足条件的节点为止。两种遍历方式都可以使用递归实现，也可以使用栈或队列来实现。

基于深度优先搜索DFS的实现

function findNodeByDFS(root, callback) {
  let result = null
  traverseTree(root, node => {
    if (callback(node)) {
      result = node
    }
  })
  return result
}

基于广度优先搜索BFS的实现

function findNodeByBFS(root, callback) {
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    if (callback(node)) {
      return node
    }
    if (node.children && node.children.length) {
      node.children.forEach(child => {
        queue.push(child)
      })
    }
  }
  return null
}

三、根据节点属性查找节点

在树形结构中，每个节点有自己的属性，例如名称、类型、值等，可以根据这些属性来查找符合条件的节点。下面以节点名称为例，给出基于DFS和BFS的两种实现方式。

根据节点名称查找节点

function findNodeByName(root, name) {
  return findNodeByDFS(root, node => node.name === name)
}

function findNodeByNameBFS(root, name) {
  return findNodeByBFS(root, node => node.name === name)
}

四、根据节点路径查找节点

在树形结构中，每个节点可以定义自己的唯一路径，例如文件系统中的绝对路径或者URL地址，可以根据这些路径来查找符合条件的节点。下面以节点路径为例，给出基于DFS和BFS的两种实现方式。

根据节点路径查找节点

function findNodeByPath(root, path) {
  const names = path.split('/')
  let index = 0
  let node = root
  while (node && index < names.length) {
    const name = names[index]
    node = node.children.find(child => child.name === name)
    index++
  }
  return node
}

function findNodeByPathBFS(root, path) {
  return findNodeByBFS(root, node => node.path === path)
}