腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

JavaScript二叉樹(shù)及各種遍歷算法詳情

更新時(shí)間：2022年07月13日 17:21:29 作者：??一碗周?

這篇文章主要介紹了JavaScript二叉樹(shù)及各種遍歷算法詳情，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下

什么是二叉樹(shù)

二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的樹(shù)，如下圖所示：

一個(gè)二叉樹(shù)具有以下幾個(gè)特質(zhì)：

第i層的節(jié)點(diǎn)最有只有2^(i-1)個(gè)；
如果這顆二叉樹(shù)的深度為k，那二叉樹(shù)最多有2^k-1個(gè)節(jié)點(diǎn)；
在一個(gè)非空的二叉樹(shù)中，若使用n0表示葉子節(jié)點(diǎn)的個(gè)數(shù)，n2是度為2的非葉子節(jié)點(diǎn)的個(gè)數(shù)，那么兩者滿(mǎn)足關(guān)系n0 = n2 + 1。

滿(mǎn)二叉樹(shù)

如果在一個(gè)二叉樹(shù)中，除了葉子節(jié)點(diǎn)，其余的節(jié)點(diǎn)的每個(gè)度都是2，則說(shuō)明該二叉樹(shù)是一個(gè)滿(mǎn)二叉樹(shù)，

如下圖所示：

滿(mǎn)二叉樹(shù)除了滿(mǎn)足普通二叉樹(shù)特質(zhì)，還具有如下幾個(gè)特質(zhì)：

滿(mǎn)二叉樹(shù)的的第n層具有2^(n-1)個(gè)節(jié)點(diǎn)；
深度為k的滿(mǎn)二叉樹(shù)一定存在2^k-1個(gè)節(jié)點(diǎn)，葉子節(jié)點(diǎn)的個(gè)數(shù)為2^(k-1)；
具有n個(gè)節(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度為log_2^(n+1)。

完全二叉樹(shù)

如果一個(gè)二叉樹(shù)去掉最后一次層是滿(mǎn)二叉樹(shù)，且最后一次的節(jié)點(diǎn)是依次從左到右分布的，則這個(gè)二叉樹(shù)是一個(gè)完全二叉樹(shù)，

如下圖所示：

二叉樹(shù)的存儲(chǔ)

存儲(chǔ)二叉樹(shù)的常見(jiàn)方式分為兩種，一種是使用數(shù)組存儲(chǔ)，另一種使用鏈表存儲(chǔ)。

數(shù)組存儲(chǔ)

使用數(shù)組存儲(chǔ)二叉樹(shù)，如果遇到完全二叉樹(shù)，存儲(chǔ)順序從上到下，從左到右，如下圖所示：

如果是一個(gè)非完全二叉樹(shù)，如下圖所示：

需要先將其轉(zhuǎn)換為完全二叉樹(shù)，然后在進(jìn)行存儲(chǔ)，如下圖所示：

可以很明顯的看到存儲(chǔ)空間的浪費(fèi)。

鏈表存儲(chǔ)

使用鏈表存儲(chǔ)通常將二叉樹(shù)中的分為3個(gè)部分，如下圖：

這三個(gè)部分依次是左子樹(shù)的引用，該節(jié)點(diǎn)包含的數(shù)據(jù)，右子樹(shù)的引用，存儲(chǔ)方式如下圖所示：

與二叉樹(shù)相關(guān)的算法

以下算法中遍歷用到的樹(shù)如下：

// tree.js
const bt = {
  val: 'A',
  left: {
    val: 'B',
    left: { val: 'D', left: null, right: null },
    right: { val: 'E', left: null, right: null },
  },
  right: {
    val: 'C',
    left: {
      val: 'F',
      left: { val: 'H', left: null, right: null },
      right: { val: 'I', left: null, right: null },
    },
    right: { val: 'G', left: null, right: null },
  },
}
module.exports = bt

深度優(yōu)先遍歷

二叉樹(shù)的深度優(yōu)先遍歷與樹(shù)的深度優(yōu)先遍歷思路一致，思路如下：

訪(fǎng)問(wèn)根節(jié)點(diǎn)；
訪(fǎng)問(wèn)根節(jié)點(diǎn)的left
訪(fǎng)問(wèn)根節(jié)點(diǎn)的right
重復(fù)執(zhí)行第二三步

實(shí)現(xiàn)代碼如下：

const bt = {
  val: 'A',
  left: {
    val: 'B',
    left: { val: 'D', left: null, right: null },
    right: { val: 'E', left: null, right: null },
  },
  right: {
    val: 'C',
    left: {
      val: 'F',
      left: { val: 'H', left: null, right: null },
      right: { val: 'I', left: null, right: null },
    },
    right: { val: 'G', left: null, right: null },
  },
}

function dfs(root) {
  if (!root) return
  console.log(root.val)
  root.left && dfs(root.left)
  root.right && dfs(root.right) 
}
dfs(bt)
/** 結(jié)果
A B D E C F H I G
*/

廣度優(yōu)先遍歷

實(shí)現(xiàn)思路如下：

創(chuàng)建隊(duì)列，把根節(jié)點(diǎn)入隊(duì)
把對(duì)頭出隊(duì)并訪(fǎng)問(wèn)
把隊(duì)頭的left和right依次入隊(duì)
重復(fù)執(zhí)行2、3步，直到隊(duì)列為空

實(shí)現(xiàn)代碼如下：

function bfs(root) {
  if (!root) return
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    console.log(node.val)
    node.left && queue.push(node.left)
    node.right && queue.push(node.right)
  }
}
bfs(bt)
/** 結(jié)果
A B C D E F G H I
 */

