本篇文章為大家帶來了關於javascript的相關知識，主要介紹了JavaScript二元樹及各種遍歷演算法詳情，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小夥伴可以參考一下，希望對大家有幫助。
【相關推薦：javascript影片教學、web前端】
二元樹是每個節點最多只能有兩個子節點的樹，如下圖所示：
一個二元樹具有以下幾個特質：
i層的節點最有隻有2^(i-1)個;k，那二元樹最多有2^k-1節點；n0表示葉子節點的個數，n2是度為2的非葉子節點的個數，那麼兩者滿足關係n0 = n2 1。 如果在一個二元樹中，除了葉子節點，其餘的節點的每個度數都是2，則說明該二元樹是一個滿二叉樹，
如下圖所示：
#滿叉樹除了滿足普通二元樹特質，還具有如下幾個特質：
n層具有2^(n-1)個節點；k的滿二叉樹一定存在2^k-1個節點，葉子節點的個數為2^(k-1);n個節點的滿二元樹的深度為log_2^(n 1)。 如果一個二元樹去掉最後一次層是滿二叉樹，且最後一次的節點是依序從左到右分佈的，則這個二元樹是一個完全二元樹，
如下圖所示：
儲存二元樹的常見方式分為兩種，一種是使用陣列儲存，另一種使用鍊錶儲存。
使用陣列儲存二元樹，如果遇到完全二元樹，儲存順序從上到下，從左到右，如下圖所示：
如果是非完全二元樹，如下圖所示：
需要先將其轉換為完全二元樹，然後在進行存儲，如下圖所示：
#可以很明顯的看到存儲空間的浪費。
使用鍊錶儲存通常將二元樹中的分為3個部分，如下圖：
##這三個部分依序是左子樹的引用，該節點包含的數據，右子樹的引用，儲存方式如下圖所示：
以下演算法中遍歷用到的樹如下：
// 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二元樹的深度優先遍歷與樹的深度優先遍歷思路一致，思路如下：
實作程式碼如下： #
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)
/** 结果
A B D E C F H I G
*/實作想法如下：
和right依序入隊實作程式碼如下：
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)
/** 结果
A B C D E F G H I
*/二元樹的先序遍歷實作想法如下： #
如下图所示：
递归方式实现如下：
const bt = require('./tree')
function preorder(root) {
if (!root) return
console.log(root.val)
preorder(root.left)
preorder(root.right)
}
preorder(bt)
/** 结果
A B D E C F H I G
*/迭代方式实现如下：
// 非递归版
function preorder(root) {
if (!root) return
// 定义一个栈，用于存储数据
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)
/** 结果
A B D E C F H I G
*/二叉树的中序遍历实现思想如下：
如下图所示：
递归方式实现如下：
const bt = require('./tree')
// 递归版
function inorder(root) {
if (!root) return
inorder(root.left)
console.log(root.val)
inorder(root.right)
}
inorder(bt)
/** 结果
D B E A H F I C G
*/迭代方式实现如下：
// 非递归版
function inorder(root) {
if (!root) return
const stack = []
// 定义一个指针
let p = root
// 如果栈中有数据或者p不是null，则继续遍历
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)
/** 结果
D B E A H F I C G
*/二叉树的后序遍历实现思想如下：
如下图所示：
递归方式实现如下：
const bt = require('./tree')
// 递归版
function postorder(root) {
if (!root) return
postorder(root.left)
postorder(root.right)
console.log(root.val)
}
postorder(bt)
/** 结果
D E B H I F G C A
*/迭代方式实现如下：
// 非递归版
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)
/** 结果
D E B H I F G C A
*/【相关推荐：javascript视频教程、web前端】
以上是詳細介紹JavaScript二元樹及各種遍歷演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
