快捷導(dǎo)航

JavaScript二叉搜索樹(shù)構(gòu)建操作詳解

更新時(shí)間：2022年07月13日 16:29:25 作者：??一碗周???

這篇文章主要介紹了JavaScript二叉搜索樹(shù)構(gòu)建操作詳解，文章圍繞主題展開(kāi)二叉搜索樹(shù)的性質(zhì)以及二叉搜索樹(shù)的構(gòu)建、查找和刪除等內(nèi)容，需要的小伙伴可以參考一下

前言

前面我們介紹了二叉樹(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)以及二叉樹(shù)的遍歷算法，這篇文章我們來(lái)學(xué)習(xí)一下一個(gè)特殊的二叉樹(shù)——二叉搜索樹(shù)（BST Binary Search Tree），也叫二叉排序樹(shù)、二叉查找樹(shù)。

什么是二叉搜索樹(shù)

二叉搜索樹(shù)首先它是一棵二叉樹(shù)，而且還滿足下面這些特質(zhì)：

對(duì)于任何一個(gè)非空節(jié)點(diǎn)來(lái)說(shuō)，它左子樹(shù)上的值必須小于當(dāng)前值；
對(duì)于任何一個(gè)非空節(jié)點(diǎn)來(lái)說(shuō)，它右子樹(shù)上的值必須大于當(dāng)前值；
任何一顆子樹(shù)滿足上面的條件；

如下圖所示：

上圖就是一顆二叉搜索樹(shù)，我們就拿根節(jié)點(diǎn)來(lái)說(shuō)，根節(jié)點(diǎn)的值71，它的左子樹(shù)的值分別是22、35、46、53和66，這幾個(gè)都是滿足左子樹(shù)小于當(dāng)前值；它的右子樹(shù)的值分別是78、87和98，這幾個(gè)值是滿足右子樹(shù)大于當(dāng)前值的；以此類推，所以上圖就是一棵二叉搜索樹(shù)。

根據(jù)二叉搜索樹(shù)的特質(zhì)，我們還能得到以下結(jié)論：

二叉搜索樹(shù)的任何一個(gè)節(jié)點(diǎn)的左子樹(shù)、右子樹(shù)都是一顆二叉搜索樹(shù)；
二叉搜索樹(shù)的最小的節(jié)點(diǎn)是整顆樹(shù)的最左下角的葉子節(jié)點(diǎn)；
二叉搜索樹(shù)的最大的節(jié)點(diǎn)是整棵樹(shù)的最右下角的葉子節(jié)點(diǎn)；

構(gòu)建一顆二叉搜索樹(shù)

我們現(xiàn)在使用JavaScript來(lái)構(gòu)建一顆二叉搜索樹(shù)，要知道一顆二叉搜索樹(shù)也是由一個(gè)一個(gè)節(jié)點(diǎn)組成，這里我們通過(guò)class創(chuàng)建一個(gè)節(jié)點(diǎn)類，

示例代碼如下：

class BinarySearchTree {
  constructor() {
    // 初始化根節(jié)點(diǎn)
    this.root = null
  }

  // 創(chuàng)建一個(gè)節(jié)點(diǎn)
  Node(val) {
    return {
      left: null, // 左子樹(shù)
      right: null, // 右子樹(shù)
      parent: null, // 父節(jié)點(diǎn)
      val,
    }
  }
}

這里一個(gè)節(jié)點(diǎn)由四部分組成，分別是指向左子樹(shù)的指針、指向右子樹(shù)的指針、指向父節(jié)點(diǎn)的指針以及當(dāng)前值。

二叉搜索樹(shù)的操作

關(guān)于二叉樹(shù)的遍歷操作我們?cè)?a href="http://www.dbjr.com.cn/article/255315.htm" target="_blank">上一篇文章中已經(jīng)介紹了，這里不在重復(fù)，這里主要介紹如下操作：

插入操作
查找操作
刪除操作

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

向一個(gè)二叉搜索樹(shù)插入數(shù)據(jù)實(shí)現(xiàn)思路如下：

