摘要：二叉樹(shù)和二叉搜索樹(shù)二叉樹(shù)的節(jié)點(diǎn)最多只能有兩個(gè)節(jié)點(diǎn)，而二叉搜索樹(shù)只允許在左側(cè)的節(jié)點(diǎn)處存儲(chǔ)比父節(jié)點(diǎn)小的值，在右側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大的值。接收回調(diào)函數(shù)作為參數(shù)先序遍歷先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問(wèn)沒(méi)和節(jié)點(diǎn)的。

樹(shù)是一種非順序數(shù)據(jù)結(jié)構(gòu)，對(duì)于存儲(chǔ)需要快速查找的數(shù)據(jù)非常有用。樹(shù)是一種分層數(shù)據(jù)的抽象模型，現(xiàn)實(shí)生活中最常見(jiàn)的例子就是家譜，或者是公司的組織架構(gòu)圖。

樹(shù)中的每一個(gè)元素都是節(jié)點(diǎn)，節(jié)點(diǎn)分為內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)。其中：
至少有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)（例如圖中節(jié)點(diǎn)7,5,9,15,13,20），沒(méi)有子元素的節(jié)點(diǎn)為外部節(jié)點(diǎn)或葉節(jié)點(diǎn)（例如圖中節(jié)點(diǎn)3，6,8,10,12,14,18,25）。
位于樹(shù)頂部的節(jié)點(diǎn)叫做根節(jié)點(diǎn)，它沒(méi)有父節(jié)點(diǎn)。
節(jié)點(diǎn)的一個(gè)屬性是深度，節(jié)點(diǎn)的深度 取決于它的祖先節(jié)點(diǎn)的數(shù)量。樹(shù)的高度取決于深度的最大值。同樣一棵樹(shù)也可以分為層級(jí)，根節(jié)點(diǎn)在第0層，它的子節(jié)點(diǎn)在第1層，以此類推。

二叉樹(shù)的節(jié)點(diǎn)最多只能有兩個(gè)節(jié)點(diǎn)，而二叉搜索樹(shù)只允許在左側(cè)的節(jié)點(diǎn)處存儲(chǔ)（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）大的值。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
};
class Node {
  constructor(key) {
    this.key = key;
    this.left = undefined;
    this.right = undefined;
  };
//下面我們會(huì)聲明BinarySearchTree類的基本骨架
class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.root = undefined;
  }

insert(key) {
    // special case: first key
    if (this.root == null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left == null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else if (node.right == null) {
      node.right = new Node(key);
    } else {
      this.insertNode(node.right, key);
    }
  }

中序遍歷是一種以上行順序訪問(wèn)BST所有節(jié)點(diǎn)的遍歷方式，也就是從最小到最大的順序訪問(wèn)所有節(jié)點(diǎn)。中序遍歷的一種應(yīng)用是對(duì)樹(shù)進(jìn)行排序操作。

//inOrderTraverse接收回調(diào)函數(shù)作為參數(shù)
inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

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

先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問(wèn)沒(méi)和節(jié)點(diǎn)的。先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔、我們來(lái)看代碼實(shí)現(xiàn)

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

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

后序遍歷就是縣訪問(wèn)節(jié)點(diǎn)的后代節(jié)點(diǎn)，在訪問(wèn)節(jié)點(diǎn)本身。后序遍歷的一種應(yīng)用是計(jì)算一個(gè)目錄及其子目錄中所有文件所占空間的大小

postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }

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

  minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
      current = current.left;
    }
    return current;
  }

max() {
    return this.maxNode(this.root);
  }

  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }

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

  searchNode(node, key) {
    if (node == null) {
      return false;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);
    } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    }
    return true;
  }

removeNode(node, key) {
    if (node == null) {
      return undefined;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key);
      return node;
    } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key);
      return node;
    }
    // key is equal to node.item
    // handle 3 special conditions
    // 1 - a leaf node
    // 2 - a node with only 1 child
    // 3 - a node with 2 children
    // case 1 移除一個(gè)葉節(jié)點(diǎn)
    if (node.left == null && node.right == null) {
      node = undefined;
      return node;
    }
    // case 2 移除有一個(gè)左側(cè)或者右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    if (node.left == null) {
      node = node.right;
      return node;
    } if (node.right == null) {
      node = node.left;
      return node;
    }
    // case 3    移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    const aux = this.minNode(node.right);
    node.key = aux.key;
    node.right = this.removeNode(node.right, aux.key);
    return node;
  }
}