摘要：二叉搜索樹是二叉樹的一種，其特征是左側子節點存儲比父節點小的值，右側子節點存儲比父節點大或等于父節點的值。實現和這個兩個方法其實挺簡單的，最小的節點就在二叉搜索樹的最左反之，最大的就在最右。

本系列所有文章：
第一篇文章：學習數據結構與算法之棧與隊列
第二篇文章：學習數據結構與算法之鏈表
第三篇文章：學習數據結構與算法之集合
第四篇文章：學習數據結構與算法之字典和散列表
第五篇文章：學習數據結構與算法之二叉搜索樹

二叉樹是一種非線性數據結構，其中的每個元素我們稱為節點，二叉樹中每個節點最多只能有兩個子節點；沒有父節點的節點稱為根節點，沒有子節點的節點稱為葉節點。二叉搜索樹是二叉樹的一種，其特征是左側子節點存儲比父節點小的值，右側子節點存儲比父節點大（或等于父節點）的值。下圖就是一顆典型的二叉搜索樹:

二叉搜索樹的節點，我們用類似雙向鏈表的方式存儲節點（都包含兩個對其他節點的引用），但是這里兩個引用指向的分別是左右兩個子節點。

function BinarySearchTree () {
  // 二叉樹的鍵
  var Node = function (key) {
    // 鍵值
    this.key = key
    // 左節點
    this.left = null
    // 右節點
    this.right = null
  }
  
  // 根節點
  var root = null
}

二叉搜索樹需要實現以下方法：

insert(key)：向樹中插入一個新的鍵

search(key)：在樹中查找一個鍵，如果節點存在返回tue，否則返回false

inOrderTraverse：通過中序遍歷方式遍歷所有節點

preOrderTraverse：通過先序遍歷方式遍歷節點

postOrderTraverse：通過后序遍歷方式遍歷所有節點

min：返回樹中最小的值

max：返回樹中最大的值

remove(key)：從樹中移除某個鍵

注意：本文中很多地方使用了遞歸的方法，如果不了解遞歸，可以先看看這個知乎問題-遞歸

// 用于插入節點
var insertNode = function (node, newNode) {
  // 在二叉搜索樹中，比父節點小的值存在左側節點，大于等于父節點的存在右側節點
  // 若要插入一個節點（根節點已存在），首先與根節點比大小，若比根節點小則應插入根節點的左側
  // 如果左側已存在節點，則遞歸調用函數，將左側節點傳入遞歸函數作為當前節點
  // 如果插入的節點比當前節點大且當前節點右側為空，則插入右側
  // 如果插入節點比根節點大，原理同上
  if (newNode.key < node.key) {
    if (node.left === null) {
      node.left = newNode
    } else {
      insertNode(node.left, newNode)
    }
  } else {
    if (node.right === null) {
      node.right = newNode
    } else {
      insertNode(node.right, newNode)
    }
  }
}

// 插入
this.insert = function (key) {
  var node = new Node(key)

  if (root === null) {
    root = node
  } else {
    insertNode(root, node)
  }
}

這里同樣借助一個輔助函數使用，輔助函數同樣是用了遞歸，簡單比較輸入的key與當前節點的key，當相等時（意味著找到了目標節點）就返回true；當查找完最末端的節點時，即傳入的node為null時，就返回false，表示未找到。

有人可能會懷疑，這樣真的找到嗎？實際上，由于二叉搜索樹子節點“左小右大”的性質，一個特定的值在二叉搜索樹中的大致位置是可預見的（即使是插入那個值也不會跑出那個范圍）。所以僅僅通過簡單的比較key就能在某個范圍中找到目標節點，而且這種方法不用遍歷整棵樹去找，非常節省性能。

var searchNode = function (node, key) {
  if (node === null) {
    false
  }

  if (key < node.key) {
    return searchNode(node.left, key)
  } else if (key > node.key) {
    return searchNode(node.right, key)
  } else {
    return true
  }
}

// 查找節點
this.search = function (key) {
  return searchNode(root, key)
}

接下來就是三個遍歷方法，先從中序遍歷開始，其作用是按順序（從小到大）訪問整棵樹的所有節點，也就是常見的升序排序。

其實這三種遍歷并沒有那么復雜，簡單地觀察一下回調函數（也就是訪問key）的位置，就能看出來是哪種排序。

var inOrderTraverseNode = function (node, callback) {
  if (node !== null) { // 停止遞歸的條件
    inOrderTraverseNode(node.left, callback)
    callback(node.key)
    inOrderTraverseNode(node.right, callback)
  }
}

// 中序遍歷
this.inOrderTraverse = function (callback) {
  inOrderTraverseNode(root, callback)
}

var preOrderTraverseNode = function (node, callback) {
  if (node !== null) {
    callback(node.key)
    preOrderTraverseNode(node.left, callback)
    preOrderTraverseNode(node.right, callback)
  }
}

// 先序遍歷
this.preOrderTraverse = function (callback) {
  preOrderTraverseNode(root, callback)
}

var postOrderTraverseNode = function (node, callback) {
  if (node !== null) {
    postOrderTraverseNode(node.left, callback)
    postOrderTraverseNode(node.right, callback)
    callback(node.key)
  }
}

