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); }

    }

}