JavaScript二叉搜索樹構建操作詳解

3403771864 發(fā)布于2022-09-18 21:31 / 400人閱讀

　　今天我們一起學習什特殊的二叉樹二叉搜索樹（BSTBinary Search Tree），您也可以叫它二叉排序樹、二叉查找樹?，F(xiàn)在我們看看。

二叉搜索樹說說明

　　二叉搜索樹顧名思義就是樹形叉一樣，現(xiàn)在說特質：

　　對于任何一個非空節(jié)點來說，它左子樹上的值必須小于當前值；

　　對于任何一個非空節(jié)點來說，它右子樹上的值必須大于當前值；

　　任何一顆子樹滿足上面的條件；

　　如下圖所示：

　　上圖就是一顆二叉搜索樹，總結來說就是右邊數(shù)值大于左邊數(shù)值。上圖的根節(jié)點的值71，它的左子樹的值分別是22、35、46、53和66，這幾個都是滿足左子樹小于當前值；它的右子樹的值分別是78、87和98，這幾個值是滿足右子樹大于當前值的；上述就顯示出二叉搜索樹特質。

　　根據二叉搜索樹的特質，我們還能得到以下結論：

　　二叉搜索樹的任何一個節(jié)點的左子樹、右子樹都是一顆二叉搜索樹；

　　二叉搜索樹的最小的節(jié)點是整顆樹的最左下角的葉子節(jié)點；

　　二叉搜索樹的最大的節(jié)點是整棵樹的最右下角的葉子節(jié)點；

　　構建一顆二叉搜索樹

　　先項目中用avaScript來實現(xiàn)構建一顆二叉搜索樹，我們可以想象成一個一個節(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é)點的指針以及當前值。

　　二叉搜索樹的操作

　　關于二叉樹的遍歷操作我們在上一篇文章中已經介紹了，這里不在重復，這里主要介紹如下操作：

　　插入操作

　　查找操作

　　刪除操作

　　向二叉搜索樹中插入數(shù)據

　　向一個二叉搜索樹插入數(shù)據實現(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) {
　　// 如果左子樹上沒有內容，則直接插入，如果有，尋找下一個插入位置
　　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)
　　}
　　}
　　}

　　在類中定義了insertNode方法，這個方法接受數(shù)值或者數(shù)值類型的數(shù)組，將其插入這個二叉搜索樹中；插入方法我們定義了一個私有的#insertNode方法，用于節(jié)點的插入。

　　現(xiàn)在為實現(xiàn)預估動作結果，在這里定義了一個靜態(tài)方法，用于中序遍歷（因為中序遍歷的順序是左根右，在二叉搜索樹中使用中序排序，最終結果是從小到大依次排序的）這個樹，并返回一個數(shù)組，

　　示例代碼如下：

