二叉查找树(Binary Search Tree),又叫二叉排序数(Binary Sort Tree),网上的实现都是假定元素是整型,这里使用泛型搞一个,实现插入、查找、删除、查找最小值这四个操作。
public class BST<T extends Comparable> {
public static void main(String args[])throws Exception{
BST bst = new BST();
BSTNode<Integer> root = new BSTNode<Integer>(10);
bst.insert(root,33);
bst.insert(root,2);
bst.insert(root,1);
bst.insert(root,3);
bst.insert(root,55);
bst.insert(root,7);
bst.remove(root,2);
bst.findMin(root);
bst.contains(root,7);
}
/**
* bst删除其中一个节点
* @param node
* @param value
* @return
*/
public BSTNode<T> remove(BSTNode<T> node,T value){
if(node==null){
return null;
}
//值比较,给定值小于节点值递归遍历左子树,反之遍历右子树
int result = value.compareTo(node.value);
if(result<0){
node.left = remove(node.left,value);
}else if(result>0){
node.right = remove(node.right,value);
}else {
//找到要删除的节点
//如果要删除的节点有左右子树,则节点的值变为右子树的最小值,并递归的删除右子树中的这个最小值
//之所以这样做是因为右子树中的最小值肯定比相邻的左子树值大,
// 而且小于右子树任何值,可以作为当前左右子树的父节点
if(node.left!=null && node.right!=null){
node.value = findMin(node.right);
node.right = remove(node.right,node.value);
}else{
//只有左子树或者右子树或者为树叶的情况一样
node = (node.left!=null) ? node.left:node.right;
}
}
return node;
}
/**
* 查找最小值
* @param node
* @return
*/
public T findMin(BSTNode<T> node){
if(node==null){
return null;
//节点没有左子树,自己就是最小值
}else if(node.left==null){
return node.value;
}else {
//递归查找左子树,BST的性质就是最小的值在左子树
return findMin(node.left);
}
}
/**
* bst查找
* @param node
* @param value
* @return
*/
public boolean contains(BSTNode node,T value){
if(node==null){
return false;
}
int result = value.compareTo(node.value);
//小于则搜索左子树,大于则搜索右子树
if(result<0){
return contains(node.left,value);
}else if(result>0){
return contains(node.right,value);
}else{
return true;
}
}
/**
* 插入
* @param node
* @param value
* @return
* @throws Exception
*/
public BSTNode<T> insert(BSTNode<T> node,T value) throws Exception{
if(node==null){
node = new BSTNode<T>(value);
node.left = null;
node.right = null;
return node;
}
int result = value.compareTo(node.value);
if(result<0){
node.left=insert(node.left,value);
}else if(result>0){
node.right=insert(node.right,value);
}else {
throw new Exception("the element has been inserted");
}
return node;
}
}
class BSTNode<T>{
T value;
BSTNode<T> left;
BSTNode<T> right;
public BSTNode(T value){
this.value = value;
}
}