ishenli/BST.html

## BST.html
<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>BST</title>
</head>

<body>
    <script>
    	function Node(data, left, right) {
    		this.data = data;
    		this.left = left;
    		this.right = right;
    		this.show = show;
    	}

    	function show() {
    		return this.data;
    	}

    	function BST() {
    		this.root = null;
    		this.insert = insert;
    		this.inOrder = inOrder;
    	}

		/**
		 * 插入节点
		 * @param  {number|string} data
		 */
    	function insert (data) {
    		var n = new Node(data, null, null);
    		if (this.root === null) {
    			this.root = n;
    		}
    		else {
    			var current = this.root;
				var parent;
				while(true){
					parent = current;
					if (data < current.data) {
						current = current.left;
						if (current == null){ // 没有左节点
							parent.left = n;
							break;
						}
					}
					else {
						current = current.right;
						if (current == null){
							parent.right = n;
							break;
						}
					}
				}
    		}

    	}

    	// 中序遍历
    	function inOrder(node) {
    		if (!(node==null)){
				inOrder(node.left);
				console.log(node.data);
				inOrder(node.right);
    		}
    	}

    	// test
    	var num = new BST();

    	num.insert(23);
    	num.insert(45);
    	num.insert(16);
    	num.insert(37);
    	num.insert(3);
    	num.insert(99);
    	num.insert(22);

    	console.log('start inOrder in BST:===========');

    	inOrder(num.root); // 3 16 22 23 37 45 99
    </script>
</body>

</html>
	<!DOCTYPE html>
	<html>

	<head>
	<meta charset="utf-8">
	<title>BST</title>
	</head>

	<body>
	<script>
	function Node(data, left, right) {
	this.data = data;
	this.left = left;
	this.right = right;
	this.show = show;
	}

	function show() {
	return this.data;
	}

	function BST() {
	this.root = null;
	this.insert = insert;
	this.inOrder = inOrder;
	}

	/**
	* 插入节点
	* @param {number\|string} data
	*/
	function insert (data) {
	var n = new Node(data, null, null);
	if (this.root === null) {
	this.root = n;
	}
	else {
	var current = this.root;
	var parent;
	while(true){
	parent = current;
	if (data < current.data) {
	current = current.left;
	if (current == null){ // 没有左节点
	parent.left = n;
	break;
	}
	}
	else {
	current = current.right;
	if (current == null){
	parent.right = n;
	break;
	}
	}
	}
	}

	}

	// 中序遍历
	function inOrder(node) {
	if (!(node==null)){
	inOrder(node.left);
	console.log(node.data);
	inOrder(node.right);
	}
	}

	// test
	var num = new BST();

	num.insert(23);
	num.insert(45);
	num.insert(16);
	num.insert(37);
	num.insert(3);
	num.insert(99);
	num.insert(22);

	console.log('start inOrder in BST:===========');

	inOrder(num.root); // 3 16 22 23 37 45 99
	</script>
	</body>

	</html>