二叉搜索树

[conan1992]

二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树;
二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质：

• 非空左子树的所有键值小于其父结点的键值。
• 非空右子树的所有键值大于其父结点的键值。
• 左、右子树本身也都是二叉搜索树。

实现难点

实现难点在于节点移除时，考虑被移除节点的三种情况

1. 被移除节点为叶节点（没有子节点）
2. 被移除节点有一个子节点
3. 被移除节点有二个子节点

实现

function Node( key ){
	this.key = key;
	this.left = null;
	this.right = null;
}
function BinarySerachTree(){
	this.root = null;
}
BinarySerachTree.prototype.insert = function(key){
	var newNode = new Node( key );
	if(this.root){
		this.insertNode(this.root, newNode)
	}else{
		this.root = newNode;
	}
}
BinarySerachTree.prototype.insertNode = function(node, newNode){
	if(newNode.key<node.key){
		if(node.left === null){
			node.left = newNode;
		}else{
			this.insertNode(node.left, newNode)
		}
	}else{
		if(node.right === null){
			node.right = newNode;
		}else{
			this.insertNode(node.right, newNode)
		}
	}
}
BinarySerachTree.prototype.preOrderTraversal = function(handler){
	this.preOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.preOrderTraversalNode = function(node, handler){
	if(!node){
		return
	}
	handler(node.key)
	this.preOrderTraversalNode(node.left, handler)
	this.preOrderTraversalNode(node.right, handler)
}
BinarySerachTree.prototype.inOrderTraversal = function(handler){
	this.inOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.inOrderTraversalNode = function(node, handler){
	if(!node){
		return
	}
	
	this.inOrderTraversalNode(node.left, handler)
	handler(node.key)
	this.inOrderTraversalNode(node.right, handler)
}
BinarySerachTree.prototype.postOrderTraversal = function(handler){
	this.postOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.postOrderTraversalNode = function(node, handler){
	if(!node){
		return
	}
	
	this.postOrderTraversalNode(node.left, handler)
	this.postOrderTraversalNode(node.right, handler)
	handler(node.key)
}
BinarySerachTree.prototype.min = function(node){
	var node = this.root;
	if(!node) return null;
	while(node.left){
		node = node.left
	}
	return node.key
}
BinarySerachTree.prototype.max = function(node){
	var node = this.root;
	if(!node) return null;
	while(node.right){
		node = node.right
	}
	return node.key
}
BinarySerachTree.prototype.search = function(key){
	var node = this.root;
	if(!node) return false;
	while(node){
		if(node.key==key){
			return true
		}else if(node.key>key){
			node = node.left
		}else if(node.key<key){
			node = node.right
		}
	}
	return false;
}
BinarySerachTree.prototype.remove = function(key){
	var current = this.root;
	var parent = this.root;
	var isLeftChild = false;
	
	while(current){
		if(key < current.key){
			parent = current;
			current = current.left;
			isLeftChild = true;
		}else if(key > current.key){
			parent = current;
			current = current.right
			isLeftChild = false;
		}else{
			break
		}
	}
	if(current){
		if(!current.left && !current.right){
			//空节点
			if(current==this.root){
				this.root = null;
			}else if(isLeftChild){
				parent.left = null
			}else{
				parent.right = null
			}
		}else if(current.left == null){
			if( current== this.root){
				this.root = current
			}else if(isLeftChild){
				parent.left = current.right;
			}else{
				parent.right = current.right;
			}
		}else if(current.right == null){
			if( current== this.root){
				this.root = current
			}else if(isLeftChild){
				parent.left = current.left;
			}else{
				parent.right = current.left;
			}
		}else{
			//寻找后继
			var successor = this.getSuccessor(current)
			if(current == this.root){
				this.root = successor
			}else if(isLeftChild){
				parent.left = successor
			}else{
				parent.right = successor
			}
			successor.left = current.left
		}
		
		return true
	}else{
		return false
	}
}
//寻找后继
BinarySerachTree.prototype.getSuccessor = function(delNode){
	var successor = delNode;
	var successorParent = delNode;
	var current = delNode.right;
	while(current){
		successorParent = successor
		successor = current
		current = current.left;
	}
	if(successor != delNode.right){
		successorParent.left = successor.right;
		successor.right = delNode.right
	}
	return successor
}
//test
// 测试代码
var bst = new BinarySerachTree()
console.log(bst.min(), bst.max())
// 插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
bst.inOrderTraversal(function(key){
	console.log(key)
})
console.log(bst.min(), bst.max())
console.log(bst.search(5))

参考链接

• 数据结构(十二)之二叉搜索树