詳解BST(二叉排序樹)_ZenDei技術網路在線

查找基本分類如下： 1. 線性表的查找順序查找折半查找分塊查找 2. 樹表的查找二叉排序樹平衡二叉樹 B樹 B+樹 3. 散列表的查找今天介紹二叉排序樹。二叉排序樹 ( Binary Sort Tree ) 又稱為二叉查找樹，它是一種對排序和查找都很有用的特殊二叉樹。 1. 二 ...

查找基本分類如下：

線性表的查找
- 順序查找
- 折半查找
- 分塊查找
樹表的查找
- 二叉排序樹
- 平衡二叉樹
- B樹
- B+樹
散列表的查找

今天介紹二叉排序樹。

二叉排序樹 ( Binary Sort Tree ) 又稱為二叉查找樹，它是一種對排序和查找都很有用的特殊二叉樹。

1. 二叉排序樹的定義

二叉排序樹是具有如下性質的二叉樹：

若它的左子樹不為空，則左子樹上所有節點的值均小於它的根節點的值。
若它的右子樹不為空，則右子樹上的所有節點的值均大於它的根節點的值。
它的左子樹、右子樹也均為二叉排序樹。

二叉排序樹是遞歸定義的。所以可以得出二叉排序樹的一個重要性質：中序遍歷一棵二叉排序樹時可以得到一個節點值遞增的有序序列。

若中序遍歷上圖二叉樹，則可以得到一個按數值大小排序的遞增序列：3，12，24，37，45，53，61，78，90，100

2. 創建一個二叉排序樹

二叉樹是由節點構成，所以我們需要一個Node類，node實例保存當前節點的數據，以及保存左右節點的指針，還可以輸出當前節點數據。

  class Node {
    constructor(data, leftNode, rightNode) {
      this.data = data
      this.leftNode = leftNode
      this.rightNode = rightNode
    }
    print () {
      return this.data
    }
  }

二叉排序樹有一個根節點，根節點存儲了根節點的數據，左右子節點的地址，還有相應的實例方法，提供插入、遍歷、查找等操作。

  class BST {
    constructor() {
      this.root = null
    }
    
    insert (data) {...}
    preOrder () {...}
    inOrder () {...}
    postOrder () {...}
    ...
  }

3. 二叉排序樹的插入

我們要根據二叉排序樹樹的性質來決定insert的data的位置

若當前是一棵空樹，則將插入的數據作為根節點
若不是空樹，迴圈遍歷二叉排序樹的節點
- 若當前遍歷的節點的data大於要插入的data，則將下一個要遍歷的節點賦值為當前遍歷的節點的左節點，進行下一層迴圈，直到葉子節點為止，將data作為葉子節點的左節點
- 若當前遍歷的節點的data小於要插入的data，則將下一個要遍歷的節點賦值為當前遍歷的節點的右節點，進行下一層迴圈，直到葉子節點為止，將data作為葉子節點的右節點

還是代碼直觀

  function insert (data) {
    if (this.find(data)) {
        return
    }

    var node = new Node(data, null, null)
    if (this.root == null) {
      this.root = node
    } else {
      var currentNode = this.root
      var parentNode
      while (currentNode) {
        parentNode = currentNode
        if (data < currentNode.data) {
          currentNode = currentNode.leftNode
          if (currentNode == null) {
            parentNode.leftNode = node
            break
          }
        } else {
          currentNode = currentNode.rightNode
          if (currentNode == null) {
            parentNode.rightNode = node
            break
          }
        }
      }
    }
  }

4. 遞歸遍歷二叉排序樹

簡單，貼下代碼，重點在非遞歸遍歷

  class BST {
    constructor() {
      this.data = null
    }
    
    preOrder () {
      preOrderFn(this.root)
    }
    inOrder () {
      inOrderFn(this.root)
    }
    postOrder () {
      postOrderFn(this.root)
    }
  }
  
  function preOrderFn (node) {
    if (node) {
      console.log(node.print())
      preOrderFn(node.leftNode)
      preOrderFn(node.rightNode)
    }
  }
  function inOrderFn (node) {
    if (node) {
      inOrderFn(node.leftNode)
      console.log(node.print())
      inOrderFn(node.rightNode)
    }
  }
  function postOrderFn (node) {
    postOrderFn (node.leftNode)
    postOrderFn (node.rightNode)
    console.log(node.print())
  }

5.非遞歸中序遍歷二叉排序樹

