求二叉排序树的java实现，，，

Question

求二叉排序树的java实现，哪位大哥有的话，请贴出来。主要看怎么实现从一个二叉排序树中删除一个节点，谢谢！

Answer 1

自己之前写的一个：class Node{
public int id;
public String context;
public Node l,r,p;
public Node(int id,String context){
this.id = id;
this.context = context;
}
}
public class Tree{
private Node root,cur;
private int size = 0;
public void insert(int id,String context){
Node n = new Node(id,context);
if(root==null){
root = n;
cur = n;
}else{
cur = root;
while(true){
Node parent = cur;
if(id>cur.id){
cur = cur.r;
if(cur==null){
parent.r = n;
n.p = parent;
break;
}
}else{
cur = cur.l;
if(cur==null){
parent.l = n;
n.p = parent;
break;
}
}
}
}
size++;
}
public void remove(int id){
Node del = searchNode(id);
if(del==null)
return;
cur = del;
if(cur.l==null&&cur.r==null){
if(cur!=root)
if(cur.p.r==cur)
cur.p.r = null;
else
cur.p.l = null;
else
root = null;
}else if(cur.l!=null&&cur.r!=null){
Node replacer = del.r;
while(replacer.l!=null)
replacer = replacer.l;
replacer.l = cur.l;
cur.l.p = replacer;
if(cur!=root){
if(cur.p.r==cur)
cur.p.r = cur.r;
else
cur.p.l = cur.r;
cur.r.p = cur.p;
}else{
root = cur.r;
cur.r.p = null;
}
}else if(cur.l!=null){
if(cur!=root){
if(cur.p.r==cur)
cur.p.r = cur.l;
else
cur.p.l = cur.l;
cur.l.p = cur.p;
}else{
root = cur.l;
cur.l.p = null;
}
}else if(cur.r!=null){
if(cur!=root){
if(cur.p.r==cur)
cur.p.r = cur.r;
else
cur.p.l = cur.r;
cur.r.p = cur.p;
}else{
root = cur.r;
cur.r.p = null;
}
}
size--;
}
public String search(int id){
Node n = searchNode(id);
return n==null?"node not found":n.context;
}
public Node searchNode(int id){
Node n = null;
cur = root;
while(true){
if(cur==null)
break;
if(id==cur.id){
n = cur;
break;
}
if(id>cur.id)
cur = cur.r;
else
cur = cur.l;
}
return n;
}
public int size(){
return size;
}
public void iterate(){
iterate(root);
}
private void iterate(Node n){
if(n==null)
return;
iterate(n.l);
System.out.println(n.id+","+n.context);
iterate(n.r);
}
public static void main(String args[]){
Tree t = new Tree();
java.util.Random r = new java.util.Random();
for(int i=0;i<50;i++){
int temp = r.nextInt(20);
t.insert(temp,"context"+temp);
}
t.iterate();
while(t.root!=null){
t.remove(t.root.id);
t.iterate();
System.out.println("================"+t.size());
}
}
}