BinaryTree.java

import java.util.*;
 
public class BinaryTree extends AbstractCollection
{ 
  protected Object root;
  protected BinaryTree left, right, parent;
  protected int size;
 
  public BinaryTree()
  {
  }
 
  public BinaryTree(Object root)
  { this.root = root;
    size = 1;
  }
 
  public BinaryTree(Object root, BinaryTree left, BinaryTree right)
  { 
    this(root);
    if (left != null)
    { 
      this.left = left;
        left.parent = this;
        size += left.size();
    }
    if (right != null)
    { 
      this.right = right;
        right.parent = this;
        size += right.size();
    }
  }
 
  public boolean equals(Object object)
  { 
    if (!(object instanceof BinaryTree)) 
      return false;
    BinaryTree tree = (BinaryTree)object;
    return ( tree.root.equals(root) && tree.left.equals(left)
              && tree.right.equals(right)  && tree.parent.equals(parent)
              && tree.size == size);
  }
 
  public int hashCode()
  { return root.hashCode() + left.hashCode() + right.hashCode() + size;
  }
 
  public java.util.Iterator iterator()
  { 
    return new java.util.Iterator()  // anonymous inner class
    { 
      private boolean rootDone;
      private java.util.Iterator lit, rit;  // child iterators
 
      public boolean hasNext()
      { return !rootDone || lit != null && lit.hasNext()
                         || rit != null && rit.hasNext();
      }
      public Object next()
      { if (rootDone)
        { if (lit != null && lit.hasNext()) 
              return lit.next();
          if (rit != null && rit.hasNext()) 
              return rit.next();
          return null;
        }
        if (left != null) 
            lit = left.iterator();
        if (right != null) 
            rit = right.iterator();
        rootDone = true;
        return root;
      }
      public void remove()
      { throw new UnsupportedOperationException(); 
      }
    };
  }
 
  public int size()
  { return size;
  }
//*  
  abstract public class Iterator 
  {   
      protected boolean rootDone;
      protected Iterator lit, rit;  // child iterators
 
      public boolean hasNext()
      { return !rootDone || lit != null && lit.hasNext()
                         || rit != null && rit.hasNext();
      }
 
      abstract public Object next();
 
      public void remove()
      { throw new UnsupportedOperationException(); 
      }
  }
 
  public class PreOrder extends Iterator
  {
    public PreOrder()
    {
      if (left!=null)
        lit=left.new PreOrder();
     if (right!=null)
        rit=right.new PreOrder();
    }
    public Object next()
    { 
        if (!rootDone)
        { 
           rootDone=true;
           return root;
        }   
        if (lit != null && lit.hasNext()) 
            return lit.next();
        if (rit != null && rit.hasNext()) 
            return rit.next();
        return null;
    }
  }
 
 
  public class InOrder extends Iterator
  {
    public InOrder()
    {
      if (left!=null)
        lit=left.new InOrder();
     if (right!=null)
        rit=right.new InOrder();
    }
    public Object next()
    { 
        if (lit != null && lit.hasNext()) 
            return lit.next();
        if (!rootDone)
        { 
           rootDone=true;
           return root;
        }   
        if (rit != null && rit.hasNext()) 
            return rit.next();
        return null;
    }
  }
 
  public class PostOrder extends Iterator
  {
    public PostOrder()
    {
      if (left!=null)
        lit=left.new PostOrder();
     if (right!=null)
        rit=right.new PostOrder();
    }
    public Object next()
    { 
        if (lit != null && lit.hasNext()) 
            return lit.next();
        if (rit != null && rit.hasNext()) 
            return rit.next();
        if (!rootDone)
        { 
           rootDone=true;
           return root;
        }   
        return null;
    }
  }
 
  public class LevelOrder extends Iterator
  {
    ArrayQueue q =  new ArrayQueue();
 
    public boolean hasNext()
      { return (!rootDone || !q.isEmpty());
      }
 
    public Object next()
    { 
        if (!rootDone)
        { 
          if (left != null) 
            q.enqueue(left);
          if (right != null) 
            q.enqueue(right);
          rootDone=true;
          return root;
        }   
        if (!q.isEmpty())
        { 
          BinaryTree t = (BinaryTree) q.dequeue();
          if (t.left != null) 
            q.enqueue(t.left);
          if (t.right != null) 
            q.enqueue(t.right);
          return t.root;
        }
        return null;   
    }
  }
//*/
}