/**
 * 二叉树
 */
function BinarySearchTree() {
	var Node = function(key){
    	this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null;
	// 辅助方法(插入节点)
	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);
			}
		} 
	};	
	// 插入节点
	this.insert = function(key){
        var newNode = new Node(key);
        if (root === null){
            root = newNode;
        } else {
            insertNode(root,newNode);
		} 
	};
	// 辅助方法(中序遍历)
	var inOrderTraverseNode = function (node, callback) {
        if (node !== null) {
             inOrderTraverseNode(node.left, callback);
             callback(node.key);
             inOrderTraverseNode(node.right, callback);
		} 
	};
	// 中序遍历-从小到大
	this.inOrderTraverse = function(callback){
         inOrderTraverseNode(root, callback);
	};
	// 辅助方法(先序遍历)
	var preOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            callback(node.key); //{1}
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
		} 
	};
	// 先序遍历-优先于后台节点
	this.preOrderTraverse = function(callback){
        preOrderTraverseNode(root, callback);
	};
	// 辅助方法(后序遍历)
	var postOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
		} 
	};
	// 后序遍历
	this.postOrderTraverse = function(callback){
        postOrderTraverseNode(root, callback);
	};
	// 辅助方法(最小值)
	var minNode = function (node) {
        if (node){
            while (node && node.left !== null) {
            	node = node.left;
    		}
			return node.key;
		}
    	return null;
	};
	// 最小值
	this.min = function() {
        return minNode(root);
	};
	// 辅助方法(最大值)
	var maxNode = function (node) {
    	if (node){
    		while (node && node.right !== null) {
    			node = node.right;
			}
    		return node.key;
    	}
    	return null;
    };
	// 最大值
	this.max = function() {
        return maxNode(root);
	};
	// 辅助方法(搜索特定值)
	var searchNode = function(node, key){
    	if (node === null){
        	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.search = function(key){
    	return searchNode(root, key);
	};
	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;
		}	
 	};

}