binsearchtree.java

数据结构与算法分析中binary search tree的JAVA代码 请需要的同学下载

import java.util.*;

public class BinSearchTree extends AbstractSet {

    protected Entry root;

    protected int size;


    // Postcondition: the number of elements in this BinSearchTree object 
    //                has been returned.
    public int size() {

        return size;

    } // method size()


    // Postcondition: true has been returned if this BinSearchTree object
    //                has no elements.  Otherwise, false has been returned.
    public boolean isEmpty() {

        return size == 0;

    } // method isEmpty
    


    // Postcondition: an iterator positioned at the first entry in
    //                this BinSearchTree has been returned.

    public Iterator iterator() {


        return new TreeIterator();


    } // method iterator


    // Postcondition: true has been returned if there is an element e in this
    //                BinSearchTree object such that o.equals (e).  
    //                Otherwise, false has been returned. The averageTime(n)
    //                is O(log n) and worstTime(n) is O(n).
    public boolean contains (Object o)  {

        Entry e = root;

        int comp;

        while (e != null) {

            comp =  ((Comparable)o).compareTo (e.element);
            if (comp == 0)
                return true;
            else if (comp < 0)
                e = e.left;
            else
                e = e.right;

        } // while
        return false;
    } // contains


    // Postcondition: if this BinSearchTree object contains an element equal
    //                to o, then false has been returned.  Otherwise, o 
    //                has been inserted where it belongs in this 
    //                BinSearchTree object and true has been returned. The 
    //                averageTime(n) is O(log n), and worstTime(n) is O(n).
    public boolean add (Object o) {
        
        if (root == null) {

            root = new Entry (o, null);
            size++;
            return true;

        } // empty tree
        else {

            Entry temp = root;

            int comp;

            while (true) {

                comp =  ((Comparable)o).compareTo (temp.element);
	        if (comp == 0)
	            return false;
                if (comp < 0)
                    if (temp.left != null)
                        temp = temp.left;
                    else {

                        temp.left = new Entry (o, temp);
                        size++;
                        return true;

                    } // temp.left == null
                else if (temp.right != null)
                    temp = temp.right;
                else {

                    temp.right = new Entry (o, temp);
                    size++;
                    return true;

                } // temp.right == null

            } // while

        } // root not null


    } // method add



    // Postcondition: if, before this call, this BinSearchTree object 
    //                contained an element equal to elem, then an element 
    //                equal to elem has been removed from this BinSearchTree 
    //                object and true has been returned. Otherwise, false 
    //                has been returned. The averageTime(n) is O(log n) and
    //                worstTime(n) is O(n).
    public boolean remove (Object elem) {

        Entry e = getEntry (elem);
	if (e == null)
            return false;
        deleteEntry (e);
        return true;

    } // method remove


    // Postcondition: the Entry p has been removed from this
    //                BinSearchTree.
    private void deleteEntry (Entry p) {

         size--;

	 if (p.left != null && p.right != null) {

             Entry s = successor (p);
             p.element = s.element;
             p = s;

         } // p has two children

	 Entry replacement;
         if (p.left != null)
             replacement = p.left;
         else
             replacement = p.right;

         // If p has at least one child, link replacement to p.parent.
	 if (replacement != null) {

   	    replacement.parent = p.parent;
            if (p.parent == null)
	        root = replacement;
	    else if (p == p.parent.left)
		p.parent.left  = replacement;
	    else
		p.parent.right = replacement;

          } // p has at least one child
	  else if (p.parent == null)
	      root = null;
	  else {

	      if (p == p.parent.left)
		  p.parent.left = null;
	      else if (p == p.parent.right)
		  p.parent.right = null;

	  } // p has a parent but no children

    } // method deleteEntry


    // Postcondition: if there is an Entry whose element is elem, such an
    //                Entry has been returned.  Otherwise, null has been
    //                returned. The averageTime(n) is O(log n) and 
    //                worstTime(n) is O(n).
    private Entry getEntry (Object elem) {

        int comp;

	Entry e = root;
	while (e != null) {

	    comp = ((Comparable)elem).compareTo (e.element);
	    if (comp == 0)
		return e;
	    else if (comp < 0)
		e = e.left;
	    else
		e = e.right;

        } // while
	return null;

    } // method getEntry


    // Postcondition: if e has a successor, that successor Entry has been
    //                returned.  Otherwise, null has been returned.
    private Entry successor (Entry e) {

        if (e == null)
	    return null;
	else if (e.right != null) {

            // successor is leftmost Entry in right subtree of e
	    Entry p = e.right;
	    while (p.left != null)
		p = p.left;
	    return p;

	} // e has a right child
        else {

            // go up the tree to the left as far as possible, then go up
            // to the right.
	    Entry p = e.parent;
	    Entry ch = e;
	    while (p != null && ch == p.right) {

		ch = p;
		p = p.parent;

	    } // while
	          return p;

	} // e has no right child

    } // method successor



  private static class Entry {

        Object element;

        Entry left = null,
              right = null,
              parent;

        // Postcondition: this Entry has been initialized from element and
        //                parent.
        Entry (Object element, Entry parent) {

            this.element = element;
            this.parent = parent;

        } // constructor

    } // class Entry



    private class TreeIterator implements Iterator {

	  private Entry lastReturned = null;
	  private Entry next;


          // Postcondition: next has been initialized to the smallest
          //                Entry in this BinSearchTree.
	  TreeIterator() {

              next = root;
              if (next != null)
                  while (next.left != null)
                      next = next.left;

          } // default constructor


          // Postcondition: true has been returned if this TreeIterator
          //                is not positioned beyond the end of the
          //                binary search tree.  Otherwise, false
          //                has been returned.
	  public boolean hasNext() {

	      return next != null;

	  } // method hasNext


          // Postcondition: the next element in the binary search tree
          //                has been returned.
	  public Object next() {

	      lastReturned = next;
	      next = successor(next);
	      return lastReturned.element;

	  } // method next


          // Precondition: the element that was last returned
          //               by this TreeIterator is still in the 
          //               BinSearchTree. 
          // Postcondition: the element last returned by this TreeIterator
          //                has been removed from the binary search tree.
	  public void remove() {

            if (lastReturned.left != null && lastReturned != null)
                next = lastReturned;
	    deleteEntry(lastReturned);
	    lastReturned = null;

	} // method remove

    } // class TreeIterator



} // class BinSearchTree