中序遍歷的非遞歸演算法最簡單，後序遍歷的非遞歸演算法最難，所以先介紹中序遍歷。

非遞歸遍歷一定要用到棧。

  class Stack {
    constructor() {
      this.arr = []
    }
    pop () {
      return this.arr.shift()
    }
    push (data) {
      this.arr.unshift(data)
    }
    isEmpty () {
      return this.arr.length == 0
    }
  }

我們一點一點寫想，中序遍歷，肯定是要先找到左子樹最下麵的節點吧？想不明白就好好想想。

  function inOrderWithoutRecursion (root) {
    var parentNode = root
    var stack = new Stack()

    // 一直遍歷到左子樹的最下麵，將一路遍歷過的節點push進棧中
    while (parentNode) {
      stack.push(parentNode)
      parentNode = parentNode.leftNode
    }
  }

這裡為什麼要先讓遍歷過的節點入棧呢？中序遍歷，先遍歷左節點，再根節點，最後是右節點，所以我們需要保存一下根節點，以便接下來訪問根節點和藉助根節點來訪問右節點。

1.現在我們已經到了左子樹的最下麵的節點了，這時它是一個葉子節點。通過遍歷，它也在棧中而且是在棧頂，所以就可以訪問它的data了，然後訪問根節點的data，最後將parentNode指向根節點的右節點，訪問右節點。

如圖

按我上面說的話，代碼應該是這個樣子的。

    parentNode = stack.pop()
    console.log(parentNode.data)
    parentNode = stack.pop()
    console.log(parentNode.data)
    parentNode = parentNode.rightNode

2.但是還有一種情況呢？如果左子樹最下麵的節點沒有左節點，只有右節點呢？也就是說如果這個節點不是葉子節點呢？那麼就直接訪問根節點的data，再將parentNode指向根節點的右節點，訪問右節點。對吧？

如圖

那現在代碼又成了這個樣子。

    parentNode = stack.pop()
    console.log(parentNode.data)
    parentNode = parentNode.rightNode

那麼怎麼統一格式呢？之前我們說到當parentNode不存在時就需要出棧了，那我們可以把左子樹最下麵的節點也就是第一種情況時的葉子節點看作一個根節點，繼續訪問它的右節點，因為它是一個葉子節點，所以右節點為null，所以就又執行了一次出棧操作。這時候代碼就可以統一了，好好想一想，有點抽象。

統一後的代碼就是情況2的代碼

    parentNode = stack.pop()
    console.log(parentNode.data)
    parentNode = parentNode.rightNode

如果上面的都理解了的話，就很簡單了，貼代碼

  function inOrderWithoutRecursion (root) {
    if (!root)
      return

    var parentNode = root
    var stack = new Stack()

    while (parentNode || !stack.isEmpty()) {

      // 一直遍歷到左子樹的最下麵，將一路遍歷過的節點push進棧中
      while (parentNode) {
        stack.push(parentNode)
        parentNode = parentNode.leftNode
      }
      // 當parentNode為空時，說明已經達到了左子樹的最下麵，可以出棧操作了
      if (!stack.isEmpty()) {
        parentNode = stack.pop()
        console.log(parentNode.data)
        // 進入右子樹，開始新一輪迴圈
        parentNode = parentNode.rightNode
      }
    }
  }

優化

  function inOrderWithoutRecursion (root) {
    if (!root)
      return

    var parentNode = root
    var stack = new Stack()

    while (parentNode || !stack.isEmpty()) {

      // 一直遍歷到左子樹的最下麵，將一路遍歷過的節點push進棧中
      if (parentNode) {
        stack.push(parentNode)
        parentNode = parentNode.leftNode
      }
      // 當parentNode為空時，說明已經達到了左子樹的最下麵，可以出棧操作了
      else {
        parentNode = stack.pop()
        console.log(parentNode.data)
        // 進入右子樹，開始新一輪迴圈
        parentNode = parentNode.rightNode
      }
    }
  }

6.非遞歸先序遍歷二叉排序樹

有了中序遍歷的基礎，掌握先序遍歷就不難了吧？先序就是到了根節點就列印出來，然後將節點入棧，然後左子樹，基本與中序類似，想想就明白。

