BinarySearchTree
/
BinarySearchTree.html

<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Document</title>
</head>
<body>
	<script>
		// 二叉搜索树是二叉树的一种(比父节点小的在左侧，比父节点大的在右侧)

		// 创建二叉搜索树的函数
		function BinarySearchTree () {

			// 声明一个Node来表示每个节点
			var Node = function(key){
				this.key = key;
				this.left = null;
				this.right = null;
			}
			// 根元素
			var root = null;

			// 向树种插入一个新的节点
			this.insert = function(key){
				var newNode = new Node(key);
				if(root === null){
					root = newNode;
				}else {
					insertNode(root, newNode);
				}
				console.log('我是二叉搜索树');
				console.log(root);
			}
			// 向树中插入一个新节点，需要经历三个步骤
			// 1.创建用来表示新节点的Node类实例。只需要向构造函数传递我们想用来插入树的节点值，它的左指针和右指针的值会由构造函数自动设置为null
			// 2.要验证这个插入操作是否为一种特殊情况。这个特殊情况就是我们要插入的节点是树的第一个节点。如果是，就将根节点指向新节点
			// 3.将节点加在非根节点的其他位置。这种情况下，需要有一个私有的辅助函数insertNode

			// 中序遍历(从小到大的顺序访问所有节点)
			this.inOrderTraverse = function(callback){
				console.log('进行中序遍历');
				inOrderTraverseNode(root, callback);
			}

			// 先序遍历(优先于后代节点的顺序访问每个节点。先序遍历的一种应用是打印结构化的文档。--从左至右、从上到下--)
			this.preOrderTraverse = function(callback){
				console.log('进行先序遍历');
				preOrderTraverseNode(root, callback);
			}


			// 后序遍历(先访问后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它子目录中所有文件所占空间的大小)
			this.postOrderTraverse = function(callback){
				console.log('进行后序遍历');
				postOrderTraverseNode(root, callback);
			}

			// 搜索最小键
			this.min = function(){
				return minNode(root);
			}

			// 搜索最大键
			this.max = function(){
				return maxNode(root);
			}

			// 判断某个键是否存在
			this.search = function(key){
				return searchNode(root, key);
			}

			// 实现remove节点的方法
			this.remove = function(key){
				root = removeNode(root, key);
				console.log(root);
			}
		}

		// insertNode函数帮助我们找到新节点应该插入的位置
		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);
				}
			}
		}

		// inOrderTraverseNode函数帮助我们对二叉树进行中序遍历
		var inOrderTraverseNode = function(node, callback){
			if(node !== null){
				inOrderTraverseNode(node.left, callback);
				callback(node.key);
				inOrderTraverseNode(node.right, callback);
			}
		}

		// preOrderTraverseNode函数帮助我们对二叉树进行先序遍历
		var preOrderTraverseNode = function(node, callback){
			if(node !== null){
				callback(node.key);
				preOrderTraverseNode(node.left, callback);
				preOrderTraverseNode(node.right, callback);
			}
		}

		// postOrderTraverseNode函数帮助我们对二叉树进行后序遍历
		var postOrderTraverseNode = function(node, callback){
			if(node !== null){
				postOrderTraverseNode(node.left, callback);
				postOrderTraverseNode(node.right, callback);
				callback(node.key);
			}
		}

		function printNode(value){
			console.log(value);
		}

		var minNode = function(node){
			if(node){
				while (node && node.left !== null) {
					node = node.left;
				}
				return node.key;
			}
			return null;
		}

		var maxNode = function(node){
			if(node){
				while (node && node.right !== null) {
					node = node.right;
				}
				return node.key;
			}
			return null;
		}

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

		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 { // 等于node.key

				// 第一种情况，一个叶节点
				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;

			}
		}

		var findMinNode = function(node){
			if(node){
				while (node && node.left !== null) {
					node = node.left;
				}
				return node;
			}
			return null;
		}

		// 新建一个二叉搜索树
		var tree = new BinarySearchTree();
		tree.insert(11);
		tree.insert(7);
		tree.insert(15);
		tree.insert(5);
		tree.insert(3);
		tree.insert(9);
		tree.insert(8);
		tree.insert(10);
		tree.insert(13);
		tree.insert(12);
		tree.insert(14);
		tree.insert(20);
		tree.insert(18);
		tree.insert(25);
		tree.insert(6);

		// 进行中序遍历
		tree.inOrderTraverse(printNode);

		// 进行先序遍历
		tree.preOrderTraverse(printNode);

		// 进行后序遍历
		tree.postOrderTraverse(printNode);

		// 打印最小和最大的键
		console.log('最小和最大的键');
		console.log(tree.min());
		console.log(tree.max());

		console.log('判断3是否存在');
		console.log(tree.search(3));

		console.log('判断100是否存在');
		console.log(tree.search(100));

		// remove一个节点请自己尝试打印

	</script>
</body>
</html>