Subversion Repositories programming

// Written by Ira Snyder
// Due Date: 11-15-2004
// Project #3

import java.io.*;
import java.util.*;
class BinaryTree {
    private Object root;
    private BinaryTree left, right;

    //constructors ----------------------------------------------------------
    
    // constructor to create a singleton tree
    // Precondition:  root is a non-null Object
    // Postcondition: returns a BinaryTree with the Object given as the root
    //                data, and null left and right subtrees
    public BinaryTree( Object root ) { 
        this.root = root;
        this.left = null;
        this.right = null;
    }
    
    // constructor to create a BinaryTree with the given Object as the root
    // data, and the given BinaryTrees as the left and right subtrees
    // Precondition:  root is a non-null Object (right and left CAN be null
    // Postcondition: returns a BinaryTree with the given root data and
    //                the given left and right subtrees
    public BinaryTree( Object root, BinaryTree left, BinaryTree right ) {
        this.root = root;
        this.left = left;
        this.right = right;
    }

    // copy constructor, creates a tree which has the same structure and
    // whose nodes reference the same objects as the _that_ tree
    public BinaryTree( BinaryTree that ) { 
        System.out.println("Don't use me yet");
    }

    //getter methods --------------------------------------------------------

    // method which returns the root data
    // Precondition:  none
    // Postcondition: return the root data
    public Object getRoot() { return root; }

    // method which will return a reference to the left subtree
    // Precondition:  none
    // Postcondition: returns a reference to the left subtree
    public BinaryTree getLeft() { return left; }

    // method which will return a reference to the right subtree
    // Precondition:  none
    // Postcondition: returns a reference to the right subtree
    public BinaryTree getRight() { return right; }

    //setter methods --------------------------------------------------------

    // method which updates the root data
    // Precondition:  root is non-null
    // Postcondition: sets this.root to the new data, returns the old data
    public Object setRoot( Object root ) { 
        Object temp = this.root;
        this.root = root;
        return temp;
    }
    
    // method which updates the left subtree
    // Precondition:  none ( left CAN be null )
    // Postcondition: sets this.left to the new subtree,
    //                returns a reference to the old left subtree
    public BinaryTree setLeft( BinaryTree left ) { 
        BinaryTree temp = this.left;
        this.left = left;
        return temp;
    }

    // method which update the right subtree
    // Precondition:  none ( right CAN be null )
    // Postcondition: sets this.right to the new subtree,
    //                returns a reference to the old right subtree
    public BinaryTree setRight( BinaryTree right ) {
        BinaryTree temp = this.right;
        this.right = right;
        return temp;
    }

    //toString method -------------------------------------------------------

    // returns a String representation of the BinaryTree
    // Precondition:  none
    // Postcondition: returns a string representation of the BinaryTree
    public String toString() { 
        String sLeft = "";
        String sRight = "";
        String answer = new String();
        
        //get the left tree's string representation (if it exists)
        if( !(left == null) ) { sLeft = left.toString(); }
        
        //get the right tree's string representation (if it exists)
        if( !(right == null) ) { sRight = right.toString(); }
        
        //assemble the string to return
        answer = "(";
        if( !sLeft.equals("") ) { answer += sLeft + ","; }
        answer += root.toString();
        if( !sRight.equals("") ) { answer += "," + sRight; }
        answer += ")";
        
        //return the assembled string
        return answer;
    }
    
    //misc methods ----------------------------------------------------------
    
    // method to check if the current node is a leaf
    // Precondition:  none
    // Postcondition: returns true if the current node is a leaf, and false
    //                in any other case
    public boolean isLeaf() { 
        if( (left == null) && (right == null) ) { return true; }
        return false;
    }
    
    // method to find the size of the tree
    // Precondition:  none
    // Postcondition: returns the size of the tree
    public int size() { 
        int answer=1; // 1 for the node we are at
        if( !(left == null) ) { answer += left.size(); }
        if( !(right == null) ) { answer += right.size(); }

        return answer;
    }
    
    // method to calculate the height of the tree
    // Precondition:  none
    // Postcondition: returns the height of the tree
    public int height() {
        if( this.isLeaf() ) { return 0; }
        int l=1,r=1;
        l += left.height();
        r += right.height();

        return Math.max(l,r);
    }
    
    // method to search the tree for an object
    // Precondition:  object is non-null
    // Postcondition: returns true if the tree contains the object,
    //                and false if the tree doesn't contain the object
    public boolean contains( Object object ) { 
        if( root.equals(object) ) { return true; }
        if( this.isLeaf() ) { return false; }
        return left.contains(object) || right.contains(object);
    }
    
    // method to find the number of leaves in the tree
    // Precondition:  none
    // Postcondition: returns the number of leaves in the tree
    public int numLeaves() { 
        if( this.isLeaf() ) { return 1; }
        return left.numLeaves() + right.numLeaves();
    }
    
    // method to find the number of a certain object in the tree
    // Precondition:  the object in non-null
    // Postcondition: returns the number of the object that
    //                are in the tree
    public int count( Object x ) { 
        int answer=0;
        if( root.equals(x) ) { answer=1; }
        if( !(left == null) ) { answer += left.count(x); }
        if( !(right == null) ) { answer += right.count(x); }
        return answer;
    }
    
