摘要：二叉搜索樹這一數(shù)據(jù)結(jié)構(gòu)綜合了以上兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點。上圖就展示了一個二叉搜索樹。實現(xiàn)二叉樹的算法大部分都有遞歸。

一種非順序數(shù)據(jù)結(jié)構(gòu)-樹，它對于存儲需要快速查找的數(shù)據(jù)非常有用

相關(guān)概念：

根節(jié)點：位于樹頂部的節(jié)點，沒有父節(jié)點

內(nèi)部節(jié)點：至少有一個子節(jié)點的節(jié)點（7，5，9，15，13，20）

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

子樹：由節(jié)點和它的后代構(gòu)成（節(jié)點13，12，14構(gòu)成了一個子樹）

深度：節(jié)點的深度取決于它的祖先節(jié)點的數(shù)量

高度：取決于所有節(jié)點深度的最大值

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

二叉搜索樹（BST）這一數(shù)據(jù)結(jié)構(gòu)綜合了以上兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點。但是它只允許你在左側(cè)節(jié)點存儲（比父節(jié)點）小的值，右側(cè)節(jié)點存儲（比父節(jié)點）大的值。

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

創(chuàng)建一個BinarySearchTree類

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

var tree = new BinarySearchTree();

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

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

tree.insert();

私有的輔助函數(shù)

var insertNode = function (node, newNode) { // 從根節(jié)點開始
  if (newNode.key < node.key) { // 判斷左側(cè)，遍歷左側(cè)
    if (node.left === null) { // 如果子節(jié)點為空，就在子節(jié)點添加新節(jié)點
      node.left = newNode;
    } else {
      insertNode(node.left, newNode); // 往下遞歸
    }
  } else { // 判斷右側(cè)，遍歷右側(cè)
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode);
    }
  }
}

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

對下面的樹進行遍歷

前序遍歷：abdefgc

中序遍歷：debgfac

后序遍歷：edgfbca

中序遍歷：一種應(yīng)用是對樹進行排序操作

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

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

先序遍歷：一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔

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

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

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) { // 比當前節(jié)點小，當前節(jié)點的左側(cè)子樹搜索
    return searchNode(node.left, key);
  } else if (key > node.key) { // 比當前節(jié)點大，當前節(jié)點的右側(cè)子樹搜索
    return searchNode(node.right, key);
  } else { // 要找的鍵就是當前節(jié)點
    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) { // 一個葉節(jié)點
      node = null;
      return node;
    }
    if (node.left === null) { // 一個只有一個子節(jié)點的節(jié)點 
      node = node.right;
      return node;
    } else if (node.right === null) {
      node = node.left;
      return node;
    }

    // 一個有兩個子節(jié)點的節(jié)點
    var aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    return node;
  }
}