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

本系列所有文章：
第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列
第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合
第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表
第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹

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

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

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

二叉搜索樹需要實現(xiàn)以下方法：

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

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

inOrderTraverse：通過中序遍歷方式遍歷所有節(jié)點

preOrderTraverse：通過先序遍歷方式遍歷節(jié)點

postOrderTraverse：通過后序遍歷方式遍歷所有節(jié)點

min：返回樹中最小的值

max：返回樹中最大的值

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

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

// 用于插入節(jié)點
var insertNode = function (node, newNode) {
  // 在二叉搜索樹中，比父節(jié)點小的值存在左側(cè)節(jié)點，大于等于父節(jié)點的存在右側(cè)節(jié)點
  // 若要插入一個節(jié)點（根節(jié)點已存在），首先與根節(jié)點比大小，若比根節(jié)點小則應(yīng)插入根節(jié)點的左側(cè)
  // 如果左側(cè)已存在節(jié)點，則遞歸調(diào)用函數(shù)，將左側(cè)節(jié)點傳入遞歸函數(shù)作為當(dāng)前節(jié)點
  // 如果插入的節(jié)點比當(dāng)前節(jié)點大且當(dāng)前節(jié)點右側(cè)為空，則插入右側(cè)
  // 如果插入節(jié)點比根節(jié)點大，原理同上
  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)
  }
}

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

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

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
  }
}

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

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

其實這三種遍歷并沒有那么復(fù)雜，簡單地觀察一下回調(diào)函數(shù)（也就是訪問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)
}

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

請看這個最簡單的二叉樹

如果現(xiàn)在先序遍歷這個二叉樹，它的順序應(yīng)該是M -> H -> Z；中序遍歷的順序是H -> M -> Z；后序遍歷是：H -> Z -> M

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

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

var minNode = function(node) {
  // 如果node存在，則開始搜索。能避免樹的根節(jié)點為Null的情況
  if (node) {
    // 只要樹的左側(cè)子節(jié)點不為null，則把左子節(jié)點賦值給當(dāng)前節(jié)點。
    // 若左子節(jié)點為null，則該節(jié)點肯定為最小值。
    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
}

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

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

好了，現(xiàn)在剩下最后一個方法了，先深吸一口氣。。。

接下來實現(xiàn)的方法號稱全書最復(fù)雜的方法，鑒于本人目前水平有限，我只能將自己看懂的思路寫出來，如果講得不好大家可以去看原書《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》。

下面進(jìn)入正題：

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

刪除的是葉節(jié)點（沒有子節(jié)點的節(jié)點）

刪除的節(jié)點有一側(cè)子節(jié)點

刪除的節(jié)點有兩側(cè)子節(jié)點

還是老原則，化繁為簡。

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

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

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

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

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

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

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

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

// 這個輔助函數(shù)和minNode函數(shù)是一樣的，只不過返回值不一樣
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 {
    // 第一種情況：刪除葉節(jié)點
    if (node.left === null && node.right === null) {
      node = null
      return node
    }

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

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

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

源代碼在此：

二叉搜索樹的實現(xiàn)-源代碼

實現(xiàn)二叉搜索樹花了好長時間，后面的圖也是挺麻煩的數(shù)據(jù)結(jié)構(gòu)，但是這段時間不停地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是讓自己得到了很大成長。繼續(xù)加油～