二叉查找树 --java代码
代码可能写的不够好，不过是爱心代码，宝贝要看懂哦！
?
（1）tree接口?
所有的树，都要实现这样的接口
Tree.java 文件
public interface Tree {
??? public int get_count();
??? public void?? insert(Object obj);
??? public void?? delete(Object obj);
??? public Object search(Object obj);
??? public void display();????
}
（2）TreeCompare 接口
此接口原来在比较书中对象时使用，由于书中存储的对象不同，使用的比较方法不同
TreeCompare.java文件
public interface TreeCompare {
????? public int compare(Object node_value,Object search_value);
}
（3）MyTree的实现
?MyTree.java文件
?
//树节点class TreeNode{TreeNode left; //左子树TreeNode right; //右子树Object value; //存储值/*属性的获取和设置方法*/public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}public Object getValue() {return value;}public void setValue(Object value) {this.value = value;} /*构造函数*/public TreeNode(){this.left=null;this.right=null;this.value=null;}public TreeNode(Object value){this.left=null;this.right=null;this.value=value;}}//树中存储的对象为Integer类型，所以自己实现一个比较接口class MyTreeCompare implements TreeCompare{ public int compare(Object node_value,Object search_value) { Integer a=(Integer)node_value; return a.compareTo((Integer)search_value); }}//自己的树public class MyTree implements Tree {TreeNode root; //树根int count; //节点数TreeCompare compare_method; //比较函数//子树最大值 private TreeNode tree_node_max(TreeNode node) { //一直向右，最右边的是最大的 while(node.getRight()!=null) { node=node.getRight(); } return node; } //子树最小值 private TreeNode tree_node_min(TreeNode node) { //一直向左，最左边的是最大的 while(node.getLeft()!=null) { node=node.getLeft(); } return node; } //递归插入一个节点 /* 算法解释: 插入一个节点，首先要看是否已经存在，也就是先查找， 所以要不断的递归进行比较。 (1)如果一直到NULL，也就是没有找到，说明插入的为新节点， 需要创建新的节点。 (2)如果相等，说明已经存在，不需要再插入了，则返回即可 (3)如果不相等，根据大小插入节点的左子树或者右子树 */ TreeNode tree_node_insert(TreeNode node,Object value) { //如果没有比较方法，不能插入 if(this.compare_method==null) { return null; } //节点为空表明已经查找到了叶子，插入的值为新值，需要创建新的节点 if(node==null) { this.count++; return new TreeNode(value); } //如果插入值等于节点值，说明已经存在，无需插入，直接返回 else if(this.compare_method.compare(node.getValue(),value)==0) { return node; } //如果插入值大于节点值，继续往右子树插入 else if(this.compare_method.compare(node.getValue(),value)<0) { node.setRight(tree_node_insert(node.getRight(),value)); return node; } //如果插入值小于节点值，继续往左子树插入 else { node.setLeft(tree_node_insert(node.getLeft(),value)); return node; } } // 递归删除一个节点 /* 算法解释: 删除一个节点，删除和插入很像，不过要复杂点。 也要先查找点，不过找到要执行删除操作，没找到反而不用干什么。 (1)如果为NULL，说明没找到，只要返回NULL就行了 (2)如果相等，说明已经存在要删除的节点，那就需要删除此节点了 1)如果此节点左右子树都为空，那就直接删除节点，返回NULL就行 2)如果此节点左子树不空，而右子树为空，删除节点，返回左子树 3)如果此节点右子树不空，而左子树为空，删除节点，返回右子树 4)如果左右子树都不空，那就需要早到左子树中最大的数或则右子树 中最小的值，替换到要删除的值，然后在左子树中删除最大的节点 或者右子树删除最小的节点。 (3)如果不相等，根据大小删除节点 */ TreeNode tree_node_delete(TreeNode node,Object value) { //如果为NULL，说明没找到，只要返回NULL就行了 if(node==null) { return null; } //如果相等，说明已经存在要删除的节点，那就需要删除此节点了 else if(this.compare_method.compare(node.getValue(),value)==0) { TreeNode left=node.getLeft(); TreeNode right=node.getRight(); this.count--; //如果此节点左右子树都为空，那就直接删除节点，返回NULL就行 if(left==null&&right==null) { return null; } //如果此节点左子树不空，而右子树为空，删除节点，返回左子树 else if(left!=null&&right==null) { return left; } //如果此节点右子树不空，而左子树为空，删除节点，返回右子树 else if(left==null&&right!=null) { return right; } //如果左右子树都不空，那就需要早到左子树中最大的数 //替换到要删除的值 //然后在左子树中删除最大的节点 //返回节点 else { TreeNode max=tree_node_max(left); node.setValue(max.getValue()); node.setLeft(tree_node_delete(left,max.getValue())); return node; } } //如果不相等，根据大小删除节点 else if(this.compare_method.compare(node.getValue(),value)<0) { node.setRight(tree_node_delete(node.getRight(),value)); return node; } //如果插入值小于节点值，继续往左子树插入 else { node.setLeft(tree_node_delete(node.getLeft(),value)); return node; } } //查找TreeNode tree_node_search(TreeNode node,Object value) { //没有找到，直接返回 if(node==null) { return null; } //找到，直接返回 else if(this.compare_method.compare(node.getValue(),value)==0) { return node; } //继续往右子树查找 else if(this.compare_method.compare(node.getValue(),value)<0) { return tree_node_search(node.getRight(),value); } //继续往左子树查找 else { return tree_node_search(node.getLeft(),value); } } //先序遍历void display_tree_node(TreeNode node) { if(node!=null) { System.out.print(" ["+node.getValue()+"]"); display_tree_node(node.getLeft()); display_tree_node(node.getRight()); } } /*下面是对外的Tree接口实现*/public void delete(Object obj) {// TODO Auto-generated method stub this.root=this.tree_node_delete(this.root,obj);}public int get_count() {// TODO Auto-generated method stubreturn this.count;}public void insert(Object obj) {// TODO Auto-generated method stub this.root=this.tree_node_insert(this.root,obj);}public Object search(Object obj) {// TODO Auto-generated method stub TreeNode node=tree_node_search(this.root,obj); if(node!=null) { return node.getValue(); } else { return null; } } public void display() {// TODO Auto-generated method stub display_tree_node(this.root); System.out.println(); } public MyTree() { this.root=null; this.count=0; this.compare_method=null; } public MyTree(TreeCompare compare) { this.root=null; this.count=0; this.compare_method=compare; }/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stub Tree tree=new MyTree(new MyTreeCompare()); Integer a=new Integer("1"); Integer a1=new Integer("1"); Integer b=new Integer("2"); Integer c=new Integer("3"); Integer d=new Integer("0"); Integer e=new Integer("5"); //插入a System.out.println("插入"+a); tree.insert(a); tree.display(); System.out.println("插入"+a); tree.insert(a); tree.display(); System.out.println("插入"+b); tree.insert(b); tree.display(); System.out.println("插入"+c); tree.insert(c); tree.display(); System.out.println("插入"+d); tree.insert(d); tree.display(); //查找 if(tree.search(a)!=null) { System.out.println("查找"+a+": 找到"); } else { System.out.println("查找"+a+": 没有找到"); } //查找 if(tree.search(e)!=null) { System.out.println("查找"+e+": 找到"); } else { System.out.println("查找"+e+": 没有找到"); } //删除节点a System.out.println("删除"+a1); tree.delete(a1); tree.display(); //删除节点c System.out.println("删除"+c); tree.delete(c); tree.display(); //删除节点d System.out.println("删除"+d); tree.delete(d); tree.display(); //删除节点b System.out.println("删除"+b); tree.delete(b); tree.display(); //删除节点a System.out.println("删除"+a); tree.delete(a); }}?