JS樹結(jié)構(gòu)操作:查找、遍歷、篩選、樹結(jié)構(gòu)和列表結(jié)構(gòu)相互轉(zhuǎn)換

今天在做欄目樹的處理的時候，對于樹結(jié)構(gòu)的操作有點暈，看了一篇文章，感覺講解的挺好的，測試了一下文中的代碼，感覺挺好用的，就記錄一下，原文地址：https://wintc.top/article/20，Github地址：https://github.com/Lushenggang/js-tree-tool

JS樹結(jié)構(gòu)相關(guān)操作

一、遍歷樹結(jié)構(gòu)

1. 樹結(jié)構(gòu)介紹

JS中樹結(jié)構(gòu)一般是類似于這樣的結(jié)構(gòu)：

let tree = [
  {
    id: '1',
    title: '節(jié)點1',
    children: [
      {
        id: '1-1',
        title: '節(jié)點1-1'
      },
      {
        id: '1-2',
        title: '節(jié)點1-2'
      }
    ]
  },
  {
    id: '2',
    title: '節(jié)點2',
    children: [
      {
        id: '2-1',
        title: '節(jié)點2-1'
      }
    ]
  }
]

為了更通用，可以用存儲了樹根節(jié)點的列表表示一個樹形結(jié)構(gòu)，每個節(jié)點的children屬性（如果有）是一顆子樹，如果沒有children屬性或者children長度為0，則表示該節(jié)點為葉子節(jié)點。

2. 樹結(jié)構(gòu)遍歷方法介紹

樹結(jié)構(gòu)的常用場景之一就是遍歷，而遍歷又分為廣度優(yōu)先遍歷、深度優(yōu)先遍歷。其中深度優(yōu)先遍歷是可遞歸的，而廣度優(yōu)先遍歷是非遞歸的，通常用循環(huán)來實現(xiàn)。深度優(yōu)先遍歷又分為先序遍歷、后序遍歷，二叉樹還有中序遍歷，實現(xiàn)方法可以是遞歸，也可以是循環(huán)。

JS遍歷樹結(jié)構(gòu)

廣度優(yōu)先和深度優(yōu)先的概念很簡單，區(qū)別如下：

  • 深度優(yōu)先，訪問完一顆子樹再去訪問后面的子樹，而訪問子樹的時候，先訪問根再訪問根的子樹，稱為先序遍歷；先訪問子樹再訪問根，稱為后序遍歷。
  • 廣度優(yōu)先，即訪問樹結(jié)構(gòu)的第n+1層前必須先訪問完第n層

3. 廣度優(yōu)先遍歷的實現(xiàn)

廣度優(yōu)先的思路是，維護一個隊列，隊列的初始值為樹結(jié)構(gòu)根節(jié)點組成的列表，重復(fù)執(zhí)行以下步驟直到隊列為空：

  • 取出隊列中的第一個元素，進行訪問相關(guān)操作，然后將其后代元素（如果有）全部追加到隊列最后。

下面是代碼實現(xiàn)，類似于數(shù)組的forEach遍歷，我們將數(shù)組的訪問操作交給調(diào)用者自定義，即一個回調(diào)函數(shù)：

// 廣度優(yōu)先
function treeForeach (tree, func) {
  let node, list = [...tree]
  while (node = list.shift()) {
    func(node)
    node.children && list.push(...node.children)
  }
}

很簡單吧，,
用上述數(shù)據(jù)測試一下看看：

treeForeach(tree, node => { console.log(node.title) })

輸出，可以看到第一層所有元素都在第二層元素前輸出：

> 節(jié)點1
> 節(jié)點2
> 節(jié)點1-1
> 節(jié)點1-2
> 節(jié)點2-1

4. 深度優(yōu)先遍歷的遞歸實現(xiàn)

先序遍歷，三五行代碼，太簡單，不過多描述了：

function treeForeach (tree, func) {
  tree.forEach(data => {
    func(data)
    data.children && treeForeach(data.children, func) // 遍歷子樹
  })
}

后序遍歷，與先序遍歷思想一致，代碼也及其相似，只不過調(diào)換一下節(jié)點遍歷和子樹遍歷的順序：

function treeForeach (tree, func) {
  tree.forEach(data => {
    data.children && treeForeach(data.children, func) // 遍歷子樹
    func(data)
  })
}

測試：

treeForeach(tree, node => { console.log(node.title) })

輸出：

// 先序遍歷
> 節(jié)點1
> 節(jié)點1-1
> 節(jié)點1-2
> 節(jié)點2
> 節(jié)點2-1

// 后序遍歷
> 節(jié)點1-1
> 節(jié)點1-2
> 節(jié)點1
> 節(jié)點2-1
> 節(jié)點2

5. 深度優(yōu)先循環(huán)實現(xiàn)

先序遍歷與廣度優(yōu)先循環(huán)實現(xiàn)類似，要維護一個隊列，不同的是子節(jié)點不追加到隊列最后，而是加到隊列最前面：

function treeForeach (tree, func) {
  let node, list = [...tree]
  while (node = list.shift()) {
    func(node)
    node.children && list.unshift(...node.children)
  }
}

后序遍歷就略微復(fù)雜一點，我們需要不斷將子樹擴展到根節(jié)點前面去，（艱難地）執(zhí)行列表遍歷，遍歷到某個節(jié)點如果它沒有子節(jié)點或者它的子節(jié)點已經(jīng)擴展到它前面了，則執(zhí)行訪問操作，否則擴展子節(jié)點到當前節(jié)點前面：

