摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學(xué)習(xí)的內(nèi)容，就是如何寫一個(gè)二叉搜索樹。但在二叉搜索樹中，我們把節(jié)點(diǎn)成為鍵，這是術(shù)語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法四二叉搜索樹

本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列
第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表
第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合
第四篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（四）：二叉搜索樹

在剛學(xué)編程時(shí)，就知道有一種數(shù)據(jù)結(jié)構(gòu)叫“樹”，樹中的翹楚是“二叉樹”，“紅黑樹”等。
據(jù)說“樹”構(gòu)在編程界呼風(fēng)喚雨無所不能。讓無數(shù)程序員聞風(fēng)喪膽。甚至在面試時(shí)，更是有“手寫二叉樹”，“翻轉(zhuǎn)二叉樹”等題目坐鎮(zhèn)。

好吧，我承認(rèn)這些在當(dāng)時(shí)都把我嚇住了。

但是當(dāng)我顫抖著打開《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》，開始敲下關(guān)于“樹”的代碼時(shí)，突然覺得，好像也沒有那么難呢。
于是心懷激動(dòng)，一口氣敲完了書上的例子，中途也思考了很久，不斷的在紙上演算等。但總的來說，還是學(xué)的很開心的。

之前學(xué)的棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹，將會(huì)是我們學(xué)的第一種非順序數(shù)據(jù)結(jié)構(gòu)。

放在現(xiàn)實(shí)里呢，有個(gè)很生動(dòng)的例子，公司組織架構(gòu)圖。長這樣:

而我們要學(xué)的樹，長這樣:

其中，樹中的每個(gè)元素，都叫做節(jié)點(diǎn)。從節(jié)點(diǎn)延伸而下的，叫子節(jié)點(diǎn)。
樹頂部的節(jié)點(diǎn)叫根節(jié)點(diǎn)。每棵樹只有一個(gè)根節(jié)點(diǎn)。（圖中15就是根節(jié)點(diǎn)）
在節(jié)點(diǎn)中，有子節(jié)點(diǎn)的節(jié)點(diǎn)也稱為內(nèi)部節(jié)點(diǎn)，沒有的話則被稱為外部節(jié)點(diǎn)或者葉節(jié)點(diǎn)。
同時(shí)在節(jié)點(diǎn)中是有祖先和后代關(guān)系的，比如節(jié)點(diǎn)9的祖先就有13,7,6,15四個(gè)。

深度: 節(jié)點(diǎn)的深度取決于其祖先的數(shù)量，節(jié)點(diǎn)9的深度就是4。
樹的高度，樹的高度體現(xiàn)為節(jié)點(diǎn)深度的最大值。
比如上圖，節(jié)點(diǎn)深度最大值為4，則樹的高度為4。

二叉樹的最大特點(diǎn)就在于，它的節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn):左側(cè)子節(jié)點(diǎn)和右側(cè)子節(jié)點(diǎn)。
二叉搜索樹則是二叉樹的一種，但它只允許你在左側(cè)節(jié)點(diǎn)儲(chǔ)存比父節(jié)點(diǎn)小的值，右側(cè)只允許儲(chǔ)存比父節(jié)點(diǎn)大的值。
像剛才的這幅圖，就是二叉搜索樹。

而我們本文要學(xué)習(xí)的內(nèi)容，就是如何寫一個(gè)二叉搜索樹。

首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。

/**
 * 二叉搜索樹的構(gòu)造函數(shù)
 */
function BinarySearchTree() {
  /**
   * 二叉搜索樹鍵的構(gòu)造函數(shù)
   * @param {Number} key 要生成的鍵值
   */
  var Node = function(key) {
    // 鍵值
    this.key = key;
    // 左子節(jié)點(diǎn)
    this.left = null;
    // 右子節(jié)點(diǎn)
    this.right = null;
  }

  /**
   * 二叉樹的根節(jié)點(diǎn)，不存在時(shí)表示為Null
   * @type {Null or Number}
   */
  var root = null;
}

在之前提到過的雙向鏈表中，每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向左側(cè)節(jié)點(diǎn)，一個(gè)指向右側(cè)節(jié)點(diǎn)。在二叉搜索樹中，每個(gè)節(jié)點(diǎn)也有兩個(gè)指針，一個(gè)指向左側(cè)子節(jié)點(diǎn)，一個(gè)指向右側(cè)子節(jié)點(diǎn)。但在二叉搜索樹中，我們把節(jié)點(diǎn)成為鍵，這是術(shù)語。