判斷root是否為空，如果為空則創(chuàng)建root；
如果root非空，則需要判斷插入節(jié)點(diǎn)的val比根節(jié)點(diǎn)的val是大還是小；
如果比根節(jié)點(diǎn)小，說(shuō)明是左子樹(shù)的節(jié)點(diǎn)；
如果比根節(jié)點(diǎn)大，說(shuō)明是右子樹(shù)的節(jié)點(diǎn)；
上面兩步重復(fù)執(zhí)行，直到找到一個(gè)點(diǎn)，如果這個(gè)點(diǎn)小于我們要插入的值，且不存在右子樹(shù)，將這個(gè)點(diǎn)作為其右葉子節(jié)點(diǎn)；如果這個(gè)點(diǎn)大于我們要插入的值，且不存在右子樹(shù)，將這個(gè)點(diǎn)作為其左葉子節(jié)點(diǎn)。

示例代碼如下：

// 創(chuàng)建要給插入節(jié)點(diǎn)的方法
insertNode(val) {
  const that = this
  // 允許接受一個(gè)數(shù)組，批量插入
  if (Object.prototype.toString.call(val) === '[object Array]') {
    val.forEach(function (v) {
      that.insertNode(v)
    })
    return
  }
  if (typeof val !== 'number') throw Error('插入的值不是一個(gè)數(shù)字')
  const newNode = this.Node(val)
  if (this.root) {
    // 根節(jié)點(diǎn)非空
    this.#insertNode(this.root, newNode)
  } else {
    // 根節(jié)點(diǎn)是空的，直接創(chuàng)建
    this.root = newNode
  }
}
// 私有方法，插入節(jié)點(diǎn)
#insertNode(root, newNode) {
  if (newNode.val < root.val) {
    // 新節(jié)點(diǎn)比根節(jié)點(diǎn)小，左子樹(shù)
    if (root.left === null) {
      // 如果左子樹(shù)上沒(méi)有內(nèi)容，則直接插入，如果有，尋找下一個(gè)插入位置
      root.left = newNode
      root.left.parent = root
    } else {
      this.#insertNode(root.left, newNode)
    }
  } else {
    // 新節(jié)點(diǎn)比根節(jié)點(diǎn)大，右子樹(shù)
    if (root.right === null) {
      // 如果右子樹(shù)上沒(méi)有內(nèi)容，則直接插入，如果有，尋找下一個(gè)插入位置
      root.right = newNode
      root.right.parent = root
    } else {
      this.#insertNode(root.right, newNode)
    }
  }
}

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

為了看到效果，我們這里定義了一個(gè)靜態(tài)方法，用于中序遍歷（因?yàn)橹行虮闅v的順序是左根右，在二叉搜索樹(shù)中使用中序排序，最終結(jié)果是從小到大依次排序的）這個(gè)樹(shù)，并返回一個(gè)數(shù)組，

示例代碼如下：

// 中序遍歷這個(gè)樹(shù)
static inorder(root) {
  if (!root) return
  const result = []
  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()
    result.push(node.val)
    p = node.right
  }
  return result
}

測(cè)試代碼如下：

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ù)結(jié)構(gòu)如下：

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

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

其查找思路如下圖所示：

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

/**
 * 根據(jù) val 查找節(jié)點(diǎn)
 * @param {number} val 需要查找的數(shù)值
 * @returns 如果找到返回當(dāng)前節(jié)點(diǎn)的引用，如果未找到返回 undefined
 */
find(val) {
  if (typeof val !== 'number') throw Error('插入的值不是一個(gè)數(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)
}

迭代方式實(shí)現(xiàn)如下：

/**
 * 根據(jù) val 查找節(jié)點(diǎn)
 * @param {number} val 需要查找的數(shù)值
 * @returns 如果找到返回當(dāng)前節(jié)點(diǎn)的引用，如果未找到返回 undefined
 */
find(val) {
  if (typeof val !== 'number') throw Error('插入的值不是一個(gè)數(shù)字')
  let node = this.root
  while (node) {
    if (node.val < val) {
      // 進(jìn)入右子樹(shù)
      node = node.right
    } else if (node.val > val) {
      // 進(jìn)入左子樹(shù)
      node = node.left
    } else {
      return node
    }
  }
  return
}

兩者相對(duì)來(lái)說(shuō)，使用迭代的方式更優(yōu)一些。

刪除二叉搜索樹(shù)的某個(gè)節(jié)點(diǎn)

前驅(qū)后繼節(jié)點(diǎn)

在開(kāi)始刪除二叉搜索樹(shù)中的某個(gè)節(jié)點(diǎn)之前，我們先來(lái)了解一下什么是前驅(qū)和后繼節(jié)點(diǎn)；

前驅(qū)節(jié)點(diǎn)指的是使用中序遍歷當(dāng)前二叉搜索樹(shù)時(shí)，當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)就是前驅(qū)節(jié)點(diǎn)，換一種說(shuō)法就是在二叉搜索樹(shù)中，當(dāng)前節(jié)點(diǎn)的左子樹(shù)的最大值，就是該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)；
后繼節(jié)點(diǎn)指的是使用中序遍歷當(dāng)前二叉搜索樹(shù)時(shí)，當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就是后繼節(jié)點(diǎn)，換一種說(shuō)法就是在二叉搜索樹(shù)中，當(dāng)前節(jié)點(diǎn)的右子樹(shù)的最小值，就是該節(jié)點(diǎn)的后繼節(jié)點(diǎn)；

如下圖所示：

了解了什么是前驅(qū)和后繼節(jié)點(diǎn)之后，現(xiàn)在我們來(lái)開(kāi)始刪除某個(gè)節(jié)點(diǎn)。

刪除一個(gè)節(jié)點(diǎn)的三種情況

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

當(dāng)需要?jiǎng)h除的節(jié)點(diǎn)存在一個(gè)子節(jié)點(diǎn)時(shí)，需要將要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)的parent指針指向要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)，然后將當(dāng)前要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)指向子節(jié)點(diǎn)即可，

如下圖所示：

當(dāng)需要?jiǎng)h除的節(jié)點(diǎn)存在一個(gè)子節(jié)點(diǎn)時(shí)，刪除步驟如下：

找到當(dāng)前節(jié)點(diǎn)的前驅(qū)或者后繼節(jié)點(diǎn)，這里選擇后繼；
然后將后繼節(jié)點(diǎn)的值賦值給當(dāng)前節(jié)點(diǎn)；
刪除后繼節(jié)點(diǎn)。

如下圖所示：

現(xiàn)在我們將這些情況已經(jīng)分析完成了，現(xiàn)在通過(guò)代碼實(shí)現(xiàn)一下。

實(shí)現(xiàn)代碼

實(shí)現(xiàn)代碼如下：

remove(val) {
  // 1. 刪除節(jié)點(diǎn)
  const cur = this.find(val)
  if (!val) return false // 未找到需要?jiǎng)h除的節(jié)點(diǎn)
  if (!cur.left && !cur.right) {
    // 1. 當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)的情況
    this.#removeLeaf(cur)
  } else if (cur.left && cur.right) {
    // 2. 當(dāng)前節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)
    // 2.1 找到當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)
    const successorNode = this.#minNode(cur.right)
    // 2.2 將后繼節(jié)點(diǎn)的值賦值給當(dāng)前值
    cur.val = successorNode.val
    if (!successorNode.left && !successorNode.right) {
      // 2.3 后繼節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接刪除
      this.#removeLeaf(successorNode)
    } else {
      // 2.4 后繼節(jié)點(diǎn)不是葉子節(jié)點(diǎn)
      // 2.4.1記錄該節(jié)點(diǎn)的子節(jié)點(diǎn)，
      let child =
        successorNode.left !== null ? successorNode.left : successorNode.right
      // 2.4.2 記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)
      let parent = successorNode.parent
      // 2.4.3 如果當(dāng)前父節(jié)點(diǎn)的left是后繼結(jié)點(diǎn)，則把后繼結(jié)點(diǎn)的父節(jié)點(diǎn)的left指向后繼結(jié)點(diǎn)的子節(jié)點(diǎn)
      if (parent.left === successorNode) {
        parent.left = child
      } else {
        // 2.4.4 如果不是，則讓父節(jié)點(diǎn)的right指向后繼結(jié)點(diǎn)的子節(jié)點(diǎn)
        parent.right = child
      }
      // 2.4.5 修改子節(jié)點(diǎn)的parent指針
      child.parent = parent
    }

    // 2.3 刪除后繼節(jié)點(diǎn)
  } else {
    // 記錄當(dāng)前節(jié)點(diǎn)的是否是父節(jié)點(diǎn)的左子樹(shù)
    const isLeft = cur.val < cur.parent.val
    // 3. 僅存在一個(gè)子節(jié)點(diǎn)
    if (cur.left) {
      // 3.1 當(dāng)前節(jié)點(diǎn)存在左子樹(shù)
      cur.parent[isLeft ? 'left' : 'right'] = cur.left
      cur.left.parent = cur.parent
    } else if (cur.right) {
      // 3.2 當(dāng)前節(jié)點(diǎn)存在右子樹(shù)
      cur.parent[isLeft ? 'left' : 'right'] = cur.right
      cur.right.parent = cur.parent
    }
  }
}
// 刪除葉子節(jié)點(diǎn)
#removeLeaf(node) {
  if (!node) return
  const parent = node.parent
  if (node.val < parent.val) {
    // 當(dāng)前要?jiǎng)h除的葉子節(jié)點(diǎn)是左節(jié)點(diǎn)
    parent.left = null
  } else {
    // 當(dāng)前要?jiǎng)h除的葉子節(jié)點(diǎn)是右節(jié)點(diǎn)
    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é)點(diǎn)
    this.root = null
  }

  // 創(chuàng)建一個(gè)節(jié)點(diǎn)
  Node(val) {
    return {
      left: null, // 左子樹(shù)
      right: null, // 右子樹(shù)
      parent: null, // 父節(jié)點(diǎn)
      val,
    }
  }
  /**
   * 創(chuàng)建要給插入節(jié)點(diǎn)的方法
   * @param {number | array[number]} val
   * @returns
   */
  insertNode(val) {
    const that = this
    // 允許接受一個(gè)數(shù)組，批量插入
    if (Object.prototype.toString.call(val) === '[object Array]') {
      val.forEach(function (v) {
        that.insertNode(v)
      })
      return
    }

    if (typeof val !== 'number') throw Error('插入的值不是一個(gè)數(shù)字')

    const newNode = this.Node(val)
    if (this.root) {
      // 根節(jié)點(diǎn)非空
      this.#insertNode(this.root, newNode)
    } else {
      // 根節(jié)點(diǎn)是空的，直接創(chuàng)建
      this.root = newNode
    }
  }

  /**
   * 私有方法，插入節(jié)點(diǎn)
   * @param {Object{Node}} root
   * @param {Object{Node}} newNode
   */
  #insertNode(root, newNode) {
    if (newNode.val < root.val) {
      // 新節(jié)點(diǎn)比根節(jié)點(diǎn)小，左子樹(shù)
      if (root.left === null) {
        // 如果左子樹(shù)上沒(méi)有內(nèi)容，則直接插入，如果有，尋找下一個(gè)插入位置
        root.left = newNode
        root.left.parent = root
      } else {
        this.#insertNode(root.left, newNode)
      }
    } else {
      // 新節(jié)點(diǎn)比根節(jié)點(diǎn)大，右子樹(shù)
      if (root.right === null) {
        root.right = newNode
        root.right.parent = root
      } else {
        this.#insertNode(root.right, newNode)
      }
    }
  }
  /**
   * 根據(jù) val 查找節(jié)點(diǎn)
   * @param {number} val 需要查找的數(shù)值
   * @returns 如果找到返回當(dāng)前節(jié)點(diǎn)的引用，如果未找到返回 undefined
   */
  find(val) {
    if (typeof val !== 'number') throw Error('插入的值不是一個(gè)數(shù)字')
    let node = this.root
    while (node) {
      if (node.val < val) {
        // 進(jìn)入右子樹(shù)
        node = node.right
      } else if (node.val > val) {
        // 進(jìn)入左子樹(shù)
        node = node.left
      } else {
        return node
      }
    }
    return
  }
  // /**
  //  * 根據(jù) val 查找節(jié)點(diǎn) 遞歸版
  //  * @param {number} val 需要查找的數(shù)值
  //  * @returns 如果找到返回當(dāng)前節(jié)點(diǎn)的引用，如果未找到返回 undefined
  //  */
  // find(val) {
  //   if (typeof val !== 'number') throw Error('插入的值不是一個(gè)數(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é)點(diǎn)
    const cur = this.find(val)
    if (!val) return false // 未找到需要?jiǎng)h除的節(jié)點(diǎn)

    if (!cur.left && !cur.right) {
      // 1. 當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)的情況
      this.#removeLeaf(cur)
    } else if (cur.left && cur.right) {
      // 2. 當(dāng)前節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)
      // 2.1 找到當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)
      const successorNode = this.#minNode(cur.right)
      // 2.2 將后繼節(jié)點(diǎn)的值賦值給當(dāng)前值
      cur.val = successorNode.val
      if (!successorNode.left && !successorNode.right) {
        // 2.3 后繼節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接刪除
        this.#removeLeaf(successorNode)
      } else {
        // 2.4 后繼節(jié)點(diǎn)不是葉子節(jié)點(diǎn)
        // 2.4.1記錄該節(jié)點(diǎn)的子節(jié)點(diǎn)，
        let child =
          successorNode.left !== null ? successorNode.left : successorNode.right
        // 2.4.2 記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)
        let parent = successorNode.parent
        // 2.4.3 如果當(dāng)前父節(jié)點(diǎn)的left是后繼結(jié)點(diǎn)，則把后繼結(jié)點(diǎn)的父節(jié)點(diǎn)的left指向后繼結(jié)點(diǎn)的子節(jié)點(diǎn)
        if (parent.left === successorNode) {
          parent.left = child
        } else {
          // 2.4.4 如果不是，則讓父節(jié)點(diǎn)的right指向后繼結(jié)點(diǎn)的子節(jié)點(diǎn)
          parent.right = child
        }
        // 2.4.5 修改子節(jié)點(diǎn)的parent指針
        child.parent = parent
      }

      // 2.3 刪除后繼節(jié)點(diǎn)
    } else {
      // 記錄當(dāng)前節(jié)點(diǎn)的是否是父節(jié)點(diǎn)的左子樹(shù)
      const isLeft = cur.val < cur.parent.val
      // 3. 僅存在一個(gè)子節(jié)點(diǎn)
      if (cur.left) {
        // 3.1 當(dāng)前節(jié)點(diǎn)存在左子樹(shù)
        cur.parent[isLeft ? 'left' : 'right'] = cur.left
        cur.left.parent = cur.parent
      } else if (cur.right) {
        // 3.2 當(dāng)前節(jié)點(diǎn)存在右子樹(shù)
        cur.parent[isLeft ? 'left' : 'right'] = cur.right
        cur.right.parent = cur.parent
      }
    }
  }
  // 刪除葉子節(jié)點(diǎn)
  #removeLeaf(node) {
    if (!node) return
    const parent = node.parent
    if (node.val < parent.val) {
      // 當(dāng)前要?jiǎng)h除的葉子節(jié)點(diǎn)是左節(jié)點(diǎn)
      parent.left = null
    } else {
      // 當(dāng)前要?jiǎng)h除的葉子節(jié)點(diǎn)是右節(jié)點(diǎn)
      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
  }
  // 中序遍歷這個(gè)樹(shù)
  static inorder(root) {
    if (!root) return
    const result = []
    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()
      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 ]