function treeForeach (tree, func) {
  let node, list = [...tree], i =  0
  while (node = list[i]) {
    let childCount = node.children ? node.children.length : 0
    if (!childCount || node.children[childCount - 1] === list[i - 1]) {
      func(node)
      i++
    } else {
      list.splice(i, 0, ...node.children)
    }
  }
}

二、列表和樹結(jié)構(gòu)相互轉(zhuǎn)換

1. 列表轉(zhuǎn)為樹

列表結(jié)構(gòu)通常是在節(jié)點信息中給定了父級元素的id，然后通過這個依賴關(guān)系將列表轉(zhuǎn)換為樹形結(jié)構(gòu)，列表結(jié)構(gòu)是類似于：

let list = [
  {
    id: '1',
    title: '節(jié)點1',
    parentId: '',
  },
  {
    id: '1-1',
    title: '節(jié)點1-1',
    parentId: '1'
  },
  {
    id: '1-2',
    title: '節(jié)點1-2',
      parentId: '1'
  },
  {
    id: '2',
    title: '節(jié)點2',
    parentId: ''
  },
  {
    id: '2-1',
    title: '節(jié)點2-1',
    parentId: '2'
  }
]

列表結(jié)構(gòu)轉(zhuǎn)為樹結(jié)構(gòu)，就是把所有非根節(jié)點放到對應(yīng)父節(jié)點的chilren數(shù)組中，然后把根節(jié)點提取出來：

function listToTree (list) {
  let info = list.reduce((map, node) => (map[node.id] = node, node.children = [], map), {})
  return list.filter(node => {
    info[node.parentId] && info[node.parentId].children.push(node)
    return !node.parentId
  })
}

這里首先通過info建立了id=>node的映射，因為對象取值的時間復(fù)雜度是O(1)，這樣在接下來的找尋父元素就不需要再去遍歷一次list了，因為遍歷尋找父元素時間復(fù)雜度是O(n)，并且是在循環(huán)中遍歷，則總體時間復(fù)雜度會變成O(n^2)，而上述實現(xiàn)的總體復(fù)雜度是O(n)。

2. 樹結(jié)構(gòu)轉(zhuǎn)列表結(jié)構(gòu)

有了遍歷樹結(jié)構(gòu)的經(jīng)驗，樹結(jié)構(gòu)轉(zhuǎn)為列表結(jié)構(gòu)就很簡單了。不過有時候，我們希望轉(zhuǎn)出來的列表按照目錄展示一樣的順序放到一個列表里的，并且包含層級信息。使用先序遍歷將樹結(jié)構(gòu)轉(zhuǎn)為列表結(jié)構(gòu)是合適的，直接上代碼:

//遞歸實現(xiàn)
function treeToList (tree, result = [], level = 0) {
  tree.forEach(node => {
    result.push(node)
    node.level = level + 1
    node.children && treeToList(node.children, result, level + 1)
  })
  return result
}

// 循環(huán)實現(xiàn)
function treeToList (tree) {
  let node, result = tree.map(node => (node.level = 1, node))
  for (let i = 0; i < result.length; i++) {
    if (!result[i].children) continue
    let list = result[i].children.map(node => (node.level = result[i].level + 1, node))
    result.splice(i+1, 0, ...list)
  }
  return result
}

三、樹結(jié)構(gòu)篩選

樹結(jié)構(gòu)過濾即保留某些符合條件的節(jié)點，剪裁掉其它節(jié)點。一個節(jié)點是否保留在過濾后的樹結(jié)構(gòu)中，取決于它以及后代節(jié)點中是否有符合條件的節(jié)點?？梢詡魅胍粋€函數(shù)描述符合條件的節(jié)點:

function treeFilter (tree, func) {
  // 使用map復(fù)制一下節(jié)點，避免修改到原樹
  return tree.map(node => ({ ...node })).filter(node => {
    node.children = node.children && treeFilter(node.children, func)
    return func(node) || (node.children && node.children.length)
  })
}

四、樹結(jié)構(gòu)查找

1. 查找節(jié)點

查找節(jié)點其實就是一個遍歷的過程，遍歷到滿足條件的節(jié)點則返回，遍歷完成未找到則返回null。類似數(shù)組的find方法，傳入一個函數(shù)用于判斷節(jié)點是否符合條件，代碼如下：

function treeFind (tree, func) {
  for (const data of tree) {
    if (func(data)) return data
    if (data.children) {
      const res = treeFind(data.children, func)
      if (res) return res
    }
  }
  return null
}

2. 查找節(jié)點路徑

略微復(fù)雜一點，因為不知道符合條件的節(jié)點在哪個子樹，要用到回溯法的思想。查找路徑要使用先序遍歷，維護一個隊列存儲路徑上每個節(jié)點的id，假設(shè)節(jié)點就在當前分支，如果當前分支查不到，則回溯。

function treeFindPath (tree, func, path = []) {
  if (!tree) return []
  for (const data of tree) {
    path.push(data.id)
    if (func(data)) return path
    if (data.children) {
      const findChildren = treeFindPath(data.children, func, path)
      if (findChildren.length) return findChildren
    }
    path.pop()
  }
  return []
}

用上面的樹結(jié)構(gòu)測試：

let result = treeFindPath(tree, node => node.id === '2-1')
console.log(result)

輸出：

["2","2-1"]

3. 查找多條節(jié)點路徑

思路與查找節(jié)點路徑相似，不過代碼卻更加簡單：

function treeFindPath (tree, func, path = [], result = []) {
  for (const data of tree) {
    path.push(data.id)
    func(data) && result.push([...path])
    data.children && treeFindPath(data.children, func, path, result)
    path.pop()
  }
  return result
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容