二叉搜索樹需要有如下的方法:

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

inOrderTraverse(): 通過中序遍歷方式，遍歷所有節(jié)點(diǎn)

preOrderTranverse(): 通過先序遍歷方式，遍歷所有節(jié)點(diǎn)

postOrderTranverse(): 通過后序遍歷方式，遍歷所有節(jié)點(diǎn)

min(): 返回樹中最小的值

max(): 返回樹中最大的值

search(key): 搜索某個(gè)值，在樹中則返回true

remove(key): 從樹中移除某個(gè)鍵

二叉搜索樹的實(shí)現(xiàn)，基本都與遞歸有關(guān)（對(duì)我來說遞歸很繞，花了很久才理解）。如果不清楚遞歸相關(guān)概念，可以看看下面的參考鏈接。

什么是遞歸

說明:向樹中插入一個(gè)新的鍵
實(shí)現(xiàn):

/**
 * 插入某個(gè)鍵到二叉樹中
 * @param  {Number} key 要插入的鍵值
 */
this.insert = function(key) {
  // 用傳入的值生成二叉樹的鍵
  var newNode = new Node(key);

  // 根節(jié)點(diǎn)為Null時(shí)，傳入的鍵則為根節(jié)點(diǎn)
  // 否則調(diào)用insertNode函數(shù)來插入子節(jié)點(diǎn)
  if (root === null) {
    root = newNode;
  } else {
    insertNode(root, newNode)
  }
};

/**
 * 用于插入子節(jié)點(diǎn)。
 * @param  {Node} node    根節(jié)點(diǎn)
 * @param  {Node} newNode 要插入的節(jié)點(diǎn)
 */
var insertNode = function(node, newNode) {
  //由于二叉搜索樹的性質(zhì)，所以當(dāng)鍵值小于當(dāng)前所在節(jié)點(diǎn)的鍵值
  //則使得左子結(jié)點(diǎn)成為新的要比較的節(jié)點(diǎn)，進(jìn)行遞歸調(diào)用
  //如果左子結(jié)點(diǎn)為null，則將鍵值賦值給左子結(jié)點(diǎn)。
  //如果鍵值大于當(dāng)前所在節(jié)點(diǎn)的鍵值，原理同上。
  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)
    }
  }
};

說明:通過中序遍歷方式，遍歷所有節(jié)點(diǎn)
實(shí)現(xiàn):

/**
 * 中序遍歷操作，常用于排序。會(huì)把樹中元素從小到大的打印出來。
 * 因?yàn)樵趈avascript的遞歸中，遇到遞歸是，會(huì)優(yōu)先調(diào)用遞歸的函數(shù)。直到遞歸不再進(jìn)行。
 * 然后會(huì)在遞歸調(diào)用的最后一個(gè)函數(shù)中執(zhí)行其它語句。再一層層的升上去。
 * 所以中序遍歷會(huì)有從小到大的輸出結(jié)果。
 * 后續(xù)的先序和后續(xù)遍歷和這個(gè)原理差不多，取決于callback放在哪兒。
 * 
 * @param  {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù)
 */
this.inOrderTraverse = function(callback) {
  inOrderTraverseNode(root, callback);
};


/**
 * 中序遍歷的輔助函數(shù)，用于遍歷節(jié)點(diǎn)
 * @param  {Node}   node     遍歷開始的節(jié)點(diǎn)，默認(rèn)為root
 * @param  {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù)
 * @return {[type]}            [description]
 */
var inOrderTraverseNode = function(node, callback) {
  // 當(dāng)前節(jié)點(diǎn)不為NULL則繼續(xù)遞歸調(diào)用
  if (node != null) {
    inOrderTraverseNode(node.left, callback);
    // 獲取到節(jié)點(diǎn)后，調(diào)用的函數(shù)
    callback(node.key);
    inOrderTraverseNode(node.right, callback);
  }
};

假如我們這兒加入打印節(jié)點(diǎn)值的函數(shù):

var printNode = function(value) {
  console.log(value);
};

inOrderTraverse(printNode) // 輸出排序后樹的值

