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

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

相關(guān)概念：

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

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

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

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

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

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

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

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

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

創(chuàng)建一個(gè)BinarySearchTree類

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

var tree = new BinarySearchTree();

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

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

tree.insert();

私有的輔助函數(shù)

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

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

對下面的樹進(jìn)行遍歷

前序遍歷：abdefgc

中序遍歷：debgfac

后序遍歷：edgfbca

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

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

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

先序遍歷：一種應(yīng)用是打印一個(gè)結(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)用是計(jì)算一個(gè)目錄和它的子目錄中所有文件所占的空間大小。

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

尋找一個(gè)特定的值

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

var searchNode = function (node, kye) {
  if (node === null) { // node有效性檢查
    return false;
  }
  if (key < node.key) { // 比當(dāng)前節(jié)點(diǎn)小，當(dāng)前節(jié)點(diǎn)的左側(cè)子樹搜索
    return searchNode(node.left, key);
  } else if (key > node.key) { // 比當(dāng)前節(jié)點(diǎn)大，當(dāng)前節(jié)點(diǎn)的右側(cè)子樹搜索
    return searchNode(node.right, key);
  } else { // 要找的鍵就是當(dāng)前節(jié)點(diǎn)
    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) { // 一個(gè)葉節(jié)點(diǎn)
      node = null;
      return node;
    }
    if (node.left === null) { // 一個(gè)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) 
      node = node.right;
      return node;
    } else if (node.right === null) {
      node = node.left;
      return node;
    }

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