JavaScript二叉樹(shù)及各種遍歷算法詳情
前言:
上一篇文章中介紹了樹(shù)的概念、深度優(yōu)先遍歷和廣度優(yōu)先遍歷，這篇文章我們來(lái)學(xué)習(xí)一個(gè)特殊的樹(shù)——二叉樹(shù)。
什么是二叉樹(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ù)，那么兩者滿足關(guān)系n0 = n2 + 1。
滿二叉樹(shù)
如果在一個(gè)二叉樹(shù)中，除了葉子節(jié)點(diǎn)，其余的節(jié)點(diǎn)的每個(gè)度都是2，則說(shuō)明該二叉樹(shù)是一個(gè)滿二叉樹(shù)，
如下圖所示：
滿二叉樹(shù)除了滿足普通二叉樹(shù)特質(zhì)，還具有如下幾個(gè)特質(zhì)：
- 滿二叉樹(shù)的的第
n層具有2^(n-1)個(gè)節(jié)點(diǎn)； - 深度為
k的滿二叉樹(shù)一定存在2^k-1個(gè)節(jié)點(diǎn)，葉子節(jié)點(diǎn)的個(gè)數(shù)為2^(k-1)； - 具有
n個(gè)節(jié)點(diǎn)的滿二叉樹(shù)的深度為log_2^(n+1)。
完全二叉樹(shù)
如果一個(gè)二叉樹(shù)去掉最后一次層是滿二叉樹(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)先遍歷思路一致，思路如下：
- 訪問(wèn)根節(jié)點(diǎn)；
- 訪問(wèn)根節(jié)點(diǎn)的
left - 訪問(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ì)并訪問(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)思想如下：
- 訪問(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)行中序遍歷；
- 訪問(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)行后序遍歷；
- 訪問(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)文章希望大家以后多多支持腳本之家！
相關(guān)文章
微信小程序?qū)崿F(xiàn)多層級(jí)復(fù)選框菜單
這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)多層級(jí)復(fù)選框菜單，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-07-07
JavaScript樹(shù)形結(jié)構(gòu)數(shù)組處理之遞歸問(wèn)題
這篇文章主要介紹了JavaScript樹(shù)形結(jié)構(gòu)數(shù)組處理之遞歸問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
這篇文章主要給大家介紹了關(guān)于webpack2.0搭建前端項(xiàng)目的相關(guān)資料，文中介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用webpack2.0具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起看看吧。2017-04-04
JavaScript實(shí)現(xiàn)將xml轉(zhuǎn)換成html table表格的方法
這篇文章主要介紹了JavaScript實(shí)現(xiàn)將xml轉(zhuǎn)換成html table表格的方法,實(shí)例分析了javascript操作XML文件與table表格的技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-04-04
本文是小編在平時(shí)項(xiàng)目中收集整理的javascript常用函數(shù)方法，特別是javascript方法經(jīng)常會(huì)用到，對(duì)javascript函數(shù)方法相關(guān)知識(shí)感興趣的朋友一起學(xué)習(xí)吧2015-12-12
JavaScript實(shí)現(xiàn)俄羅斯方塊游戲過(guò)程分析及源碼分享
這篇文章主要介紹了JavaScript實(shí)現(xiàn)俄羅斯方塊游戲過(guò)程分析及源碼分享,本文分解了游戲規(guī)則、實(shí)現(xiàn)過(guò)程、難點(diǎn)分析及實(shí)現(xiàn)源碼,需要的朋友可以參考下2015-03-03
javascript:void(0)用法及常見(jiàn)問(wèn)題分析
javascript:void(0) 在某些情況下會(huì)有瀏覽器不兼容的bug。下面我們先來(lái)看下javascript:void(0) 的基礎(chǔ)介紹及用法，然后再來(lái)看使用它會(huì)出現(xiàn)什么問(wèn)題，該怎么解決，感興趣的朋友跟隨小編一起看看吧2023-10-10
設(shè)計(jì)專屬于自己的右鍵菜單，添加自己需要的快捷方式，本文就為大家分享自定義javascript鼠標(biāo)右鍵菜單的實(shí)現(xiàn)方法，感興趣的小伙伴們可以參考一下2016-02-02
ES6出來(lái)已經(jīng)有好幾年了，同時(shí)很多新特性可以被巧妙地運(yùn)用在項(xiàng)目中。我想要列下其中一些，希望它們對(duì)你有用2018-07-07
js獲取當(dāng)前頁(yè)的URL與window.location.href簡(jiǎn)單方法
下面小編就為大家?guī)?lái)一篇js獲取當(dāng)前頁(yè)的URL與window.location.href簡(jiǎn)單方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-02-02