說明:通過先序遍歷方式，遍歷所有節(jié)點(diǎn)
實(shí)現(xiàn):

/**
 * 前序遍歷操作，常用于打印一個(gè)結(jié)構(gòu)化的文檔
 * @param  {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù)
 */
this.preOrderTranverse = function(callback) {
  preOrderTranverseNode(root, callback);
};

/**
 * 前序遍歷的輔助函數(shù)，用于遍歷節(jié)點(diǎn)
 * @param  {Node}   node     遍歷開始的節(jié)點(diǎn)，默認(rèn)為root
 * @param  {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù)
 */
var preOrderTranverseNode = function(node, callback) {
  if (node != null) {
    callback(node.key);
    preOrderTranverseNode(node.left, callback);
    preOrderTranverseNode(node.right, callback);
  }
};

說明:通過后序遍歷方式，遍歷所有節(jié)點(diǎn)
實(shí)現(xiàn):

/**
 * 后序遍歷操作，常用于計(jì)算所占空間
 * @param  {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù)
 */
this.postOrderTranverse = function(callback) {
  postOrderTranverseNode(root, callback);
};

/**
 * 后序遍歷的輔助函數(shù)，用于遍歷節(jié)點(diǎn)
 * @param  {Node}   node     遍歷開始的節(jié)點(diǎn)，默認(rèn)為root
 * @param  {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù)
 */
var postOrderTranverseNode = function(node, callback) {
  postOrderTranverseNode(node.left, callback);
  postOrderTranverseNode(node.right, callback);
  callback(node.key);
};

說明:返回樹中最小的值，由二叉搜索樹的性質(zhì)易知，最左側(cè)的為最小值。則只需取得最左側(cè)的值即可。
實(shí)現(xiàn):

/**
 * 返回樹中最小的值
 * @return {Function} min函數(shù)的輔助函數(shù)
 */
this.min = function() {
  return minNode(root);
};

/**
 * min函數(shù)的輔助函數(shù)
 * @param  {Node} node 查找開始的節(jié)點(diǎn)，默認(rèn)為root
 */
var minNode = function(node) {
  // 如果node存在，則開始搜索。能避免樹的根節(jié)點(diǎn)為Null的情況
  if (node) {
    // 只要樹的左側(cè)子節(jié)點(diǎn)不為null，則把左子節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)。
    // 若左子節(jié)點(diǎn)為null，則該節(jié)點(diǎn)肯定為最小值。
    while (node && node.left !== null) {
      node = node.left;
    }
    return node.key;
  }
  return null;
};

說明:返回樹中最大的值，由min函數(shù)易知，最大值在最右側(cè)。
實(shí)現(xiàn):

/**
 * 返回樹中最大的值
 * @return {Function} max函數(shù)的輔助函數(shù)
 */
this.max = function() {
  return maxNode(root);
};

/**
 * max函數(shù)的輔助函數(shù)
 * @param  {Node} node 查找開始的節(jié)點(diǎn)，默認(rèn)為root
 * @return {Key}      節(jié)點(diǎn)的值
 */
var maxNode = function(node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right;
    }
    return node.key;
  }
  return null;
};

說明: 搜索某個(gè)值，在樹中則返回true
實(shí)現(xiàn):

/**
 * 搜索某個(gè)值是否存在于樹中
 * @param  {Node} key 搜索開始的節(jié)點(diǎn)，默認(rèn)為root
 * @return {Function}     search函數(shù)的輔助函數(shù)
 */
this.search = function(key) {
  return searchNode(root, key);
};

/**
 * search函數(shù)的輔助函數(shù)
 * @param  {Node} node 搜索開始的節(jié)點(diǎn)，默認(rèn)為root
 * @param  {Key} key  要搜索的鍵值
 * @return {Boolean}      找到節(jié)點(diǎn)則返回true，否則返回false
 */
var searchNode = function(node, key) {
  // 如果根節(jié)點(diǎn)不存在，則直接返回null
  if (node === null) {
    return false;
  } else if (key < node.key) {
    searchNode(node.left, key)
  } else if (key > node.key) {
    searchNode(node.right, key)
  } else {
    // 如果該節(jié)點(diǎn)值等于傳入的值，返回true
    return true;
  }
};

