JavaScript二叉搜索樹構(gòu)建操作詳解
更新時間：2022年07月13日 16:29:25 作者：??一碗周???
這篇文章主要介紹了JavaScript二叉搜索樹構(gòu)建操作詳解，文章圍繞主題展開二叉搜索樹的性質(zhì)以及二叉搜索樹的構(gòu)建、查找和刪除等內(nèi)容，需要的小伙伴可以參考一下
前言
前面我們介紹了二叉樹這個數(shù)據(jù)結(jié)構(gòu)以及二叉樹的遍歷算法，這篇文章我們來學習一下一個特殊的二叉樹——二叉搜索樹（BST Binary Search Tree），也叫二叉排序樹、二叉查找樹。
什么是二叉搜索樹
二叉搜索樹首先它是一棵二叉樹，而且還滿足下面這些特質(zhì)：
- 對于任何一個非空節(jié)點來說，它左子樹上的值必須小于當前值；
- 對于任何一個非空節(jié)點來說，它右子樹上的值必須大于當前值；
- 任何一顆子樹滿足上面的條件；
如下圖所示：
上圖就是一顆二叉搜索樹，我們就拿根節(jié)點來說，根節(jié)點的值71，它的左子樹的值分別是22、35、46、53和66，這幾個都是滿足左子樹小于當前值；它的右子樹的值分別是78、87和98，這幾個值是滿足右子樹大于當前值的；以此類推，所以上圖就是一棵二叉搜索樹。
根據(jù)二叉搜索樹的特質(zhì)，我們還能得到以下結(jié)論：
- 二叉搜索樹的任何一個節(jié)點的左子樹、右子樹都是一顆二叉搜索樹；
- 二叉搜索樹的最小的節(jié)點是整顆樹的最左下角的葉子節(jié)點；
- 二叉搜索樹的最大的節(jié)點是整棵樹的最右下角的葉子節(jié)點；
構(gòu)建一顆二叉搜索樹
我們現(xiàn)在使用JavaScript來構(gòu)建一顆二叉搜索樹，要知道一顆二叉搜索樹也是由一個一個節(jié)點組成，這里我們通過class創(chuàng)建一個節(jié)點類，
示例代碼如下：
class BinarySearchTree {
constructor() {
// 初始化根節(jié)點
this.root = null
}
// 創(chuàng)建一個節(jié)點
Node(val) {
return {
left: null, // 左子樹
right: null, // 右子樹
parent: null, // 父節(jié)點
val,
}
}
}這里一個節(jié)點由四部分組成，分別是指向左子樹的指針、指向右子樹的指針、指向父節(jié)點的指針以及當前值。
二叉搜索樹的操作
關(guān)于二叉樹的遍歷操作我們在上一篇文章中已經(jīng)介紹了，這里不在重復，這里主要介紹如下操作：
- 插入操作
- 查找操作
- 刪除操作
向二叉搜索樹中插入數(shù)據(jù)
向一個二叉搜索樹插入數(shù)據(jù)實現(xiàn)思路如下：
- 判斷
root是否為空，如果為空則創(chuàng)建root； - 如果
root非空，則需要判斷插入節(jié)點的val比根節(jié)點的val是大還是??； - 如果比根節(jié)點小，說明是左子樹的節(jié)點；
- 如果比根節(jié)點大，說明是右子樹的節(jié)點；
- 上面兩步重復執(zhí)行，直到找到一個點，如果這個點小于我們要插入的值，且不存在右子樹，將這個點作為其右葉子節(jié)點；如果這個點大于我們要插入的值，且不存在右子樹，將這個點作為其左葉子節(jié)點。
示例代碼如下：
// 創(chuàng)建要給插入節(jié)點的方法
insertNode(val) {
const that = this
// 允許接受一個數(shù)組，批量插入
if (Object.prototype.toString.call(val) === '[object Array]') {
val.forEach(function (v) {
that.insertNode(v)
})
return
}
if (typeof val !== 'number') throw Error('插入的值不是一個數(shù)字')
const newNode = this.Node(val)
if (this.root) {
// 根節(jié)點非空
this.#insertNode(this.root, newNode)
} else {
// 根節(jié)點是空的，直接創(chuàng)建
this.root = newNode
}
}
// 私有方法，插入節(jié)點
#insertNode(root, newNode) {
if (newNode.val < root.val) {
// 新節(jié)點比根節(jié)點小，左子樹
if (root.left === null) {
// 如果左子樹上沒有內(nèi)容，則直接插入，如果有，尋找下一個插入位置
root.left = newNode
root.left.parent = root
} else {
this.#insertNode(root.left, newNode)
}
} else {
// 新節(jié)點比根節(jié)點大，右子樹
if (root.right === null) {
// 如果右子樹上沒有內(nèi)容，則直接插入，如果有，尋找下一個插入位置
root.right = newNode
root.right.parent = root
} else {
this.#insertNode(root.right, newNode)
}
}
}在類中定義了insertNode方法，這個方法接受數(shù)值或者數(shù)值類型的數(shù)組，將其插入這個二叉搜索樹中；插入方法我們定義了一個私有的#insertNode方法，用于節(jié)點的插入。
為了看到效果，我們這里定義了一個靜態(tài)方法，用于中序遍歷（因為中序遍歷的順序是左根右，在二叉搜索樹中使用中序排序，最終結(jié)果是從小到大依次排序的）這個樹，并返回一個數(shù)組，
示例代碼如下：
// 中序遍歷這個樹
static inorder(root) {
if (!root) return
const result = []
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()
result.push(node.val)
p = node.right
}
return result
}測試代碼如下：
const tree = new BinarySearchTree()
tree.insertNode([71, 35, 87, 22, 53, 46, 66, 78, 98])
const arr = BinarySearchTree.inorder(tree.root)
console.log(arr) // [ 22, 35, 46, 53, 66,71, 78, 87, 98 ]
最終的樹結(jié)構(gòu)如下：
查找二叉搜索樹中的數(shù)據(jù)
現(xiàn)在我們封裝一個find方法，用于查找二叉搜索樹中的某個數(shù)據(jù)，假如我們查找66這個數(shù)據(jù)，利用上面那個樹，
其查找思路如下圖所示：
遞歸方式實現(xiàn)如下：
/**
* 根據(jù) val 查找節(jié)點
* @param {number} val 需要查找的數(shù)值
* @returns 如果找到返回當前節(jié)點的引用，如果未找到返回 undefined
*/
find(val) {
if (typeof val !== 'number') throw Error('插入的值不是一個數(shù)字')
function r(node, val) {
// console.log(node)
if (!node) return
if (node.val < val) {
return r(node.right, val)
} else if (node.val > val) {
return r(node.left, val)
} else {
return node
}
}
return r(this.root, val)
}迭代方式實現(xiàn)如下：
/**
* 根據(jù) val 查找節(jié)點
* @param {number} val 需要查找的數(shù)值
* @returns 如果找到返回當前節(jié)點的引用，如果未找到返回 undefined
*/
find(val) {
if (typeof val !== 'number') throw Error('插入的值不是一個數(shù)字')
let node = this.root
while (node) {
if (node.val < val) {
// 進入右子樹
node = node.right
} else if (node.val > val) {
// 進入左子樹
node = node.left
} else {
return node
}
}
return
}兩者相對來說，使用迭代的方式更優(yōu)一些。
刪除二叉搜索樹的某個節(jié)點
前驅(qū)后繼節(jié)點
在開始刪除二叉搜索樹中的某個節(jié)點之前，我們先來了解一下什么是前驅(qū)和后繼節(jié)點；
- 前驅(qū)節(jié)點指的是使用中序遍歷當前二叉搜索樹時，當前節(jié)點的上一個節(jié)點就是前驅(qū)節(jié)點，換一種說法就是在二叉搜索樹中，當前節(jié)點的左子樹的最大值，就是該節(jié)點的前驅(qū)節(jié)點；
- 后繼節(jié)點指的是使用中序遍歷當前二叉搜索樹時，當前節(jié)點的下一個節(jié)點就是后繼節(jié)點，換一種說法就是在二叉搜索樹中，當前節(jié)點的右子樹的最小值，就是該節(jié)點的后繼節(jié)點；
如下圖所示：
了解了什么是前驅(qū)和后繼節(jié)點之后，現(xiàn)在我們來開始刪除某個節(jié)點。
刪除一個節(jié)點的三種情況
當刪除的節(jié)點是葉子節(jié)點時，只需要將指向它的指針修改為null，即可，如下圖所示：
當需要刪除的節(jié)點存在一個子節(jié)點時， 需要將要刪除節(jié)點的子節(jié)點的parent指針指向要刪除節(jié)點的父節(jié)點，然后將當前要刪除節(jié)點的父節(jié)點指向子節(jié)點即可，
如下圖所示：
當需要刪除的節(jié)點存在一個子節(jié)點時， 刪除步驟如下：
- 找到當前節(jié)點的前驅(qū)或者后繼節(jié)點，這里選擇后繼；
- 然后將后繼節(jié)點的值賦值給當前節(jié)點；
- 刪除后繼節(jié)點。
如下圖所示：
現(xiàn)在我們將這些情況已經(jīng)分析完成了，現(xiàn)在通過代碼實現(xiàn)一下。
實現(xiàn)代碼
實現(xiàn)代碼如下：
remove(val) {
// 1. 刪除節(jié)點
const cur = this.find(val)
if (!val) return false // 未找到需要刪除的節(jié)點
if (!cur.left && !cur.right) {
// 1. 當前節(jié)點是葉子節(jié)點的情況
this.#removeLeaf(cur)
} else if (cur.left && cur.right) {
// 2. 當前節(jié)點存在兩個子節(jié)點
// 2.1 找到當前節(jié)點的后繼節(jié)點
const successorNode = this.#minNode(cur.right)
// 2.2 將后繼節(jié)點的值賦值給當前值
cur.val = successorNode.val
if (!successorNode.left && !successorNode.right) {
// 2.3 后繼節(jié)點是葉子節(jié)點，直接刪除
this.#removeLeaf(successorNode)
} else {
// 2.4 后繼節(jié)點不是葉子節(jié)點
// 2.4.1記錄該節(jié)點的子節(jié)點，
let child =
successorNode.left !== null ? successorNode.left : successorNode.right
// 2.4.2 記錄該節(jié)點的父節(jié)點
let parent = successorNode.parent
// 2.4.3 如果當前父節(jié)點的left是后繼結(jié)點，則把后繼結(jié)點的父節(jié)點的left指向后繼結(jié)點的子節(jié)點
if (parent.left === successorNode) {
parent.left = child
} else {
// 2.4.4 如果不是，則讓父節(jié)點的right指向后繼結(jié)點的子節(jié)點
parent.right = child
}
// 2.4.5 修改子節(jié)點的parent指針
child.parent = parent
}
// 2.3 刪除后繼節(jié)點
} else {
// 記錄當前節(jié)點的是否是父節(jié)點的左子樹
const isLeft = cur.val < cur.parent.val
// 3. 僅存在一個子節(jié)點
if (cur.left) {
// 3.1 當前節(jié)點存在左子樹
cur.parent[isLeft ? 'left' : 'right'] = cur.left
cur.left.parent = cur.parent
} else if (cur.right) {
// 3.2 當前節(jié)點存在右子樹
cur.parent[isLeft ? 'left' : 'right'] = cur.right
cur.right.parent = cur.parent
}
}
}
// 刪除葉子節(jié)點
#removeLeaf(node) {
if (!node) return
const parent = node.parent
if (node.val < parent.val) {
// 當前要刪除的葉子節(jié)點是左節(jié)點
parent.left = null
} else {
// 當前要刪除的葉子節(jié)點是右節(jié)點
parent.right = null
}
}
// 查找最小值
#minNode(node) {
if (!node) return
if (!node.left) return node
let p = node.left
while (p.left) {
p = p.left
}
return p
}完整代碼
本篇文章中的完整代碼如下：
class BinarySearchTree {
constructor() {
// 初始化根節(jié)點
this.root = null
}
// 創(chuàng)建一個節(jié)點
Node(val) {
return {
left: null, // 左子樹
right: null, // 右子樹
parent: null, // 父節(jié)點
val,
}
}
/**
* 創(chuàng)建要給插入節(jié)點的方法
* @param {number | array[number]} val
* @returns
*/
insertNode(val) {
const that = this
// 允許接受一個數(shù)組，批量插入
if (Object.prototype.toString.call(val) === '[object Array]') {
val.forEach(function (v) {
that.insertNode(v)
})
return
}
if (typeof val !== 'number') throw Error('插入的值不是一個數(shù)字')
const newNode = this.Node(val)
if (this.root) {
// 根節(jié)點非空
this.#insertNode(this.root, newNode)
} else {
// 根節(jié)點是空的，直接創(chuàng)建
this.root = newNode
}
}
/**
* 私有方法，插入節(jié)點
* @param {Object{Node}} root
* @param {Object{Node}} newNode
*/
#insertNode(root, newNode) {
if (newNode.val < root.val) {
// 新節(jié)點比根節(jié)點小，左子樹
if (root.left === null) {
// 如果左子樹上沒有內(nèi)容，則直接插入，如果有，尋找下一個插入位置
root.left = newNode
root.left.parent = root
} else {
this.#insertNode(root.left, newNode)
}
} else {
// 新節(jié)點比根節(jié)點大，右子樹
if (root.right === null) {
root.right = newNode
root.right.parent = root
} else {
this.#insertNode(root.right, newNode)
}
}
}
/**
* 根據(jù) val 查找節(jié)點
* @param {number} val 需要查找的數(shù)值
* @returns 如果找到返回當前節(jié)點的引用，如果未找到返回 undefined
*/
find(val) {
if (typeof val !== 'number') throw Error('插入的值不是一個數(shù)字')
let node = this.root
while (node) {
if (node.val < val) {
// 進入右子樹
node = node.right
} else if (node.val > val) {
// 進入左子樹
node = node.left
} else {
return node
}
}
return
}
// /**
// * 根據(jù) val 查找節(jié)點 遞歸版
// * @param {number} val 需要查找的數(shù)值
// * @returns 如果找到返回當前節(jié)點的引用，如果未找到返回 undefined
// */
// find(val) {
// if (typeof val !== 'number') throw Error('插入的值不是一個數(shù)字')
// function r(node, val) {
// // console.log(node)
// if (!node) return
// if (node.val < val) {
// return r(node.right, val)
// } else if (node.val > val) {
// return r(node.left, val)
// } else {
// return node
// }
// }
// return r(this.root, val)
// }
remove(val) {
// 1. 刪除節(jié)點
const cur = this.find(val)
if (!val) return false // 未找到需要刪除的節(jié)點
if (!cur.left && !cur.right) {
// 1. 當前節(jié)點是葉子節(jié)點的情況
this.#removeLeaf(cur)
} else if (cur.left && cur.right) {
// 2. 當前節(jié)點存在兩個子節(jié)點
// 2.1 找到當前節(jié)點的后繼節(jié)點
const successorNode = this.#minNode(cur.right)
// 2.2 將后繼節(jié)點的值賦值給當前值
cur.val = successorNode.val
if (!successorNode.left && !successorNode.right) {
// 2.3 后繼節(jié)點是葉子節(jié)點，直接刪除
this.#removeLeaf(successorNode)
} else {
// 2.4 后繼節(jié)點不是葉子節(jié)點
// 2.4.1記錄該節(jié)點的子節(jié)點，
let child =
successorNode.left !== null ? successorNode.left : successorNode.right
// 2.4.2 記錄該節(jié)點的父節(jié)點
let parent = successorNode.parent
// 2.4.3 如果當前父節(jié)點的left是后繼結(jié)點，則把后繼結(jié)點的父節(jié)點的left指向后繼結(jié)點的子節(jié)點
if (parent.left === successorNode) {
parent.left = child
} else {
// 2.4.4 如果不是，則讓父節(jié)點的right指向后繼結(jié)點的子節(jié)點
parent.right = child
}
// 2.4.5 修改子節(jié)點的parent指針
child.parent = parent
}
// 2.3 刪除后繼節(jié)點
} else {
// 記錄當前節(jié)點的是否是父節(jié)點的左子樹
const isLeft = cur.val < cur.parent.val
// 3. 僅存在一個子節(jié)點
if (cur.left) {
// 3.1 當前節(jié)點存在左子樹
cur.parent[isLeft ? 'left' : 'right'] = cur.left
cur.left.parent = cur.parent
} else if (cur.right) {
// 3.2 當前節(jié)點存在右子樹
cur.parent[isLeft ? 'left' : 'right'] = cur.right
cur.right.parent = cur.parent
}
}
}
// 刪除葉子節(jié)點
#removeLeaf(node) {
if (!node) return
const parent = node.parent
if (node.val < parent.val) {
// 當前要刪除的葉子節(jié)點是左節(jié)點
parent.left = null
} else {
// 當前要刪除的葉子節(jié)點是右節(jié)點
parent.right = null
}
}
// 查找最小值
#minNode(node) {
if (!node) return
if (!node.left) return node
let p = node.left
while (p.left) {
p = p.left
}
return p
}
// 中序遍歷這個樹
static inorder(root) {
if (!root) return
const result = []
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()
result.push(node.val)
p = node.right
}
return result
}
}
const tree = new BinarySearchTree()
tree.insertNode([71, 35, 84, 22, 53, 46, 66, 81, 83, 82, 88, 98])
console.log(BinarySearchTree.inorder(tree.root)) // [ 22, 35, 46, 53, 66, 71, 81, 82, 83, 84, 88, 98 ]
tree.remove(71
console.log(BinarySearchTree.inorder(tree.root)) // [ 22, 35, 46, 53, 66, 81, 82, 83, 84, 88, 98 ]總結(jié)
文章介紹了二叉搜索樹的性質(zhì)以及二叉搜索樹的構(gòu)建、查找和刪除
到此這篇關(guān)于JavaScript二叉搜索樹構(gòu)建操作詳解的文章就介紹到這了,更多相關(guān)JS二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了微信小程序點擊item使之滾動到屏幕中間位置,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-03-03
在使用try catch處理iframe跨域產(chǎn)生的異常時，chrome和safari瀏覽器似乎不能正常運作：他們直接拋出了錯誤而沒有拋出可供JS截獲的異常。2011-09-09
在本文中小編通過實例給大家分享了JavaScript中如何截取字符串的方法，需要的朋友們參考一下。2018-11-11
easyui combogrid實現(xiàn)本地模糊搜索過濾多列
本篇文章主要介紹了easyui combogrid實現(xiàn)本地模糊搜索過濾多列，非常具有實用價值，需要的朋友可以參考下2017-05-05
閉包機制是JavaScript的重點和難點，本文希望能幫助大家輕松的學習閉包。下面跟著小編一起來看下吧2017-03-03
微信小程序 調(diào)用微信授權(quán)窗口相關(guān)問題解決
這篇文章主要介紹了微信小程序 調(diào)用微信授權(quán)窗口相關(guān)問題解決,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了JavaScript中var的重要性,結(jié)合實例形式分析了javascript變量定義、作用范圍、作用域及相關(guān)操作注意事項,需要的朋友可以參考下2019-07-07
基于JavaScript+HTML5 實現(xiàn)打地鼠小游戲邏輯流程圖文詳解(附完整代碼)
打地鼠小游戲大家都喜歡玩，本文是以html編寫的，并且使用HBulider軟件進行編寫的，下面通過本文給大家分享基于JavaScript+HTML5 實現(xiàn)打地鼠小游戲邏輯流程圖文詳解，需要的朋友參考下吧2017-11-11
Javascript和Java、C這些語言不同，它是一種無類型、弱檢測的語言。它對變量的定義并不需要聲明變量類型，我們只要通過賦值的形式，可以將各種類型的數(shù)據(jù)賦值給同一個變量2012-01-01
js下通過prototype擴展實現(xiàn)indexOf的代碼
這里使用js prototype擴展實現(xiàn)的indexOf的實現(xiàn)代碼，跟js自帶的方法，差不多。2010-12-12