摘要：二叉搜索樹這一數據結構綜合了以上兩種數據結構的優點。上圖就展示了一個二叉搜索樹。實現二叉樹的算法大部分都有遞歸。

一種非順序數據結構-樹，它對于存儲需要快速查找的數據非常有用

相關概念：

根節點：位于樹頂部的節點，沒有父節點

內部節點：至少有一個子節點的節點（7，5，9，15，13，20）

外部節點（葉節點）：沒有子元素的節點（第3層）

子樹：由節點和它的后代構成（節點13，12，14構成了一個子樹）

深度：節點的深度取決于它的祖先節點的數量

高度：取決于所有節點深度的最大值

無序鏈表在插入時候具有較高的靈敏性，而有序數組在查找的時候具有較高的效率。

二叉搜索樹（BST）這一數據結構綜合了以上兩種數據結構的優點。但是它只允許你在左側節點存儲（比父節點）小的值，右側節點存儲（比父節點）大的值。

上圖就展示了一個二叉搜索樹。實現二叉樹的算法大部分都有遞歸。

創建一個BinarySearchTree類

function BinarySearchTree () {
  var Node = function () {
    this.key = key; // 鍵
    this.left = null; // 指針指向左側子節點
    this.right = null; // 指針指向右側子節點
  };
  var root = null;
}

var tree = new BinarySearchTree();

實現insert(key)方法，插入一個鍵

this.insert = function (key) {
  var newNode = new Node(kye); // 創建用來表示新節點的Node類實例，
  if (root === null) { // 如果插入的節點是樹第一個節點
    root = newNode;
  } else {
    insertNode(root, newNode); // 私有的輔助函數
  }
}

tree.insert();

私有的輔助函數

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

前序遍歷：根節點->左子樹->右子樹
中序遍歷：左子樹->根節點->右子樹
后序遍歷：左子樹->右子樹->根節點

對下面的樹進行遍歷

前序遍歷：abdefgc

中序遍歷：debgfac

后序遍歷：edgfbca

中序遍歷：一種應用是對樹進行排序操作

this.inOrderTraverse = function {callback} {
  inOrderTraverse(root, callback); // 回調函數用來處理遍歷到的每個節點
};

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

先序遍歷：一種應用是打印一個結構化的文檔

this.preOrderTraverse = function (callback) {
  preOrderTraverseNode(root, callback);
}

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

后序遍歷：一種應用是計算一個目錄和它的子目錄中所有文件所占的空間大小。

this.postOrderTraverse = function (callback) {
  postOrderTraverse(root, callback);
}

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

對于尋找最小值，總是沿著樹的左邊；對于尋找最大值，總是沿著樹的右邊

尋找樹中的最小鍵

this.min = function () {
  return minNode(root);
}

var minNode = function (node) {
  if (node) {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node.key;
  }
  return null;
}

尋找一個特定的值

this.search = function (key) {
  return searchNode(root, key);
}

var searchNode = function (node, kye) {
  if (node === null) { // node有效性檢查
    return false;
  }
  if (key < node.key) { // 比當前節點小，當前節點的左側子樹搜索
    return searchNode(node.left, key);
  } else if (key > node.key) { // 比當前節點大，當前節點的右側子樹搜索
    return searchNode(node.right, key);
  } else { // 要找的鍵就是當前節點
    return true;
  }
}

this.remove = function (key) {
  root = removeNode (root, key);
}

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