【www.gdgbn.com--js教程】

java二叉排序树实现代码

public class binarysearchtree{
 private node root;
 private int size;
 
 public binarysearchtree(node root){
  this.root=root;
  size++;
 }
 
 public int getsize(){
  return this.size;
 }
 
 public boolean contains(name name){
  return contains(name,this.root);
  //return false;
 }
 
 private boolean contains(name n,node root){
  if(root==null){
   return false;
  }
  int compare=n.compareto(root.element);
  if(compare>0){
   if(root.right!=null){
    return contains(n,root.right);
   }else{
    return false;
   }
  }else if(compare<0){
   if(root.left!=null){
    return contains(n,root.left);
   }else{
    return false;
   }
  }else{
   return true;
  }
 }
 
 public boolean insert(name n){
  boolean flag = insert(n,this.root);
  if(flag) size++;
  return flag;
 }
 
 private boolean insert(name n,node root){
  if(root==null){
   this.root=new node(n);
   return true;
  }else if(root.element.compareto(n)>0){
   if(root.left!=null){
    return insert(n,root.left);
   }else{
    root.left=new node(n);
    return true;
   }
  }else if(root.element.compareto(n)<0){
   if(root.right!=null){
    return insert(n,root.right);
   }else{
    root.right=new node(n);
    return true;
   }
  }else{
   root.frequency++;
   return true;
  }
 }

 public boolean remove(name name){
  root = remove(name,this.root);
  if(root != null){
   size--;
   return true;
  }
  return false;
 }
 
 private node remove(name name,node root){
  int compare = root.element.compareto(name);
  if(compare == 0){
   if(root.frequency>1){
    root.frequency--;
   }else{
    /**根据删除节点的类型,分成以下几种情况
    **①如果被删除的节点是叶子节点,直接删除
    **②如果被删除的节点含有一个子节点,让指向该节点的指针指向他的儿子节点
    **③如果被删除的节点含有两个子节点,找到左字数的最大节点,并替换该节点
    **/
    if(root.left == null && root.right == null){
     root = null;
    }else if(root.left !=null && root.right == null){
     root = root.left;
    }else if(root.left == null && root.right != null){
     root = root.right;
    }else{
     //被删除的节点含有两个子节点
     node newroot = root.left;
     while (newroot.left != null){
      newroot = newroot.left;//找到左子树的最大节点
     }
     root.element = newroot.element;
     root.left = remove(root.element,root.left);
    }
   }
  }else if(compare > 0){
   if(root.left != null){
    root.left = remove(name,root.left);
   }else{
    return null;
   }
  }else{
   if(root.right != null){
    root.right = remove(name,root.right);
   }else{
    return null;
   }
  }
  return root;
 }

 public string tostring(){
  //中序遍历就可以输出树中节点的顺序
  return tostring(root);
 }
 
 private string tostring(node n){
  string result = "";
  if(n != null){
   if(n.left != null){
    result += tostring(n.left);
   }
   result += n.element + " ";
   if(n.right != null){
    result += tostring(n.right);
   }
  }
  return result;
 }
 
}

删除节点

class node{
 public name element;
 public node left;
 public node right;
 public int frequency = 1;
 
 public node(name n){
  this.element=n;
 }
}

class name implements comparable{
 private string firstname;
 private string lastname;
 
 public name(string firstname,string lastname){
  this.firstname=firstname;
  this.lastname=lastname;
 }
 
 public int compareto(name n) {
  int result = this.firstname.compareto(n.firstname);
  return result==0?this.lastname.compareto(n.lastname):result;
 }
 
 public string tostring(){
  return firstname + "-" +lastname;
 }
}

本文来源:http://www.gdgbn.com/wangyezhizuo/29325/