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

*/