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() == false || right.isFull() == false )

            return false;

        return true;

    }

    // method to check if the tree is balanced

    // Precondition:  none

    // Postcondition: returns true if the tree is balanced, false otherwise

    public boolean isBalanced() { 

    }

    public int pathLength() { }

    public BinaryTree reverse() { }

    public int level( Object x ) { }

    public boolean isDisjointFrom( BinaryTree that ) { }

    public boolean isValid() { }

    public boolean equals( Object object ) { }

    //printing methods ------------------------------------------------------

    public static void preOrderPrint( BinaryTree tree ) { }

    public static void postOrderPrint( BinaryTree tree ) { }

    public static void levelOrderPrint( BinaryTree tree ) { }

    public static void inOrderPrint( BinaryTree tree ) { }

    */

}

/*

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

*/