欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript二叉樹及各種遍歷算法詳情

 更新時間：2022年07月13日 17:21:29   作者：??一碗周?  
這篇文章主要介紹了JavaScript二叉樹及各種遍歷算法詳情，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下

前言:

上一篇文章中介紹了樹的概念、深度優(yōu)先遍歷和廣度優(yōu)先遍歷，這篇文章我們來學(xué)習(xí)一個特殊的樹——二叉樹。

什么是二叉樹

二叉樹是每個節(jié)點最多只能有兩個子節(jié)點的樹，如下圖所示：

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

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

滿二叉樹

如果在一個二叉樹中，除了葉子節(jié)點，其余的節(jié)點的每個度都是2，則說明該二叉樹是一個滿二叉樹，

如下圖所示：

滿二叉樹除了滿足普通二叉樹特質(zhì)，還具有如下幾個特質(zhì)：

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

完全二叉樹

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

如下圖所示：

二叉樹的存儲

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

數(shù)組存儲

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

如果是一個非完全二叉樹，如下圖所示：

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

可以很明顯的看到存儲空間的浪費。

鏈表存儲

使用鏈表存儲通常將二叉樹中的分為3個部分，如下圖：

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

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

以下算法中遍歷用到的樹如下：

// 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)先遍歷

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

  • 訪問根節(jié)點；
  • 訪問根節(jié)點的left
  • 訪問根節(jié)點的right
  • 重復(fù)執(zhí)行第二三步

實現(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)先遍歷

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

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

實現(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
 */

先序遍歷

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

  • 訪問根節(jié)點;
  • 對當(dāng)前節(jié)點的左子樹進(jìn)行先序遍歷；
  • 對當(dāng)前節(jié)點的右子樹進(jìn)行先序遍歷；

如下圖所示：

遞歸方式實現(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
*/

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

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

中序遍歷

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

  • 對當(dāng)前節(jié)點的左子樹進(jìn)行中序遍歷；
  • 訪問根節(jié)點;
  • 對當(dāng)前節(jié)點的右子樹進(jìn)行中序遍歷；

如下圖所示：

遞歸方式實現(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
*/

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

// 非遞歸版
function inorder(root) {
  if (!root) return
  const stack = []
  // 定義一個指針
  let p = root
  // 如果棧中有數(shù)據(jù)或者p不是null，則繼續(xù)遍歷
  while (stack.length || p) {
    // 如果p存在則一致將p入棧并移動指針
    while (p) {
      // 將 p 入棧，并以移動指針
      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
*/

后序遍歷

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

  • 對當(dāng)前節(jié)點的左子樹進(jìn)行后序遍歷；
  • 對當(dāng)前節(jié)點的右子樹進(jìn)行后序遍歷；
  • 訪問根節(jié)點;

如下圖所示：

遞歸方式實現(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
*/

迭代方式實現(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二叉樹及各種遍歷算法詳情的文章就介紹到這了,更多相關(guān)JavaScript二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • 微信小程序?qū)崿F(xiàn)多層級復(fù)選框菜單

    微信小程序?qū)崿F(xiàn)多層級復(fù)選框菜單

    這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)多層級復(fù)選框菜單，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-07-07
  • JavaScript樹形結(jié)構(gòu)數(shù)組處理之遞歸問題

    JavaScript樹形結(jié)構(gòu)數(shù)組處理之遞歸問題

    這篇文章主要介紹了JavaScript樹形結(jié)構(gòu)數(shù)組處理之遞歸問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2023-06-06
  • webpack2.0搭建前端項目的教程詳解

    webpack2.0搭建前端項目的教程詳解

    這篇文章主要給大家介紹了關(guān)于webpack2.0搭建前端項目的相關(guān)資料，文中介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用webpack2.0具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。
    2017-04-04
  • JavaScript實現(xiàn)將xml轉(zhuǎn)換成html table表格的方法

    JavaScript實現(xiàn)將xml轉(zhuǎn)換成html table表格的方法

    這篇文章主要介紹了JavaScript實現(xiàn)將xml轉(zhuǎn)換成html table表格的方法,實例分析了javascript操作XML文件與table表格的技巧,非常具有實用價值,需要的朋友可以參考下
    2015-04-04
  • 日常收集整理的JavaScript常用函數(shù)方法

    日常收集整理的JavaScript常用函數(shù)方法

    本文是小編在平時項目中收集整理的javascript常用函數(shù)方法，特別是javascript方法經(jīng)常會用到，對javascript函數(shù)方法相關(guān)知識感興趣的朋友一起學(xué)習(xí)吧
    2015-12-12
  • JavaScript實現(xiàn)俄羅斯方塊游戲過程分析及源碼分享

    JavaScript實現(xiàn)俄羅斯方塊游戲過程分析及源碼分享

    這篇文章主要介紹了JavaScript實現(xiàn)俄羅斯方塊游戲過程分析及源碼分享,本文分解了游戲規(guī)則、實現(xiàn)過程、難點分析及實現(xiàn)源碼,需要的朋友可以參考下
    2015-03-03
  • javascript:void(0)用法及常見問題分析

    javascript:void(0)用法及常見問題分析

    javascript:void(0) 在某些情況下會有瀏覽器不兼容的bug。下面我們先來看下javascript:void(0) 的基礎(chǔ)介紹及用法，然后再來看使用它會出現(xiàn)什么問題，該怎么解決，感興趣的朋友跟隨小編一起看看吧
    2023-10-10
  • javascript鼠標(biāo)右鍵菜單自定義效果

    javascript鼠標(biāo)右鍵菜單自定義效果

    設(shè)計專屬于自己的右鍵菜單，添加自己需要的快捷方式，本文就為大家分享自定義javascript鼠標(biāo)右鍵菜單的實現(xiàn)方法，感興趣的小伙伴們可以參考一下
    2016-02-02
  • 不得不知的ES6小技巧

    不得不知的ES6小技巧

    ES6出來已經(jīng)有好幾年了，同時很多新特性可以被巧妙地運用在項目中。我想要列下其中一些，希望它們對你有用
    2018-07-07
  • js獲取當(dāng)前頁的URL與window.location.href簡單方法

    js獲取當(dāng)前頁的URL與window.location.href簡單方法

    下面小編就為大家?guī)硪黄猨s獲取當(dāng)前頁的URL與window.location.href簡單方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2017-02-02

最新評論