学步园

在二叉查找树里用到了大量的递归调用，首先整清楚一个问题-----引用拷贝，下面代码实际上swap的两个参数都是引用的拷贝。

public class Main {
	public static void main(String[] args) {
		String s1 = "1";
		String s2 = "2";
		swap(s1,s2);
		System.out.println(s1);
		System.out.println(s2);
	}
	
	static void swap(String s1,String s2){
		String s = s1;
		s1 = s2;
		s2 = s;
	}
}

output：

1

2

package changsheng.datastructure;

import changsheng.algorithms.util.DuplicateItemException;
import changsheng.algorithms.util.EmptyTreeException;
import changsheng.algorithms.util.ItemNotFoundException;

public class BinarySearchTree<E extends Comparable<? super E>> {
	private Node<E> root;

	public BinarySearchTree() {
		this.root = null;
	}
	
	/**
	 * 清空二叉树
	 */
	public void makeEmpty() {
		this.root = null;
	}
	
	/**
	 * 判断二叉树是否为空
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * 是否包含元素x
	 */
	public boolean contains(E x) {
		return contains(x, root);
	}

	private boolean contains(E x, Node<E> r) {

		int compareResult = x.compareTo(r.value);
		if (compareResult < 0) {
			return contains(x, r.left);
		} else if (compareResult > 0) {
			return contains(x, r.right);
		} else {
			return true;
		}
	}

	/**
	 * 返回二叉树最小值
	 */
	public E findMin() {
		if (isEmpty()) {
			throw new EmptyTreeException();
		}
		return findMin(root).value;
	}
	
	public E find(E x){
		return elementAt(find(x,root));
	}
	
	/**
	 *返回二叉树最大值 
	 */
	public E findMax() {
		if (isEmpty()) {
			throw new EmptyTreeException();
		}
		return findMax(root).value;
	}
	
	/**
	 * 插入x
	 */
	public void insert(E x) {
		root = insert(x, root);
	}
	
	/**
	 * 移除x
	 */
	public void remove(E x) {
		root = remove(x, root);
	}
	
	/**
	 * 移除最小元素
	 */
	public void removeMin(){
		root = removeMin(root);
	}

	/**
	 * 寻找x
	 */
	private Node<E> find( E x, Node<E> t )
    {
        while( t != null )
        {
            if( x.compareTo( t.value ) < 0 )
                t = t.left;
            else if( x.compareTo( t.value ) > 0 )
                t = t.right;
            else
                return t;    // Match
        }
        
        return null;         // Not found
    }
	
	private E elementAt( Node<E> t )
    {
        return t == null ? null : t.value;
    }

	private Node<E> findMin(Node<E> r) {
		if (r != null) {
			while (r.left != null) {
				r = r.left;
			}
		}
		return r;
	}

	
	private Node<E> findMax(Node<E> r) {
		if (r != null) {
			while (r.right != null) {
				r = r.right;
			}
		}
		return r;
	}

	private Node<E> insert(E x, Node<E> r) {
		if (r == null) {
			return new Node<E>(x, null, null);
		}

		int compareresult = x.compareTo(r.value);
		if (compareresult < 0) {
			r.left = insert(x, r.left);
		} else if (compareresult > 0) {
			r.right = insert(x, r.right);
		} else {
			throw new DuplicateItemException( x.toString( ) );
		}
		return r;
	}

	private Node<E> removeMin( Node<E> t )
    {
        if( t == null )
            throw new ItemNotFoundException( );
        else if( t.left != null )
        {
            t.left = removeMin( t.left );
            return t;
        }
        else
            return t.right;
    }  
	

	private Node<E> remove(E x, Node<E> r) {
		if (r == null) {
			throw new ItemNotFoundException( x.toString( ) );
		}

		int compareResult = x.compareTo(r.value);
		if (compareResult < 0) {
			r.left = remove(x,r.left);
		} else if (compareResult > 0) {
			r.right = remove(x,r.right);
		} else if (r.left != null && r.right != null) {
			r.value = findMin(r.right).value;
			r.right = removeMin(r.right);
		} else {
			r = (r.left != null) ? r.left : r.right;
		}
		return r;
	}

	private static class Node<E> {
		Node<E> left;
		Node<E> right;
		E value;

		public Node(E value, Node<E> left, Node<E> right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
	
	public static void main( String [ ] args )
    {
        BinarySearchTree<Integer> t = new BinarySearchTree<Integer>( );
        final int NUMS = 4000;
        final int GAP  =   37;

        System.out.println( "Checking... (no more output means success)" );

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        for( int i = 1; i < NUMS; i += 2 )
            t.remove( i );

        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );

        for( int i = 2; i < NUMS; i += 2 )
             if( t.find( i ) != i )
                 System.out.println( "Find error1!" );

        for( int i = 1; i < NUMS; i += 2 )
            if( t.find( i ) != null )
                System.out.println( "Find error2!" );
    }
}