說明:從樹中移除某個(gè)鍵，要應(yīng)對(duì)的場景:

只是一個(gè)葉節(jié)點(diǎn)

有一個(gè)子節(jié)點(diǎn)

有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
因?yàn)橐獞?yīng)付不同的場景，所以這是最麻煩的方法了。讓我思考了好久才理解。如果你覺得看不懂的話，可以下載源代碼把這一段寫一遍。

實(shí)現(xiàn):

/**
 * 從樹中移除某個(gè)鍵
 * @param  {Key} key 要移除的鍵值
 * @return {Function}     remove函數(shù)的輔助函數(shù)
 */
this.remove = function(key) {
  root = removeNode(root, key);
};

/**
 * remove函數(shù)的輔助函數(shù)
 * @param  {Node} node 搜索開始的節(jié)點(diǎn)，默認(rèn)為root
 * @param  {Key} key   要移除的鍵值
 * @return {Boolean}   移除成功則返回true，否則返回false
 */
var removeNode = function(node, key) {
  // 如果根節(jié)點(diǎn)不存在，則直接返回null
  if (node === root) {
    return null;
  }
  // 未找到節(jié)點(diǎn)前，繼續(xù)遞歸調(diào)用。
  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 {
    // 第一種場景：只是一個(gè)葉節(jié)點(diǎn)
    // 這種情況只需要直接把節(jié)點(diǎn)賦值為null即可
    if (node.left === null && node.right === null) {
      node = null;
      // 處理完直接return節(jié)點(diǎn)
      return node;
    }
    // 第二種場景：有一個(gè)子節(jié)點(diǎn)
    // 如果左節(jié)點(diǎn)為null，則代表右節(jié)點(diǎn)存在。
    // 于是把當(dāng)前節(jié)點(diǎn)賦值為存在的那個(gè)子節(jié)點(diǎn)
    if (node.left === null) {
      node = node.right;
      // 處理完直接return節(jié)點(diǎn)
      return node;
    } else if (node.right == null) {
      node = node.left;
      // 處理完直接return節(jié)點(diǎn)
      return node;
    }
    // 第三種場景：有兩個(gè)子節(jié)點(diǎn)
    // 首先加入輔助節(jié)點(diǎn)，同時(shí)找尋右子節(jié)點(diǎn)中的最小節(jié)點(diǎn)
    // 并把當(dāng)前節(jié)點(diǎn)替換為右子節(jié)點(diǎn)中的最小節(jié)點(diǎn)
    // 同時(shí)為了避免節(jié)點(diǎn)重復(fù)，移除右子節(jié)點(diǎn)中的最小節(jié)點(diǎn)
    var aux = findMinNode(node.right);
    node.key = aux.key;

    node.right = removeNode(node.right, aux.key);
    // 處理完直接return節(jié)點(diǎn)
    return node;
  }
};

/**
 * remove函數(shù)的輔助函數(shù)
 * @param  {Node} node 查找開始的節(jié)點(diǎn)，默認(rèn)為root
 * @return {Node}      最小的節(jié)點(diǎn)
 */
var findMinNode = function(node) {
  // 如果node存在，則開始搜索。能避免樹的根節(jié)點(diǎn)為Null的情況
  if (node) {
    // 只要樹的左側(cè)子節(jié)點(diǎn)不為null，則把左子節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)。
    // 若左子節(jié)點(diǎn)為null，則該節(jié)點(diǎn)肯定為最小值。
    while (node && node.left !== null) {
      node = node.left;
    }
    return node;
  }
  return null;
};

源代碼在此~

二叉搜索樹-源代碼

寫文章的時(shí)候，人有點(diǎn)感冒，暈暈乎乎的。不過寫完之后就好多了，腦子清醒了許多。
二叉樹這一章，就我而言感慨萬分，也算是暫時(shí)滿足了自己對(duì)數(shù)據(jù)結(jié)構(gòu)中“樹”的向往與愿望，也不是之前看數(shù)據(jù)結(jié)構(gòu)中那種迷茫的感覺。
能用JavaScript親手實(shí)現(xiàn)，還是非常開心的。

前端路漫漫，且行且歌~

Lxxyx的前端樂園
原文鏈接：寒假前端學(xué)習(xí)(6)——學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（四）：二叉搜索樹