直接貼最終代碼

  function PreOrderWithoutRecursion (root) {
    if (!root)
      return

    var parentNode = root
    var stack = new Stack()

    while (parentNode || !stack.isEmpty()) {

      // 一直遍歷到左子樹的最下麵，一邊列印data,將一路遍歷過的節點push進棧中
      if (parentNode) {
        console.log(parentNode.data)
        stack.push(parentNode)
        parentNode = parentNode.leftNode
      }
      // 當parentNode為空時，說明已經達到了左子樹的最下麵，可以出棧操作了
      else {
        parentNode = stack.pop()
        // 進入右子樹，開始新一輪迴圈
        parentNode = parentNode.rightNode
      }
    }
  }

7.非遞歸後序遍歷二叉排序樹

後序遍歷中，一個根節點被訪問的前提是，右節點不存在或者右節點已經被訪問過

後序遍歷難點在於：判斷右節點是否被訪問過。

如果右節點不存在或者右節點已經被訪問過，則訪問根節點
如果不符合上述條件，則跳過根節點，去訪問右節點

我們可以使用一個變數來保存上一個訪問的節點，如果是當前訪問的節點的右節點就是上一個訪問過的節點，證明右節點已經被訪問過了，可以去訪問根節點了。

這裡需要註意的一點是：節點Node是一個對象，如果用==比較的話，返回的永遠是false，所以我們比較的是node的data屬性。

代碼在這裡

function PostOrderWithoutRecursion (root) {
    if (!root)
      return

    var parentNode = root
    var stack = new Stack()
    var lastVisitNode = null

    while (parentNode || !stack.isEmpty()) {
      if (parentNode) {
        stack.push(parentNode)
        parentNode = parentNode.leftNode
      }
      else {
        parentNode = stack.pop()
        // 如果當前節點沒有右節點或者是右節點被訪問過，則訪問當前節點
        if (!parentNode.rightNode || parentNode.rightNode.data == lastVisitNode.data) {
          console.log(parentNode.data)
          lastVisitNode = parentNode
        }
        // 訪問右節點
        else {
          stack.push(parentNode)
          parentNode = parentNode.rightNode
          while (parentNode) {
            parentNode = parentNode.leftNode
          }
        }
      }
    }
  }

8.二叉排序樹的查找

寫查找是為了刪除節點做準備。

1.查找給定值

很簡單，根據要查找的數據和根節點對比，然後遍歷左子樹或者右子樹就好了。

  find (data) {
    var currentNode = this.root
    while (currentNode) {
      if (currentNode.data == data) {
        return currentNode
      } else if (currentNode.data > data) {
        currentNode = currentNode.leftNode
      } else {
        currentNode = currentNode.rightNode
      }
    }
    return null
  }

2.查找最大值

很簡單，直接找到最右邊的節點就是了

  getMax () {
    var currentNode = this.root
    while (currentNode.rightNode) {
      currentNode = currentNode.rightNode
    }
    return currentNode.data
  }

3.查找最小值

一樣

  getMax () {
    var currentNode = this.root
    while (currentNode.leftNode) {
      currentNode = currentNode.leftNode
    }
    return currentNode.data
  }

9.二叉排序樹的刪除

刪除很重要，說下邏輯：

首先從二叉排序樹的根節點開始查找關鍵字為key的待刪節點，如果樹中不存在此節點，則不做任何操作；

否則，假設待刪節點為delNode，其父節點為delNodeParent，delNodeLeft和delNodeRight分別為待刪節點的左子樹、右子樹。

可設delNode是delNodeParent的左子樹（右子樹情況類似）。分下麵三種情況考慮

1.若delNode為葉子節點，即delNodeLeft和delNodeRight均為空。刪除葉子節點不會破壞整棵樹的結構，則只需修改delNodeParent的指向即可。

delNodeParent.leftNode = null

2.若delNode只有左子樹delNodeLeft或者只有右子樹delNodeRight，此時只要令delNodeLeft或者delNodeRight直接成為待刪節點的父節點的左子樹即可。

delNodeParent.leftNode = delNode.leftNode
（或者delNodeParent.leftNode = delNode.rightNode）

3.若delNode左子樹和右子樹均不為空，刪除delNode之後，為了保持其他元素之間的相對位置不變，可以有兩種處理辦法

令delNode的左子樹為delNodeParent的左子樹，而delNode的右子樹為delNode的左子樹中序遍歷的最後一個節點（令其為leftBigNode，即左子樹中最大的節點，因為要符合二叉樹的性質，仔細想一想）的右子樹