　　// 中序遍歷這個樹
　　static inorder(root) {
　　if (!root) return
　　const result = []
　　const stack = []
　　// 定義一個指針
　　let p = root
　　// 如果棧中有數(shù)據或者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 ]

　　最終的樹結構如下：

　　查找二叉搜索樹中的數(shù)據

　　現(xiàn)在我們封裝一個find方法，用于查找二叉搜索樹中的某個數(shù)據，假如我們查找66這個數(shù)據，利用上面那個樹，

　　其查找思路如下圖所示：

　　遞歸方式實現(xiàn)如下：

　　/**
　　* 根據 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é)點

　　前驅后繼節(jié)點

　　在開始刪除二叉搜索樹中的某個節(jié)點之前，我們先來了解一下什么是前驅和后繼節(jié)點；

　　前驅節(jié)點指的是使用中序遍歷當前二叉搜索樹時，當前節(jié)點的上一個節(jié)點就是前驅節(jié)點，換一種說法就是在二叉搜索樹中，當前節(jié)點的左子樹的最大值，就是該節(jié)點的前驅節(jié)點；

　　后繼節(jié)點指的是使用中序遍歷當前二叉搜索樹時，當前節(jié)點的下一個節(jié)點就是后繼節(jié)點，換一種說法就是在二叉搜索樹中，當前節(jié)點的右子樹的最小值，就是該節(jié)點的后繼節(jié)點；

　　如下圖所示：

　　了解了什么是前驅和后繼節(jié)點之后，現(xiàn)在我們來開始刪除某個節(jié)點。

　　刪除一個節(jié)點的三種情況

　　當刪除的節(jié)點是葉子節(jié)點時，只需要將指向它的指針修改為null，即可，如下圖所示：

　　當需要刪除的節(jié)點存在一個子節(jié)點時，需要將要刪除節(jié)點的子節(jié)點的parent指針指向要刪除節(jié)點的父節(jié)點，然后將當前要刪除節(jié)點的父節(jié)點指向子節(jié)點即可，

　　如下圖所示：

　　當需要刪除的節(jié)點存在一個子節(jié)點時，刪除步驟如下：

　　找到當前節(jié)點的前驅或者后繼節(jié)點，這里選擇后繼；

　　然后將后繼節(jié)點的值賦值給當前節(jié)點；

　　刪除后繼節(jié)點。

　　如下圖所示：

　　現(xiàn)在我們將這些情況已經分析完成了，現(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é)點的left指向后繼結點的子節(jié)點
　　if (parent.left === successorNode) {
　　parent.left = child
　　} else {
　　// 2.4.4 如果不是，則讓父節(jié)點的right指向后繼結點的子節(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) {
　　// 如果左子樹上沒有內容，則直接插入，如果有，尋找下一個插入位置
　　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)
　　}
　　}
　　}
　　/**
　　* 根據 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
　　}
　　// /**
　　// * 根據 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é)點的left指向后繼結點的子節(jié)點
　　if (parent.left === successorNode) {
　　parent.left = child
　　} else {
　　// 2.4.4 如果不是，則讓父節(jié)點的right指向后繼結點的子節(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ù)據或者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 ]

　　總結

　　此篇結束，大家可以更多深入了解關于二叉搜索樹的其他內容。

GPU云服務器云服務器二叉樹排序樹規(guī)則二叉查找樹二叉排序樹二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/127769.html

CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優(yōu)秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數(shù)組的極值技巧使你的更加專業(yè)前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續(xù)更新… 一、...

Jonathan Shieber 2019-08-29 12:33 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優(yōu)秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數(shù)組的極值技巧使你的更加專業(yè)前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續(xù)更新… 一、...

SHERlocked93 2019-08-22 11:04 評論0 收藏0
PHP面試：說說你理解的二叉樹吧

摘要：每個節(jié)點都必須滿足這個屬性，這就是二叉搜索樹。自平衡二叉樹自平衡二叉搜索樹或高度平衡二叉搜索樹是一種特殊類型的二叉搜索樹，它試圖通過自動調整來盡量保持樹的高度或層次盡可能小。自平衡或高度平衡二叉搜索樹有不同的實現(xiàn)。理解和實現(xiàn)樹迄今為止，我們對數(shù)據結構的探索僅觸及線性部分。無論我們使用數(shù)組、鏈表、棧還是隊列，都是線性數(shù)據結構。我們已經看到了線性數(shù)據結構操作的復雜性，大多數(shù)時候，插入和...

leejan97 2019-07-01 10:20 評論0 收藏0
數(shù)據結構與算法JavaScript （不定時更新）

摘要：每個列表中的數(shù)據項稱為元素。棧被稱為一種后入先出，的數(shù)據結構。散列使用的數(shù)據結構叫做散列表。不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。因此二叉搜索樹需要平衡，即左右子樹高度要相近。樓樓非計算機專業(yè)，但是對計算機也還算喜歡。個人理解若有偏差，歡迎各位批評指正！對于數(shù)據結構和算法一直是我的薄弱環(huán)節(jié)，相信大多數(shù)前端工程師可能多少會有些這方面的弱點，加上數(shù)據結構和算法本...

levius 2019-08-26 11:40 評論0 收藏0

發(fā)表評論

登陸后可評論

0條評論

3403771864

男|高級講師

我要關注我要私信

TA的文章

匯總有關JS對象的創(chuàng)建與繼承

閱讀 566·2023-03-27 18:33
小程序有關手寫板簽名具體代碼

閱讀 755·2023-03-26 17:27
剖析Vue3中偵聽器watch的使用教程

閱讀 656·2023-03-26 17:14
JavaScript取消請求有哪些方法

閱讀 608·2023-03-17 21:13
解析React SSR 中的限流案例

閱讀 541·2023-03-17 08:28
解析微信小程序如何實現(xiàn)日期范圍選擇

閱讀 1829·2023-02-27 22:32
講解Web Components實現(xiàn)類Element UI中的Card卡片

閱讀 1324·2023-02-27 22:27
JavaScript使用export和import的兩個報錯如何解決

閱讀 2207·2023-01-20 08:28

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript二叉搜索樹構建操作詳解

相關文章

CSS技巧 - 收藏集 - 掘金

CSS技巧 - 收藏集 - 掘金

PHP面試：說說你理解的二叉樹吧

**數(shù)據結構與算法JavaScript （不定時更新）**

發(fā)表評論

0條評論

3403771864

男|高級講師

TA的文章

匯總有關JS對象的創(chuàng)建與繼承

小程序有關手寫板簽名具體代碼

剖析Vue3中偵聽器watch的使用教程

JavaScript取消請求有哪些方法

解析React SSR 中的限流案例

解析微信小程序如何實現(xiàn)日期范圍選擇

講解Web Components實現(xiàn)類Element UI中的Card卡片

JavaScript使用export和import的兩個報錯如何解決

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript二叉搜索樹構建操作詳解

相關文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！