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)文章
用jq提交時(shí)想同時(shí)按回車鍵可以提交，此時(shí)就不要用form,需要的朋友可以參考下2014-02-02
手把手教你uniapp和uview2.0實(shí)現(xiàn)表單校驗(yàn)實(shí)戰(zhàn)
表單提交對(duì)大家來(lái)說(shuō)應(yīng)該都不陌生,這是個(gè)很常見(jiàn)的功能,這篇文章主要給大家介紹了關(guān)于手把手教你uniapp和uview2.0實(shí)現(xiàn)表單校驗(yàn)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-05-05
Bootstrap中的fileinput 多圖片上傳及編輯功能
這篇文章主要介紹了Bootstrap中的fileinput 多圖片上傳及編輯功能的實(shí)現(xiàn),非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-09-09
這篇文章主要介紹了鼠標(biāo)滾軸控制文本框值的JS代碼，有需要的朋友可以參考一下2013-11-11
這篇文章介紹了JS中的幾種循環(huán)和跳出方式，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
connection reset by peer問(wèn)題總結(jié)及解決方案
這篇文章主要介紹了connection reset by peer問(wèn)題解決方案的相關(guān)資料,這里整理了一些常見(jiàn)問(wèn)題，及如何解決，需要的朋友可以參考下2016-10-10
在前端開(kāi)發(fā)中Webpack已經(jīng)成為構(gòu)建現(xiàn)代JavaScript應(yīng)用的必備工具,它負(fù)責(zé)模塊的打包和優(yōu)化,這篇文章主要介紹了前端webpack一些常用配置的作用,文中介紹的非常詳細(xì),需要的朋友可以參考下2025-04-04
javascript中的字符串替換及字符串分割在某些情況下還是比較實(shí)用的，下面有個(gè)不錯(cuò)的示例，感興趣的朋友可以參考下2013-12-12
這篇文章主要介紹了淺談jQuery中setInterval()方法，十分的簡(jiǎn)單實(shí)用，有需要的小伙伴可以參考下。2015-07-07
為什么用表單的方式就可以傳遞中文，而URL的方式就不行了呢？非得用URL傳值的方式才能解決問(wèn)題嗎？這里我想到了動(dòng)態(tài)表單，何不用它來(lái)解決呢2013-04-04