// 后序遍歷
this.postOrderTraverse = function (callback) {
  postOrderTraverseNode(root, callback)
}

這里先停一下：的確看回調函數就能知道這是哪種遍歷，但是這些函數遞歸理解起來確實有點困難，這里我建議在重復的大問題面前先拆成小問題來看：

請看這個最簡單的二叉樹

如果現在先序遍歷這個二叉樹，它的順序應該是M -> H -> Z；中序遍歷的順序是H -> M -> Z；后序遍歷是：H -> Z -> M

那么再看下面這棵大樹的中序遍歷就會好理解了：先從根節點左側子樹開始遍歷，左側子樹里面又有小左側子樹，里面最小的由3，5，6組成的子樹就和上面最簡單的二叉樹一樣了。這時遍歷從3開始，以正常的中序遍歷順序3 -> 5 -> 6。當遍歷完6之后我們可以將這個小的子樹看成一個整體，這個整體和上面的父節點7以及右邊的子樹也組成了一個簡單的二叉樹結構，然后正常遍歷7 -> 右側子樹，右側子樹中依舊按照中序遍歷的順序：8 -> 9 -> 10，按此順序不斷遍歷完所有的節點。

這個兩個方法其實挺簡單的，最小的節點就在二叉搜索樹的最左；反之，最大的就在最右。

var minNode = function(node) {
  // 如果node存在，則開始搜索。能避免樹的根節點為Null的情況
  if (node) {
    // 只要樹的左側子節點不為null，則把左子節點賦值給當前節點。
    // 若左子節點為null，則該節點肯定為最小值。
    while (node && node.left !== null) {
      node = node.left
    }
    return node.key
  }
  return null
}

var maxNode = function(node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right
    }
    return node.key
  }
  return null
}

// 找到最小節點
this.min = function () {
  return minNode(root)
}

// 找到最大節點
this.max = function () {
  return maxNode(root)
}

好了，現在剩下最后一個方法了，先深吸一口氣。。。

接下來實現的方法號稱全書最復雜的方法，鑒于本人目前水平有限，我只能將自己看懂的思路寫出來，如果講得不好大家可以去看原書《學習JavaScript數據結構與算法》。

下面進入正題：

移除二叉搜索樹中的一個節點需要考慮三種情況：

刪除的是葉節點（沒有子節點的節點）

刪除的節點有一側子節點

刪除的節點有兩側子節點

還是老原則，化繁為簡。

先看第一個比較簡單的：既然它沒有子節點，那就先找到它，再直接將它與父節點的聯系切斷就行了；

第二個就稍微復雜一點：你得先把它刪掉，然后把它的子節點接到它的父節點上去；

第三個最復雜：你不能直接刪掉它，你應該在它的右側子樹里面找到最小的那個節點把它替換掉，然后為防止重復，把替換它的節點刪掉就萬事大吉了。

這里前兩種情況都還能理解，所以我只解釋為什么是右側子樹的最小節點。

其實這是為了防止順序亂掉而做的處理，舉個例子：

還是之前的那張圖，我要刪掉15這個節點，那么這時無論是把20還是13接到根節點11下面都會導致二叉搜索樹“左小右大”的結構大亂（就像曹操如果沒有接班人就死了北方就會大亂），因此最好的辦法是找一個比他大一點的節點來替換它（找一個強一點的接班人坐他的位子維持秩序）。

這里為啥是大一點而不是大很多？因為大太多也會導致結構混亂（過于強勢成為暴君就不給底下人活路了）。所以就選了一個大一點的節點替換到這個位置上來，同時為防止重復就刪掉了原來的節點（接班人不能身兼兩職所以要辭掉原來的職位）。

說到這里我就直接貼代碼了，反正現在讓我寫，一時半會是寫不出來的，因此僅供觀摩：

// 這個輔助函數和minNode函數是一樣的，只不過返回值不一樣
var findMinNode = function (node) {
  if (node === null) {
    while (node && node.left !== null) {
      node = node.left
    }
    return node
  }
  return null
}

var removeNode = function (node, key) {
  if (node === null) {
    return null
  }

  if (key < node.key) {
    node.left = removeNode(node.left, key)
    return node
  } else if (key > node.key) {
    node.right = removeNode(node.right, key)
    return node
  } else {
    // 第一種情況：刪除葉節點
    if (node.left === null && node.right === null) {
      node = null
      return node
    }

    // 第二種情況：刪除一側有子節點的節點
    // 將一側的子節點替換為當前節點
    if (node.left === null) {
      node = node.right
      return node
    } else if (node.right === null) {
      node = node.left
      return node
    }

    // 第三種情況：刪除兩側都有子節點的節點
    // 找到當前節點右側子樹中最小的那個節點，替換掉要刪除的節點
    // 然后再把右側子樹中最小的節點移除
    var aux = findMinNode(node.right)
    node.key = aux.key
    node.right = removeNode(node.right, aux.key)
    return node
  }
}

// 刪除節點
this.remove = function (key) {
  root = removeNode(root, key)
}

源代碼在此：

二叉搜索樹的實現-源代碼

實現二叉搜索樹花了好長時間，后面的圖也是挺麻煩的數據結構，但是這段時間不停地學習數據結構也是讓自己得到了很大成長。繼續加油～