使用JavaScript怎么實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)

今天就跟大家聊聊有關(guān)使用JavaScript怎么實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

JavaScript可以做什么

1.可以使網(wǎng)頁(yè)具有交互性，例如響應(yīng)用戶點(diǎn)擊，給用戶提供更好的體驗(yàn)。 2.可以處理表單，檢驗(yàn)用戶的輸入，并提供及時(shí)反饋節(jié)省用戶時(shí)間。 3.可以根據(jù)用戶的操作，動(dòng)態(tài)的創(chuàng)建頁(yè)面。 4使用JavaScript可以通過(guò)設(shè)置cookie存儲(chǔ)在瀏覽器上的一些臨時(shí)信息。

二叉搜索樹(shù)是一顆二叉樹(shù), 可以為空；如果不為空，滿足以下性質(zhì)：

• 非空左子樹(shù)的所有鍵值小于其根結(jié)點(diǎn)的鍵值

• 非空右子樹(shù)的所有鍵值大于其根結(jié)點(diǎn)的鍵值

• 也就是左結(jié)點(diǎn)值想<根結(jié)點(diǎn)值<右節(jié)點(diǎn)值

• 左、右子樹(shù)本身也都是二叉搜索樹(shù)

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

insert(key)：向樹(shù)中插入一個(gè)新的鍵

search(key)：在樹(shù)中查找一個(gè)鍵，如果結(jié)點(diǎn)存在，則返回true；如果不存在，則返回false

inOrderTraverse：通過(guò)中序遍歷方式遍歷所有結(jié)點(diǎn)

preOrderTraverse：通過(guò)先序遍歷方式遍歷所有結(jié)點(diǎn)

postOrderTraverse：通過(guò)后序遍歷方式遍歷所有結(jié)點(diǎn)

min：返回樹(shù)中最小的值/鍵

max：返回樹(shù)中最大的值/鍵

remove(key)：從樹(shù)中移除某個(gè)鍵

先序遍歷

• ①訪問(wèn)根結(jié)點(diǎn)

• ②先序遍歷其左子樹(shù)

• ③先序遍歷其右子樹(shù)
  

中序遍歷

①中序遍歷其左子樹(shù)
②訪問(wèn)根結(jié)點(diǎn)
③中序遍歷其右子樹(shù)

后序遍歷

①后序遍歷其左子樹(shù)
②后序遍歷其右子樹(shù)
③訪問(wèn)根結(jié)點(diǎn)

JavaScript 代碼實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)

