学步园

package nuaa.ds;

//对于重复项:只记录一项，维护对重复项的计数
public class BinarySearchTree<T extends Comparable<? super T>> {
	
	protected BinaryNode<T> root;
	
	public BinarySearchTree(){
	}
	
	public void insert(T x) throws Exception{
		root = this.insert(x, root);
	}
	
	//递归插入
	protected BinaryNode<T> insert(T x,BinaryNode<T> t) throws Exception{
		if(t==null)//没有更深的节点，同时包含了树本身为空的情况
			t = new BinaryNode<T>(x);
		else if(x.compareTo(t.element)<0)       //把生成的的左(右)节点
			t.left = this.insert(x, t.left);    //或者原始的左(右)节点
		else if(x.compareTo(t.element)>0)		//值返回给树的上一层,一
			t.right = this.insert(x, t.right);  //直到最上层返回根
		else 
			throw new Exception("DuplicateItem:"+x);
		return t;
	}
	
	
	public void remove(T x) throws Exception{
		root = remove(x,root);
	}
	
	//很多无意义的赋值
	protected BinaryNode<T> remove(T x,BinaryNode<T> t) throws Exception{
		if(t==null)
			throw new Exception("Item Not Found");
		if(x.compareTo(t.element)<0)
			t.left = remove(x,t.left);
		else if(x.compareTo(t.element)>0)
			t.right = remove(x,t.right);
		else if(t.left!=null&&t.right!=null){
			t.element = findMin(t.right).element;//替换右子树的最小元素 
			t.right = removeMin(t.right);//删除右子树中的最小节点
		}else{
			t = (t.left!=null)?t.left:t.right;
		}
		return t;
	}
	
	public void removeMin() throws Exception{
		root = this.removeMin(root);
	}
	

	protected BinaryNode<T> removeMin(BinaryNode<T> t) throws Exception{
		if(t==null)
			throw new Exception("Item Not Found:"+t);
		else if(t.left!=null){                 //有左子树进入左子树
			t.left = this.removeMin(t.left);   //
			return t;						   //本层有左子树的就返回本层的根给上层
		}else
			return t.right;  //没有就返回右子树给上层
	}

	private T elementAt(BinaryNode<T> t){
		return t==null?null:t.element;
	}
	
	public T findMin(){
		return this.elementAt(this.findMin(root));
	}
	protected BinaryNode<T> findMin(BinaryNode<T> t){
		if(t!=null)
			while(t.left!=null)
				t = t.left;
		return t;
	}
	
	
	public T findMax(){
		return this.elementAt(this.findMax(root));
	}
	private BinaryNode<T> findMax(BinaryNode<T> t){
		if(t!=null)
			while(t.right!=null)
				t = t.right;
		return t;
	}
	
	public T find(T x){
		return this.elementAt(this.find(x, root));
	}
	
	private BinaryNode<T> find(T x,BinaryNode<T> t){
		while(t!=null){
			if(x.compareTo(t.element)<0)
				t = t.left;
			else if(x.compareTo(t.element)>0)
				t = t.right;
			else
				return t;
		}
		return null;//NOT_FOUND
	}
	
	public void makeEmpty(){
		this.root = null;
	}
	public boolean isEmpty(){
		return root==null;
	}

	
}

二叉查找树在每个节点处多加一个字段，存放下面的子孙个数，就能很容易的找到第k个节点：左子树的个数+1是否等于k，等于就返回，小于就进入右子树，大于就进入左子树，递归继续往下执行。最后找不到了就返回错误

package nuaa.ds;

import java.util.NoSuchElementException;

public class BinarySearchTreeWithRank<T extends Comparable<? super T>> extends
		BinarySearchTree<T> {
	
	public T findKth(int k){
		return findKth(k,root).element;
	}
	
	protected BinaryNode<T> findKth(int k,BinaryNode<T> t){
		if(t==null)
			throw new IllegalArgumentException();
		int leftSize = t.left!=null ? 
				((BinaryNodeWithSize<T>)t.left).size : 0;
		if(k<=leftSize)
			return findKth(k,t.left);
		if(k==leftSize+1)
			return t;
		return findKth(k-leftSize-1,t.right);
	}
	
	protected BinaryNode<T> insert(T x,BinaryNode<T> tt) throws Exception{
		BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>)tt;
		if(t==null)
			t = new BinaryNodeWithSize<T>(x);
		else if(x.compareTo(t.element)>0)
			t.right = insert(x,t.right);
		else if(x.compareTo(t.element)<0)
			t.left = insert(x,t.left);
		else
			throw new Exception("Duplicate item");
		t.size++;
		return t;
	}
	
	protected BinaryNode<T> remove(T x,BinaryNode<T> tt) throws Exception{
		if(tt==null)
			throw new Exception("empty tree");
		if(x.compareTo(tt.element)>0)
			tt.right = remove(x,tt.right);
		if(x.compareTo(tt.element)<0)
			tt.left = remove(x,tt.left);
		else if(tt.left!=null&&tt.right!=null){
			tt.element = findMin(tt.right).element;
			tt.right = removeMin(tt.right);
		}else
			return tt.left!=null ? tt.left : tt.right;
		((BinaryNodeWithSize<T>)tt).size--;
		return tt;
	}
	
	protected BinaryNode<T> removeMin(BinaryNode<T> tt){
		if(tt==null)
			throw new NoSuchElementException();
		if(tt.left==null)
			return tt.right;
		tt.left = removeMin(tt.left);
		((BinaryNodeWithSize<T>)tt).size--;
		return tt;
	}
	
	private static class BinaryNodeWithSize<T> extends BinaryNode<T>{
		int size;
		BinaryNodeWithSize(T x){
			super(x);
			size = 0;
		}
		
	}
}