先序遍歷

二叉樹(shù)的先序遍歷實(shí)現(xiàn)思想如下：

訪(fǎng)問(wèn)根節(jié)點(diǎn);
對(duì)當(dāng)前節(jié)點(diǎn)的左子樹(shù)進(jìn)行先序遍歷；
對(duì)當(dāng)前節(jié)點(diǎn)的右子樹(shù)進(jìn)行先序遍歷；

如下圖所示：

遞歸方式實(shí)現(xiàn)如下：

const bt = require('./tree')

function preorder(root) {
  if (!root) return
  console.log(root.val)
  preorder(root.left)
  preorder(root.right)
}
preorder(bt)
/** 結(jié)果
A B D E C F H I G
*/

迭代方式實(shí)現(xiàn)如下：

// 非遞歸版
function preorder(root) {
  if (!root) return
  // 定義一個(gè)棧，用于存儲(chǔ)數(shù)據(jù)
  const stack = [root]
  while (stack.length) {
    const node = stack.pop()
    console.log(node.val)
    /* 由于棧存在先入后出的特性，所以需要先入右子樹(shù)才能保證先出左子樹(shù) */
    node.right && stack.push(node.right)
    node.left && stack.push(node.left)
  }
}
preorder(bt)
/** 結(jié)果
A B D E C F H I G
*/

中序遍歷

二叉樹(shù)的中序遍歷實(shí)現(xiàn)思想如下：

對(duì)當(dāng)前節(jié)點(diǎn)的左子樹(shù)進(jìn)行中序遍歷；
訪(fǎng)問(wèn)根節(jié)點(diǎn);
對(duì)當(dāng)前節(jié)點(diǎn)的右子樹(shù)進(jìn)行中序遍歷；

如下圖所示：

遞歸方式實(shí)現(xiàn)如下：

const bt = require('./tree')

// 遞歸版
function inorder(root) {
  if (!root) return
  inorder(root.left)
  console.log(root.val)
  inorder(root.right)
}
inorder(bt)

/** 結(jié)果
D B E A H F I C G
*/

迭代方式實(shí)現(xiàn)如下：

// 非遞歸版
function inorder(root) {
  if (!root) return
  const stack = []
  // 定義一個(gè)指針
  let p = root
  // 如果棧中有數(shù)據(jù)或者p不是null，則繼續(xù)遍歷
  while (stack.length || p) {
    // 如果p存在則一致將p入棧并移動(dòng)指針
    while (p) {
      // 將 p 入棧，并以移動(dòng)指針
      stack.push(p)
      p = p.left
    }

    const node = stack.pop()
    console.log(node.val)
    p = node.right
  }
}
inorder(bt)
/** 結(jié)果
D B E A H F I C G
*/

后序遍歷

二叉樹(shù)的后序遍歷實(shí)現(xiàn)思想如下：

對(duì)當(dāng)前節(jié)點(diǎn)的左子樹(shù)進(jìn)行后序遍歷；
對(duì)當(dāng)前節(jié)點(diǎn)的右子樹(shù)進(jìn)行后序遍歷；
訪(fǎng)問(wèn)根節(jié)點(diǎn);

如下圖所示：

遞歸方式實(shí)現(xiàn)如下：

const bt = require('./tree')

// 遞歸版
function postorder(root) {
  if (!root) return
  postorder(root.left)
  postorder(root.right)
  console.log(root.val)
}
postorder(bt)
/** 結(jié)果
D E B H I F G C A
*/

迭代方式實(shí)現(xiàn)如下：

// 非遞歸版
function postorder(root) {
  if (!root) return
  const outputStack = []
  const stack = [root]
  while (stack.length) {
    const node = stack.pop()
    outputStack.push(node)
    // 這里先入left需要保證left后出，在stack中后出，就是在outputStack棧中先出
    node.left && stack.push(node.left)
    node.right && stack.push(node.right)
  }
  while (outputStack.length) {
    const node = outputStack.pop()
    console.log(node.val)
  }
}
postorder(bt)
/** 結(jié)果
D E B H I F G C A
*/

到此這篇關(guān)于JavaScript二叉樹(shù)及各種遍歷算法詳情的文章就介紹到這了,更多相關(guān)JavaScript二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: