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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

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

目錄

前言

什么是二叉搜索樹

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

二叉搜索樹的操作

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

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

刪除二叉搜索樹的某個節(jié)點

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

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

實現(xiàn)代碼

完整代碼

總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线 免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

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

目錄

前言

什么是二叉搜索樹

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

二叉搜索樹的操作

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

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

刪除二叉搜索樹的某個節(jié)點

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

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

實現(xiàn)代碼

完整代碼

總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