Subversion Repositories programming

// Written by Ira Snyder
// Due Date: 11-15-2004
// Project #3
// People Helped: Allen Oliver
// License: Public Domain (added 07-11-2005)

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 ) {
        root = that.root;
        left = null; right = null;
        
        if( that.left != null ) { left = new BinaryTree(that.left); }
        if( that.right != null ) { right = new BinaryTree(that.right); }
    }

    //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=0,r=0; 
        
        if( left != null ) { l = 1 + left.height(); }
        if( right != null ) { r = 1 + 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; }

        boolean l=false, r=false;
        if( left != null ) { l=left.contains(object); }
        if( right != null ) { r=right.contains(object); }
        
        return l || r;
    }
    
    // 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; }

        int l=0, r=0;

        if( left != null ) { l = left.numLeaves(); }
        if( right != null ) { r = right.numLeaves(); }
        
        return l + r;
    }
    
    // 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; }
        
        //get left and right heights as applicable
        int l=0, r=0;
        if( left != null ) { l = left.height(); }
        if( right != null ) { r = right.height(); }
        
        //check for the criteria of balance. If we are balanced, then
        //check our subtrees for balance recursively
        if( Math.abs( l-r ) < 2 ) {
            if( left != null && right != null ) //check both
                return left.isBalanced() && right.isBalanced();
            if( left != null ) //right is null (check left)
                return left.isBalanced();
            //left is null, right is not null
            return right.isBalanced(); //check right
        }
        return false; //the criteria of balance was not met
    }
    
    // method to get the total path length of the current tree
    // Precondition:  none
    // Postcondition: returns the sum of all the root to node paths in
    //                the tree
    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;
    }
    
    // method to create a reverse of the tree
    // Precondition:  none
    // Postcondition: returns a new BinaryTree with the structure
    //                reversed as if it were seen in a mirror
    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());
    }
        
    // a method to find the level of an object in the tree
    // Precondition:  x is not null
    // Postcondition: returns the level of the deepest object x in the tree
    public int level( Object x ) { 
        if( !this.contains(x) ) { return -1; }  //not found
        if( this.root.equals(x) ) { return 0; } //found here
        int ansLeft=0, ansRight=0;
        if( left != null ) { ansLeft = left.level(x); }
        if( right != null ) { ansRight = right.level(x); }
        
        int answer = Math.max(ansLeft,ansRight);
        if( answer >= 0 ) { return answer + 1; }
        return answer;
    }
    
    // method to check if the current tree is disjoint from "that" tree
    // disjoint: no element in both this tree and that tree
    // Precondition:  none
    // Postcondition: returns true if and only if no element from "that"
    //                tree is in "this" tree
    public boolean isDisjointFrom( BinaryTree that ) { 
        if( that == null ) { return true; }
        if( this.contains(that.root) ) { return false; }

        return isDisjointFrom(that.left) && isDisjointFrom(that.right);
    }
    
    // method to check if a tree is valid
    // valid: all of it's subtrees are disjoint
    // Precondition:  none
    // Postcondition: returns true if the tree is valid, false otherwise
    public boolean isValid() { 
        if( this.isLeaf() ) { return true; }
        boolean answer;
        
        if( left != null ) { answer = left.isDisjointFrom(right); }
        else { answer = right.isDisjointFrom(left); }

        return answer;
    }
    
    // method to check if one tree is equal to another
    // Precondition:  object should be a BinaryTree (this is checked anyway)
    // Postcondition: return true only if both trees are equal
    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; }
        
        if( left != null ) { //check left
            if( left.equals(x.left) ) { ansLeft = true; }
        }

        if( right != null ) { //check 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 ------------------------------------------------------

    // method to print the tree in the following order: root,left,right
    // Precondition:  none
    // Postcondition: the tree will be printed to System.out in preOrder
    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 ); }
    }
    
    // method to print the tree in the following order: left,right,root
    // Precondition:  none
    // Postcondition: the tree will be printed to System.out in postOrder
    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 + " " );
    }
    
    // method to print the tree by level
    // Precondition:  none
    // Postcondition: the tree will be printed to System.out by level
    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); }
        }   
    }
    
    // method to print the tree in the following order: left,root,right
    // Precondition:  none
    // Postcondition: the tree will be printed to System.out in inOrder
    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); }
    }
}