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  child.name === name)
    index++
  }
  return node
}

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