摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學習的內容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節點成為鍵，這是術語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法四二叉搜索樹

本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列
第二篇文章：學習JavaScript數據結構與算法（二）：鏈表
第三篇文章：學習JavaScript數據結構與算法（三）：集合
第四篇文章：學習JavaScript數據結構與算法（四）：二叉搜索樹

在剛學編程時，就知道有一種數據結構叫“樹”，樹中的翹楚是“二叉樹”，“紅黑樹”等。
據說“樹”構在編程界呼風喚雨無所不能。讓無數程序員聞風喪膽。甚至在面試時，更是有“手寫二叉樹”，“翻轉二叉樹”等題目坐鎮。

好吧，我承認這些在當時都把我嚇住了。

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

之前學的棧、隊列、鏈表等數據結構，都是順序數據結構。而樹，將會是我們學的第一種非順序數據結構。

放在現實里呢，有個很生動的例子，公司組織架構圖。長這樣:

而我們要學的樹，長這樣:

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

深度: 節點的深度取決于其祖先的數量，節點9的深度就是4。
樹的高度，樹的高度體現為節點深度的最大值。
比如上圖，節點深度最大值為4，則樹的高度為4。

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

而我們本文要學習的內容，就是如何寫一個二叉搜索樹。

首先，創建一個構造函數。

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

  /**
   * 二叉樹的根節點，不存在時表示為Null
   * @type {Null or Number}
   */
  var root = null;
}

在之前提到過的雙向鏈表中，每個節點包含兩個指針，一個指向左側節點，一個指向右側節點。在二叉搜索樹中，每個節點也有兩個指針，一個指向左側子節點，一個指向右側子節點。但在二叉搜索樹中，我們把節點成為鍵，這是術語。

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

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

inOrderTraverse(): 通過中序遍歷方式，遍歷所有節點

preOrderTranverse(): 通過先序遍歷方式，遍歷所有節點

postOrderTranverse(): 通過后序遍歷方式，遍歷所有節點

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

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

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

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

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

什么是遞歸

說明:向樹中插入一個新的鍵
實現:

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

  // 根節點為Null時，傳入的鍵則為根節點
  // 否則調用insertNode函數來插入子節點
  if (root === null) {
    root = newNode;
  } else {
    insertNode(root, newNode)
  }
};

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

說明:通過中序遍歷方式，遍歷所有節點
實現:

/**
 * 中序遍歷操作，常用于排序。會把樹中元素從小到大的打印出來。
 * 因為在javascript的遞歸中，遇到遞歸是，會優先調用遞歸的函數。直到遞歸不再進行。
 * 然后會在遞歸調用的最后一個函數中執行其它語句。再一層層的升上去。
 * 所以中序遍歷會有從小到大的輸出結果。
 * 后續的先序和后續遍歷和這個原理差不多，取決于callback放在哪兒。
 * 
 * @param  {Function} callback 獲取到節點后的回調函數
 */
this.inOrderTraverse = function(callback) {
  inOrderTraverseNode(root, callback);
};


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

假如我們這兒加入打印節點值的函數:

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

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

說明:通過先序遍歷方式，遍歷所有節點
實現:

/**
 * 前序遍歷操作，常用于打印一個結構化的文檔
 * @param  {Function} callback 獲取到節點后的回調函數
 */
this.preOrderTranverse = function(callback) {
  preOrderTranverseNode(root, callback);
};

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

說明:通過后序遍歷方式，遍歷所有節點
實現:

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

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

說明:返回樹中最小的值，由二叉搜索樹的性質易知，最左側的為最小值。則只需取得最左側的值即可。
實現:

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

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

說明:返回樹中最大的值，由min函數易知，最大值在最右側。
實現:

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

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

說明: 搜索某個值，在樹中則返回true
實現:

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

/**
 * search函數的輔助函數
 * @param  {Node} node 搜索開始的節點，默認為root
 * @param  {Key} key  要搜索的鍵值
 * @return {Boolean}      找到節點則返回true，否則返回false
 */
var searchNode = function(node, key) {
  // 如果根節點不存在，則直接返回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 {
    // 如果該節點值等于傳入的值，返回true
    return true;
  }
};

說明:從樹中移除某個鍵，要應對的場景:

只是一個葉節點

有一個子節點

有兩個子節點的節點
因為要應付不同的場景，所以這是最麻煩的方法了。讓我思考了好久才理解。如果你覺得看不懂的話，可以下載源代碼把這一段寫一遍。

實現:

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

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

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

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

源代碼在此~

二叉搜索樹-源代碼

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

前端路漫漫，且行且歌~

Lxxyx的前端樂園
原文鏈接：寒假前端學習(6)——學習JavaScript數據結構與算法（四）：二叉搜索樹