一些概念:

　　二叉查找树的重要性质:对于树中的每一个节点X,它的左子树任一节点的值均小于X,右子树上任意节点的值均大于X.

　　二叉查找树是java的TreeSet和TreeMap类实现的基础.

　　由于树的递归定义,二叉查找树的代码实现也基本上都是使用递归的函数,二叉查找树的平均深度是O(logN).

　　因为二叉查找树要求所有的节点都可以进行排序.所以编写时代码时需要一个Comparable泛型接口,当需要对类中的对象进行排序的时候,就需要实现这个泛型接口,里边定义了一个public int compareTo(Object o)方法,接受一个Object作为参数,java中String,Integer等类都实现了这个接口.

java代码实现:

　　remove方法:在查找树的代码实现中,最难得是删除,因为这涉及到三种情况:

　　　　被删除节点是树叶节点(没有子树):最简单,直接删除,将该节点置为null即可

　　　　被删除节点有一个子节点(左子树或右子树):是该节点的父节点指向该节点的子节点(左或右).见图1

　　　　被删除节点有两个子节点:用其右子树中的最小值代替该节点上的值,删除其右子树上的最小值.见图2.

  1 package com.wang.tree;
  2 
  3 public class BinarySearchTree<T extends Comparable<T>>{
  4 
  5     
  6     private static class Node<T>{
  7         private T data;
  8         private Node<T> left;
  9         private Node<T> right;
 10         
 11         public Node(T data){
 12             this(data,null,null);
 13         }
 14         public Node(T data, Node<T> left, Node<T> right) {
 15             this.data = data;
 16             this.left = left;
 17             this.right = right;
 18         }
 19     }
 20     
 21     //私有变量 根节点root
 22     private Node<T> root;
 23     
 24     //无参构造函数,根节点为null
 25     public BinarySearchTree(){
 26         root=null;
 27     }
 28     
 29     //清空二叉查找树
 30     public void makeEmpty(){
 31         root=null;
 32     }
 33     //判断树是否为空
 34     public boolean isEmpty(){
 35         
 36         return root==null;
 37     }
 38     //查找集合中是否有元素value,有返回true
 39     public boolean contains(T value){
 40         
 41         return contains(value,root);
 42     }
 43     
 44     private boolean contains(T value, Node<T> t) {
 45         
 46         if(t==null){
 47             return false;
 48         }
 49         int result=value.compareTo(t.data);
 50         if(result<0){
 51             return contains(value,t.left);
 52         }else if(result>0){
 53             return contains(value,t.right);
 54         }else{
 55             return true;
 56         }
 57     }
 58 
 59     //查找集合中的最小值
 60     public T findMin(){
 61         
 62         return  findMin(root).data;
 63     }
 64     private Node<T> findMin(Node<T> t) {
 65         if(t==null){
 66             return null;
 67         }else if(t.left==null){
 68             return t;
 69         }
 70         
 71         
 72         return findMin(t.left);
 73     }
 74 
 75     //查找集合中的最大值
 76     public T findMax(){
 77         
 78         return findMax(root).data;
 79     }
 80     
 81     private Node<T> findMax(Node<T> t) {
 82         if(t!=null){
 83             while(t.right!=null){
 84                 t=t.right;
 85             }
 86         }
 87         
 88         return t;
 89     }
 90 
 91     //插入元素
 92     public void insert(T value){
 93         
 94         root =insert(value,root);
 95     }
 96 
 97     private Node<T> insert(T value, Node<T> t) {
 98         if(t==null){
 99             return new Node(value,null,null);
100         }
101         int result=value.compareTo(t.data);
102         if(result<0){
103             t.left=insert(value,t.left);
104         }else if(result>0){
105             t.right=insert(value,t.right);
106         }
107         return t;
108     }
109     //移除元素
110     public void remove(T value){
111         root=remove(value,root);
112         
113         
114     }
115 
116     private Node<T> remove(T value, Node<T> t) {
117         if(t==null){
118             return t;
119         }
120         
121         int result=value.compareTo(t.data);
122         if(result<0){
123             t.left=remove(value,t.left);
124         }else if(result>0){
125             t.right=remove(value,t.right);
126         }else if(t.left!=null&&t.right!=null){//如果被删除节点有两个儿子
127             //1.当前节点值被其右子树的最小值代替
128             t.data=findMin(t.right).data;
129             //将右子树的最小值删除
130             t.right=remove(t.data, t.right);
131         }else{
132             //如果被删除节点是一个叶子 或只有一个儿子
133             t=(t.left!=null)?t.left:t.right;
134         }
135         
136         return t;
137     }
138     
139     //中序遍历打印
140     public void printTree(){
141         printTree(root);
142     }
143 
144     private void printTree(Node<T> t) {
145         
146         if(t!=null){
147             printTree(t.left);
148             System.out.println(t.data);
149             printTree(t.right);
150         }
151     }
152 }

　　测试代码:

package com.wang.tree;public class TestBST {public static void main(String[] args) {BinarySearchTree<Integer> bst=new BinarySearchTree<>();bst.insert(5);bst.insert(7);bst.insert(3);bst.insert(1);bst.insert(9);bst.insert(6);bst.insert(4);System.out.println("最小值:"+bst.findMin());System.out.println("最大值:"+bst.findMax());System.out.println("查找元素9是否存在:"+bst.contains(9));System.out.println("查找元素8是否存在:"+bst.contains(8));System.out.println("遍历二叉树");bst.printTree();}
}