binarySearchTree.js

function BinarySearchTree () {
  this._root = null;
}
 
BinarySearchTree.prototype = {
 
  constructor: BinarySearchTree,
 
  /**
   * find the min number of the tree
   */
  findMin: function () {
    var current = this._root;
 
    while (current.left !== null) {
      current = current.left;
    }
 
    return current.value;
  },
  
  /**
   * find the max number of the tree
   */
  findMax: function () {
    var current = this._root;
 
    while (current.right !== null) {
      current = current.right;
    }
 
    return current.value;
  },
 
  /**
   * make the tree empty
   */
  makeEmpty: function () {
 
    function empty (node) {
      if (node !== null) {
 
        if (node.left !== null) {
          empty(node.left);
        }
        
        if (node.right !== null) {
          empty(node.right);
        }
        
        node = null;
      }
    }
 
    empty(this._root);
  },
 
  /**
   * insert value to tree
   *
   * @param {Number} value
   */
  insert: function (value) {
    var node = {
      value: value,
      left: null,
      right: null
    }, current;
 
    if (this._root === null) {
      this._root = node;
    } else {
      current = this._root;
 
      while (true) {
        if (value < current.value) {
          if (current.left === null) {
            current.left = node;
            break;
          } else {
            current = current.left;
          }
        } else if (value > current.value) {
          if (current.right === null) {
            current.right = node;
            break;
          } else {
            current = current.right;
          }
        } else {
          break;
        }
      }
    }
  },
 
  /**
   * traverse the tree with callback
   *
   * @param {Function(node)} callback
   */
  traverse: function (callback) {
 
    function inOrder (node) {
      if (node) {
        if (node.left !== null) {
          inOrder(node.left);
        }
 
        callback.call(this, node);
 
        if (node.right !== null) {
          inOrder(node.right);
        }
      }
    }
 
    inOrder(this._root);
  },
 
  /**
   * delete the value node
   *
   * @param {Number} value
   */
  delete: function (value) {
    var that = this;
 
    function deleteNode (value, Tree) {
 
      var current;
 
      if (Tree === null) {
        throw new  Error('empty tree');
      } else if (value < Tree.value) {
        Tree.left = deleteNode(value, Tree.left);
      } else if (value > Tree.value) {
        Tree.right = deleteNode(value, Tree.right);
      } if (Tree.left && Tree.right) {
        // 找到节点右子树的最小节点
        current = Tree.right;
        while (current.left !== null) {
          current = current.left;
        }
        Tree.value = current.value;
        Tree.right = deleteNode(value, Tree.right);
      } else {
        if (Tree.left === null) {
          Tree = Tree.right;
        } else if (Tree.right === null) {
          Tree = Tree.left;
        }
        
        Tree = null;
      }
 
      return Tree;
    }
 
    this._root = deleteNode(value, this._root);
  },
 
  /**
   * return the tree size
   */
  size: function () {
    var length = 0;
 
    this.traverse(function (node) {
      length++;
    });
 
    return length;
  }
};