泛型二叉排序树

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Stack;

/**
* <p>
* This class is used to store Element that implements the interface of
* Comparable to a Binary Sorted Tree
*
* @param <E>
*            the type of elements stored in the tree
* @author Jay Chang
* @version 1.0, 08/14/09
* @see Iterator
* @see Comparable
* @see Stack
*/
public class SortedBiTree<E extends Comparable<E>> {

/** 内部类，定义二叉排序树的结点 */
private static class SortedBiTreeNode<E> {
   private E element;
   private SortedBiTreeNode<E> lChild;
   private SortedBiTreeNode<E> rChild;

   private SortedBiTreeNode(E element) {
    this.element = element;
    this.lChild = null;
    this.rChild = null;
   }

   public E getelement() {
    return this.element;
   }
}

/** 树根结点 */
private SortedBiTreeNode<E> root;

/** 树的元素个数 */
private int capacity;

public SortedBiTree() {
   this.capacity = 0;
}

/**
* @function 添加一个元素
* @param E类型的元素
* @return 若元素存在返回true,否则返回false
*/
public boolean add(E element) {
   if (this.isExist(element)) {
    return false;
   }
   this.create(element);
   return true;
}

/**
* @function 添加一个集合
* @param Collecton集合且，集合内元素必须是E类型
* @return 若Collection集合的元素没有一个添加成功则返回false,否则返回true
*/
public boolean addAll(Collection<E> c) {
   Iterator<E> it = c.iterator();
   int count = 0;
   while (it.hasNext()) {
    E element = it.next();
    if (!this.isExist(element)) {
     add(element);
     count++;
    }
   }
   return count >= 1 ? true : false;
}

/**
* @function 私有方法，用于协助获得添加元素后的树
* @param E类型的元素
* @return void
*/
private void create(E element) {
   this.root = this.createSortedBiTree(this.root, element);
}

/**
* @function 私有方法，用于协助判断是否存在指定的元素
* @param E类型的元素
* @return 存在返回true, 否则返回false
*/
private boolean isExist(E element) {
   SortedBiTreeNode<E> tempNode = this.root;
   while (tempNode != null) {
    if (tempNode.element.compareTo(element) > 0) {
     tempNode = tempNode.lChild;
    } else if (tempNode.element.compareTo(element) < 0) {
     tempNode = tempNode.rChild;
    } else {
     return true;
    }
   }
   return false;
}

/**
* @function 私有方法用于实现添加一个元素，且遵循二叉排序树原则
* @param SortedBiTreeNode
*            <E>类型的结点
* @param E类型元素
* @return SortedBiTreeNode<E>类型的结点
*/
private SortedBiTreeNode<E> createSortedBiTree(SortedBiTreeNode<E> node,
    E element) {
   if (node == null) {
    node = new SortedBiTreeNode<E>(element);
    this.capacity++;
   }
   if (node.element.compareTo(element) < 0) {
    node.rChild = createSortedBiTree(node.rChild, element);
   } else if (node.element.compareTo(element) > 0) {
    node.lChild = createSortedBiTree(node.lChild, element);
   }
   return node;
}

/**
* @function 判断树是否为空
* @param none
* @return 若为空，返回true,否则返回false
*/
public boolean isEmpty() {
   return this.root == null;
}

/**
* @function 判断是否存在指定元素
* @param E类型元素
* @return 存在返回true,否则返回false
*/
public boolean contains(E element) {
   if (this.isExist(element)) {
    return true;
   } else {
    return false;
   }
}

/**
* @function 判断是否存在指定集合内的所有元素
* @param Collection
*            <E>
* @return 存在返回true,否则返回false
*/
public boolean containsAll(Collection<E> c) {
   if (this.isEmpty())
    return false;
   Iterator<E> it = c.iterator();
   while (it.hasNext()) {
    if (!this.isExist(it.next())) {
     return false;
    }
   }
   return true;
}

/**
* @function 得到E类型元素最小的那个结点的元素,即树的最左下角的元素
* @param none
* @return SortedBiTreeNode<E>类型的结点
*/
public E getMin() {
   if (this.isEmpty())
    return null;
   SortedBiTreeNode<E> tempNode = this.root;
   SortedBiTreeNode<E> pref = null;
   while (tempNode != null) {
    pref = tempNode;
    tempNode = tempNode.lChild;
   }
   return pref.element;
}

/**
* @function 中序遍历后得到有序的E类型数组
* @param none
* @return E类型的数组
*/
public E[] toArray(E[] a) {
   Object[] elements = new Object[this.capacity];
   int count = 0;
   Stack<SortedBiTreeNode<E>> stack = new Stack<SortedBiTreeNode<E>>();
   SortedBiTreeNode<E> pCurrent = this.root;
   while (pCurrent != null || !stack.isEmpty()) {
    if (pCurrent != null) {
     stack.push(pCurrent);
     pCurrent = pCurrent.lChild;
    } else {
     pCurrent = stack.peek().rChild;
     elements[count++] = stack.pop().element;
    }
   }
   return (E[]) Arrays.copyOf(elements, this.capacity, a.getClass());
   // 下面是在ArrayList里找到的返回泛型数组的源代码，可是自己觉得只需要上面一行就够了
   // 首先传进E[] a是肯定需要的，因为在本方法体内不能够new一个泛型数组，需要在调用此方
   // 法时，传进来，然后可以通过复制的方法，并可数组长度，觉得一句足以完成下面7句，而无需
   // 判断，数组a的长度，与sortedBiTree的元素个数，最终一定返回的是数组的长度为sortedBiTree
   // 的长度,而且当a.length大于等于this.capacity时，返回的数组长度是a.length的，而
   // 调用者应该想得到的是sortedBiTree的元素个数
   /*
   * if (a.length < this.capacity) return (T[])
   * Arrays.copyOf(elementData,this.capacity, a.getClass());
   * System.arraycopy(elements, 0, a, 0,this.capacity); if (a.length >
   * size) a[capacity] = null; return a;
   */
}

/**
* @function 得到E类型元素最大的那个结点的元素,
* @param none
* @return SortedBiTreeNode<E>类型的结点
*/
public E getMax() {
   if (this.isEmpty())
    return null;
   SortedBiTreeNode<E> tempNode = this.root;
   SortedBiTreeNode<E> pref = null;
   while (tempNode != null) {
    pref = tempNode;
    tempNode = tempNode.rChild;
   }
   return pref.element;
}

/**
* @function 得到树的元素个数
* @param none
* @return 返回树的结点个数
*/
public int size() {
   return this.capacity;
}
}