    // method to check if the tree is full
    // Precondition:  none
    // Postcondition: returns true if the tree is a full tree, 
    //                and false if the tree is not a full tree
    public boolean isFull() { 
        if( this.isLeaf() ) { return true; }
        if( !(left.height() == right.height()) ) { return false; }
        if( left.isFull() && right.isFull() ) { return true; }
        return false;
    }
    
    // method to check if the tree is balanced
    // Precondition:  none
    // Postcondition: returns true if the tree is balanced, false otherwise
    public boolean isBalanced() { 
        if( this.isLeaf() ) { return true; }
        if( Math.abs(left.height() - right.height()) < 2 ) { return true; }
        if( left.isBalanced() && right.isBalanced() ) { return true; }
        return false;
    }
    
    public int pathLength() {
        int answer=0;
        Queue queue = new Queue();
        queue.enqueue(this);

        while( !queue.isEmpty() ) {
            BinaryTree temp = (BinaryTree)queue.dequeue();
            answer += level(temp.root);
            if( temp.left != null ) { queue.enqueue(temp.left); }
            if( temp.right != null ) { queue.enqueue(temp.right); }
        }

        return answer;
    }
        
    public BinaryTree reverse() { 
        //both left and right are null
        if( this.isLeaf() ) { return new BinaryTree(root); }
        
        //left must be null, right must not be null
        if( this.left == null ) 
            return new BinaryTree(root,right.reverse(),null);

        //right must be null, left must not be null
        if( this.right == null )
            return new BinaryTree(root,null,left.reverse());
        
        //both sides are not null
        return new BinaryTree(root,right.reverse(),left.reverse());
    }
        
    public int level( Object x ) { 
        if( !this.contains(x) ) { return -1; }  //not found
        if( this.root.equals(x) ) { return 0; } //found here
        int ansLeft = left.level(x);
        int ansRight = right.level(x);
        
        int answer = Math.max(ansLeft,ansRight);
        if( answer >= 0 ) { return answer + 1; }
        return answer;
    }
    
    public boolean isDisjointFrom( BinaryTree that ) { 
        if( that == null ) { return true; }
        if( this.contains(that.root) ) { return false; }

        return isDisjointFrom(that.left) && isDisjointFrom(that.right);
    }
    
    public boolean isValid() { 
        if( this.isLeaf() ) { return true; }
        boolean answer;
        
        if( left != null ) { answer = left.isDisjointFrom(right); }
        else { answer = right.isDisjointFrom(left); }

        return answer;
    }
    
    public boolean equals( Object object ) {
        //if we are not a BinaryTree, return false
        if( !(object instanceof BinaryTree) ) { return false; } 
        BinaryTree x = (BinaryTree)object; //typed instance of Object
        
        //temporary answer holding variables
        boolean ansLeft=false, ansRight=false;
        
        //check for the root data equality
        if( !this.root.equals(x.root) ) { return false; }
        
        //need this check to make sure that the recursive operations are ok
        if( left != null && right != null ) {
            //check the left
            if( left.equals(x.left) ) { ansLeft = true; }
            //check the right
            if( right.equals(x.right) ) { ansRight = true; }
        }
        
        //if both are null, we are still okay
        if( left == null && x.left == null ) { ansLeft = true; }
        if( right == null && x.right == null ) { ansRight = true; }
        
        //check that both left and right are okay
        if( ansLeft == true && ansRight == true ) { return true; }
        return false; //return false if any condition was not met
    }
    
    
    //printing methods ------------------------------------------------------
    public static void preOrderPrint( BinaryTree tree ) { 
        System.out.print( tree.root + " " );
        if( tree.left != null ) { preOrderPrint( tree.left ); }
        if( tree.right != null ) { preOrderPrint( tree.right ); }
    }
    
    public static void postOrderPrint( BinaryTree tree ) { 
        if( tree.left != null ) { postOrderPrint( tree.left ); }
        if( tree.right != null ) { postOrderPrint( tree.right ); }
        System.out.print( tree.root + " " );
    }
    
    public static void levelOrderPrint( BinaryTree tree ) { 
        Queue queue = new Queue();
        queue.enqueue(tree);

        while( !queue.isEmpty() ) {
            BinaryTree temp = (BinaryTree)queue.dequeue();
            System.out.print( temp.root + " " );
            if( temp.left != null ) { queue.enqueue(temp.left); }
            if( temp.right != null ) { queue.enqueue(temp.right); }
        }   
    }
    
    public static void inOrderPrint( BinaryTree tree ) { 
        if( tree.left != null ) { inOrderPrint(tree.left); }
        System.out.print( tree.root + " " );
        if( tree.right != null ) { inOrderPrint(tree.right); }
    }
}

/*
      BufferedReader kb = new BufferedReader(
                              new InputStreamReader(System.in));


      BufferedReader br = new BufferedReader(
                              new InputStreamReader(
                                  new FileInputStream(filename)));

      PrintStream ps = new PrintStream(
                           new FileOutputStream(
                               new File(filename)));

*/