delNodeParent.leftNode = delNode.leftNode
leftBigNode.rightNode = delNode.rightNode
令delNode的直接前驅（也就是左子樹中最大的節點，令其為leftBigNode）替代delNode，然後再從二叉排序樹中刪除它的直接前驅（或直接後繼，原理類似）。當以直接前驅替代delNode時，由於leftBigNode只有左子樹（否則它就不是左子樹中最大的節點），則在刪除leftBigNode之後，只要令leftBigNode的左子樹為雙親leftBigNodeParent的右子樹即可。

delNode.data = leftBigNode.data
leftBigNodeParent.rightNode = leftBigNode.leftNode

畫了三張圖片來理解下：

刪除節點P之前：

第一種方式刪除後：

第二種方式刪除後：

顯然，第一種方式可能增加數的深度，而後一種方法是以被刪節點左子樹中最大的節點代替被刪的節點，然後從左子樹中刪除這個節點。此節點一定沒有子樹（同上，否則它就不是左子樹中最大的節點），這樣不會增加樹的高度，所以常採用這種方案，下麵的演算法也使用這種方案。

代碼註釋很清除，好好理解下，這塊真的不好想

  deleteNode (data) {
    /********************** 初始化 **************************/
    var delNode = this.root,
        delNodeParent = null
    /************ 從根節點查找關鍵字為data的節點 ***************/
    while (delNode) {
      if (delNode.data == data) break
      delNodeParent = delNode // 記錄被刪節點的雙親節點
      if (delNode.data > data) delNode = delNode.leftNode // 在被刪節點左子樹中繼續查找
      else delNode = delNode.rightNode  // 在被刪節點的右子樹中繼續查找
    }
    if (!delNode) { // 沒找到
      return 
    }
    /**
     * 三種情況
     * 1.被刪節點既有左子樹，又有右子樹
     * 2.被刪節點只有右子樹
     * 3.被刪節點只有左子樹
    **/
    var leftBigNodeParent = delNode 
    if (delNode.leftNode && delNode.rightNode) { // 被刪節點左右子樹都存在
      var leftBigNode = delNode.leftNode
      while (leftBigNode.rightNode) { // 在被刪節點的左子樹中尋找其前驅節點，即最右下角的節點，也就是左子樹中數值最大的節點
        leftBigNodeParent = leftBigNode
        leftBigNode = leftBigNode.rightNode // 走到右盡頭
      }
      delNode.data = leftBigNode.data // 令被刪節點的前驅替代被刪節點
      if (leftBigNodeParent.data != delNode.data) {
        leftBigNodeParent.rightNode = leftBigNode.leftNode // 重接被刪節點的前驅的父節點的右子樹
      } else {
        leftBigNodeParent.leftNode = leftBigNode.leftNode // 重接被刪節點的前驅的父節點的左子樹
      }
    } else if (!delNode.leftNode) {
      delNode = delNode.rightNode // 若被刪節點沒有左子樹，只需重接其右子樹
    } else if (!delNode.rightNode) {
      delNode = delNode.leftNode // 若被刪節點沒有右子樹，只需重接其左子樹
    }
    /********* 將被刪節點的子樹掛接到其父節點的相應位置 **********/
    if (!delNodeParent) { 
      this.root = delNode // 若被刪節點是根節點
    } else if (leftBigNodeParent.data == delNodeParent.data) {
      delNodeParent.leftNode = delNode // 掛接到父節點的左子樹位置
    } else {
      delNodeParent.rightNode = delNode // 掛接到父節點的右子樹位置
    }
  }

10.其他方法

1.複製二叉排序樹

這一塊我先用了遞歸，後來想到，BST是個對象，直接深度克隆就好了。。。不說了

2.二叉排序樹深度

遞歸遞歸遞歸

  class BST {
    constructor() {
      this.root = null
    }
    depth () {
      return depthFn(this.root)
    }
  }

  function depthFn (node) {
    if (!node) {
      return 0
    } else {
      var leftDepth = depthFn(node.leftNode)
      var rightDepth = depthFn(node.rightNode)
      if (leftDepth > rightDepth)
        return (leftDepth + 1)
      else
        return (rightDepth + 1)
    }
  }

3.二叉排序樹節點個數

遞歸遞歸遞歸

  class BST {
    constructor() {
      this.root = null
    }
    nodeCount () {
      return nodeCount(this.root)
    }
  }
  function nodeCount(node) {
    if (!node) {
      return 0
    } else {
      return nodeCount(node.leftNode) + nodeCount(node.rightNode) + 1
    }
  }