// 創(chuàng)建BinarySearchTree
function BinarySerachTree() {
  // 創(chuàng)建節(jié)點(diǎn)構(gòu)造函數(shù)
  function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }

  // 保存根的屬性
  this.root = null

  // 二叉搜索樹(shù)相關(guān)的操作方法
  // 向樹(shù)中插入數(shù)據(jù)
  BinarySerachTree.prototype.insert = function (key) {
    // 1.根據(jù)key創(chuàng)建對(duì)應(yīng)的node
    var newNode = new Node(key)

    // 2.判斷根節(jié)點(diǎn)是否有值
    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }

  BinarySerachTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) { // 1.準(zhǔn)備向左子樹(shù)插入數(shù)據(jù)
      if (node.left === null) { // 1.1.node的左子樹(shù)上沒(méi)有內(nèi)容
        node.left = newNode
      } else { // 1.2.node的左子樹(shù)上已經(jīng)有了內(nèi)容
        this.insertNode(node.left, newNode)
      }
    } else { // 2.準(zhǔn)備向右子樹(shù)插入數(shù)據(jù)
      if (node.right === null) { // 2.1.node的右子樹(shù)上沒(méi)有內(nèi)容
        node.right = newNode
      } else { // 2.2.node的右子樹(shù)上有內(nèi)容
        this.insertNode(node.right, newNode)
      }
    }
  }

  // 獲取最大值和最小值
  BinarySerachTree.prototype.min = function () {
    var node = this.root
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }

  BinarySerachTree.prototype.max = function () {
    var node = this.root
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }

  // 搜搜特定的值
  /*
  BinarySerachTree.prototype.search = function (key) {
    return this.searchNode(this.root, key)
  }

  BinarySerachTree.prototype.searchNode = function (node, key) {
    // 1.如果傳入的node為null那么, 那么就退出遞歸
    if (node === null) {
      return false
    }

    // 2.判斷node節(jié)點(diǎn)的值和傳入的key大小
    if (node.key > key) { // 2.1.傳入的key較小, 向左邊繼續(xù)查找
      return this.searchNode(node.left, key)
    } else if (node.key < key) { // 2.2.傳入的key較大, 向右邊繼續(xù)查找
      return this.searchNode(node.right, key)
    } else { // 2.3.相同, 說(shuō)明找到了key
      return true
    }
  }
  */
  BinarySerachTree.prototype.search = function (key) {
    var node = this.root
    while (node !== null) {
      if (node.key > key) {
        node = node.left
      } else if (node.key < key) {
        node = node.right
      } else {
        return true
      }
    }
    return false
  }

  // 刪除節(jié)點(diǎn)
  BinarySerachTree.prototype.remove = function (key) {
    // 1.獲取當(dāng)前的node
    var node = this.root
    var parent = null

    // 2.循環(huán)遍歷node
    while (node) {
      if (node.key > key) {
        parent = node
        node = node.left
      } else if (node.key < key) {
        parent = node
        node = node.right
      } else {
        if (node.left == null && node.right == null) {

        }
      }
    }
  }

  BinarySerachTree.prototype.removeNode = function (node, key) {
    // 1.如果傳入的node為null, 直接退出遞歸.
    if (node === null) return null

    // 2.判斷key和對(duì)應(yīng)node.key的大小
    if (node.key > key) {
      node.left = this.removeNode(node.left, key)

    }
  }

  // 刪除結(jié)點(diǎn)
  BinarySerachTree.prototype.remove = function (key) {
    // 1.定義臨時(shí)保存的變量
    var current = this.root
    var parent = this.root
    var isLeftChild = true

    // 2.開(kāi)始查找節(jié)點(diǎn)
    while (current.key !== key) {
      parent = current
      if (key < current.key) {
        isLeftChild = true
        current = current.left
      } else {
        isLeftChild = false
        current = current.right
      }

      // 如果發(fā)現(xiàn)current已經(jīng)指向null, 那么說(shuō)明沒(méi)有找到要?jiǎng)h除的數(shù)據(jù)
      if (current === null) return false
    }

    // 3.刪除的結(jié)點(diǎn)是葉結(jié)點(diǎn)
    if (current.left === null && current.right === null) {
      if (current == this.root) {
        this.root == null
      } else if (isLeftChild) {
        parent.left = null
      } else {
        parent.right = null
      }
    }

    // 4.刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    else if (current.right === null) {
      if (current == this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    } else if (current.left === null) {
      if (current == this.root) {
        this.root = current.right
      } else if (isLeftChild) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    }

    // 5.刪除有兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)
    else {
      // 1.獲取后繼節(jié)點(diǎn)
      var successor = this.getSuccessor(current)

      // 2.判斷是否是根節(jié)點(diǎn)
      if (current == this.root) {
        this.root = successor
      } else if (isLeftChild) {
        parent.left = successor
      } else {
        parent.right = successor
      }

      // 3.將刪除節(jié)點(diǎn)的左子樹(shù)賦值給successor
      successor.left = current.left
    }

    return true
  }

  // 找后繼的方法
  BinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1.使用變量保存臨時(shí)的節(jié)點(diǎn)
    var successorParent = delNode
    var successor = delNode
    var current = delNode.right // 要從右子樹(shù)開(kāi)始找

    // 2.尋找節(jié)點(diǎn)
    while (current != null) {
      successorParent = successor
      successor = current
      current = current.left
    }

    // 3.如果是刪除圖中15的情況, 還需要如下代碼
    if (successor != delNode.right) {
      successorParent.left = successor.right
      successor.right = delNode.right
    }
  }

  // 遍歷方法
  //handler為回調(diào)函數(shù)
  // 先序遍歷
  BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
    if (node !== null) {
      handler(node.key)
      this.preOrderTranversalNode(node.left, handler)
      this.preOrderTranversalNode(node.right, handler)
    }
  }

  // 中序遍歷
  BinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      this.inOrderTraversalNode(node.left, handler)
      handler(node.key)
      this.inOrderTraversalNode(node.right, handler)
    }
  }

  // 后續(xù)遍歷
  BinarySerachTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      this.postOrderTraversalNode(node.left, handler)
      this.postOrderTraversalNode(node.right, handler)
      handler(node.key)
    }
  }
  
  /*
  // 測(cè)試遍歷結(jié)果(inOrderTraversal可以替換成別的遍歷方式)
    resultString = ""
    bst.inOrderTraversal(function (key) {
      resultString += key + " "
    })
    alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 
   */
}

看完上述內(nèi)容，你們對(duì)使用JavaScript怎么實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。