Subversion Repositories programming

Rev

Rev 100 | Blame | Compare with Previous | Last modification | View Log | RSS feed 

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

import java.io.*;

class Driver {
    public static void main ( String [] args ) throws Exception {
        BinaryTree tree1 = createTreeOne();
        BinaryTree tree2 = createTreeTwo();
        BinaryTree tree3 = createTreeThree();
        BinaryTree tree4 = createTreeOne();
        BinaryTree tree5 = createTreeThree(); //make a copy for later
        
        // ---- check getter methods ----
        System.out.println("Testing getter methods...");
        System.out.println("root: " + tree3.getRoot());
        System.out.println("left: " + tree3.getLeft());
        System.out.println("right: " + tree3.getRight());
        System.out.println();

        // ---- check setter and toString methods ----
        System.out.println("Testing setter and toString methods...");
        tree4.setRoot("A");
        tree4.setLeft( new BinaryTree("B"));
        tree4.setRight( new BinaryTree("C"));
        System.out.println("tree4: " + tree4 ); //should print ((A),B,(C))
        System.out.println();
        
        // ---- check misc methods ----
        System.out.println("Testing misc methods...");
        System.out.println("tree4.isLeaf(): " + tree4.isLeaf());
        System.out.println("tree4.left.isLeaf(): " + tree4.getLeft().isLeaf());
        System.out.println();
        
        System.out.println("tree3.size(): " + tree3.size());
        System.out.println();
        
        System.out.println("tree3.height(): " + tree3.height());
        System.out.println();
        
        System.out.println("tree3.contains(\"2\"): " + tree3.contains("2"));
        System.out.println("tree3.contains(\"zZ\"): " + tree3.contains("zZ"));
        System.out.println();
        
        System.out.println("tree3.numLeaves(): " + tree3.numLeaves());
        System.out.println("tree1.numLeaves(): " + tree1.numLeaves());
        System.out.println();
        
        System.out.println("tree3.count(\"s\"): " + tree3.count("s"));
        System.out.println("tree3.count(\"zZ\"): " + tree3.count("zZ"));
        System.out.println();
        
        System.out.println("tree3.isFull(): " + tree3.isFull());
        System.out.println("tree4.isFull(): " + tree4.isFull());
        System.out.println();
        
        System.out.println("tree3.isBalanced(): " + tree3.isBalanced());
        System.out.println("tree4.isBalanced(): " + tree4.isBalanced());
        System.out.println();
        
        System.out.println("tree3.pathLength(): " + tree3.pathLength());
        System.out.println("tree4.pathLength(): " + tree4.pathLength());
        System.out.println();
        
        System.out.println("tree4 = " + tree4);
        System.out.println("tree4.reverse() = " + tree4.reverse());
        System.out.println("tree2 = " + tree2);
        System.out.println("tree2.reverse() = " + tree2.reverse());
        System.out.println();

        System.out.println("tree1.level(\"H\"): " + tree1.level("H"));
        System.out.println("tree2.level(\"O\"): " + tree2.level("O"));
        System.out.println();

        System.out.println("tree4.isDisjointFrom(tree1): " 
            + tree4.isDisjointFrom(tree1));
        System.out.println("tree3.isDisjointFrom(new BinaryTree(\"s\"): "
            + tree3.isDisjointFrom(new BinaryTree("s")));
        System.out.println();

        System.out.println("tree1.isValid(): " + tree1.isValid());
        System.out.println("tree2.isValid(): " + tree2.isValid());
        System.out.println("tree3.isValid(): " + tree3.isValid());
        System.out.println();

        System.out.println("tree1.equals(tree3): " + tree1.equals(tree3));
        System.out.println("tree3.equals(tree5): " + tree3.equals(tree5));
        System.out.println();
        
        // ---- check print methods ----
        System.out.println("Testing Printing Methods...");

        // for tree1
        System.out.print("BinaryTree.preOrderPrint(tree1): ");
            BinaryTree.preOrderPrint(tree1); System.out.println();
        System.out.print("BinaryTree.inOrderPrint(tree1): ");
            BinaryTree.inOrderPrint(tree1); System.out.println();
        System.out.print("BinaryTree.postOrderPrint(tree1): ");
            BinaryTree.postOrderPrint(tree1); System.out.println();
        System.out.print("BinaryTree.levelOrderPrint(tree1): ");
            BinaryTree.levelOrderPrint(tree1); System.out.println();
        System.out.println();
        
        //for tree2
        System.out.print("BinaryTree.preOrderPrint(tree2): ");
            BinaryTree.preOrderPrint(tree2); System.out.println();
        System.out.print("BinaryTree.inOrderPrint(tree2): ");
            BinaryTree.inOrderPrint(tree2); System.out.println();
        System.out.print("BinaryTree.postOrderPrint(tree2): ");
            BinaryTree.postOrderPrint(tree2); System.out.println();
        System.out.print("BinaryTree.levelOrderPrint(tree2): ");
            BinaryTree.levelOrderPrint(tree2); System.out.println();
        System.out.println();
        
        //for tree3
        System.out.print("BinaryTree.preOrderPrint(tree3): ");
            BinaryTree.preOrderPrint(tree3); System.out.println();
        System.out.print("BinaryTree.inOrderPrint(tree3): ");
            BinaryTree.inOrderPrint(tree3); System.out.println();
        System.out.print("BinaryTree.postOrderPrint(tree3): ");
            BinaryTree.postOrderPrint(tree3); System.out.println();
        System.out.print("BinaryTree.levelOrderPrint(tree3): ");
            BinaryTree.levelOrderPrint(tree3); System.out.println();
        System.out.println();
    }
    
    public static BinaryTree createTreeOne() {
        return new BinaryTree("H");
    }

    public static BinaryTree createTreeTwo() {
        BinaryTree treeA = new BinaryTree("A");
        BinaryTree treeC = new BinaryTree("C");
        BinaryTree treeE = new BinaryTree("E");
        BinaryTree treeG = new BinaryTree("G");
        BinaryTree treeI = new BinaryTree("I");
        BinaryTree treeK = new BinaryTree("K");
        BinaryTree treeM = new BinaryTree("M");
        BinaryTree treeO = new BinaryTree("O");

        BinaryTree treeB = new BinaryTree("B",treeA,treeC);
        BinaryTree treeF = new BinaryTree("F",treeE,treeG);
        BinaryTree treeJ = new BinaryTree("J",treeI,treeK);
        BinaryTree treeN = new BinaryTree("N",treeM,treeO);

        BinaryTree treeD = new BinaryTree("D",treeB,treeF);
        BinaryTree treeL = new BinaryTree("L",treeJ,treeN);

        BinaryTree treeH = new BinaryTree("H",treeD,treeL);

        return treeH;
    }

    public static BinaryTree createTreeThree() {
        BinaryTree tree_2 = new BinaryTree("2");
        BinaryTree tree_a1 = new BinaryTree("a");
        BinaryTree tree_t1 = new BinaryTree("t");
        BinaryTree tree_c1 = new BinaryTree("c");
        BinaryTree tree_a2 = new BinaryTree("a");

        BinaryTree tree_s1 = new BinaryTree("s",null,tree_2);
        BinaryTree tree_n = new BinaryTree("n");
        BinaryTree tree_s2 = new BinaryTree("s",tree_a1,tree_t1);
        BinaryTree tree_a3 = new BinaryTree("a");
        BinaryTree tree_l1 = new BinaryTree("l",tree_c1,tree_a2);

        BinaryTree tree_c2 = new BinaryTree("c",null,tree_s1);
        BinaryTree tree_i1 = new BinaryTree("i");
        BinaryTree tree_t2 = new BinaryTree("t",tree_n,tree_s2);
        BinaryTree tree_l2 = new BinaryTree("l");
        BinaryTree tree_t3 = new BinaryTree("t",tree_a3,tree_l1);
        BinaryTree tree_s3 = new BinaryTree("s");

        BinaryTree tree_4 = new BinaryTree("4",tree_c2,null);
        BinaryTree tree_s4 = new BinaryTree("s",tree_i1,null);
        BinaryTree tree_f = new BinaryTree("f");
        BinaryTree tree_i2 = new BinaryTree("i",tree_t2,null);
        BinaryTree tree_a4 = new BinaryTree("a");
        BinaryTree tree_y = new BinaryTree("y",tree_l2,null);
        BinaryTree tree_r = new BinaryTree("r");
        BinaryTree tree_s5 = new BinaryTree("s",tree_t3,tree_s3);
        
        BinaryTree tree_1 = new BinaryTree("1",tree_4,tree_s4);
        BinaryTree tree_a5 = new BinaryTree("a",tree_f,tree_i2);
        BinaryTree tree_l3 = new BinaryTree("l",tree_a4,tree_y);
        BinaryTree tree_e = new BinaryTree("e",tree_r,tree_s5);
        
        BinaryTree tree_a6 = new BinaryTree("a",tree_1,tree_a5);
        BinaryTree tree_g = new BinaryTree("g",tree_l3,tree_e);
        
        BinaryTree tree_c3 = new BinaryTree("c",tree_a6,tree_g);

        return tree_c3;
    }
    
    public static void run_BinaryTree_tests() {
        System.out.println( test_12_2() );
        System.out.println( test_12_3() );
        System.out.println( test_12_4() );
        System.out.println( test_12_5() );
        System.out.println( test_12_6() );
        System.out.println( test_12_7() );
        System.out.println( test_12_8() );
        System.out.println( test_12_9() );
        System.out.println( test_12_10());
        System.out.println( test_12_11());
        System.out.println( test_12_12());
        System.out.println( test_12_13());
        System.out.println( test_12_14());
        System.out.println( test_12_15());
        System.out.println( test_12_16());

        System.out.println(); //print a blank line
        test_traversals();

    } //end main test method

    public static BinaryTree createTestTree() {
        BinaryTree treeB = new BinaryTree("B");
        BinaryTree treeD = new BinaryTree("D");
        BinaryTree treeE = new BinaryTree("E");
        BinaryTree treeC = new BinaryTree("C",treeD,treeE);
        BinaryTree treeA = new BinaryTree("A",treeB,treeC);
        
        return treeA;
    }

    public static String test_12_2() {
        BinaryTree treeA = createTestTree();
        
        String experimentalResult = treeA.toString();
        String correctResult = "((B),A,((D),C,(E)))";

        if( correctResult.equals(experimentalResult) )
            return "test_12_2: PASSED";

        return "test_12_2: *** FAILED ***";
    }
    
    public static String test_12_3() {
        BinaryTree treeA = createTestTree();
        BinaryTree treeAleft = treeA.getLeft();

        if( treeA.isLeaf() == false && treeAleft.isLeaf() == true )
            return "test_12_3: PASSED";

        return "test_12_3: *** FAILED ***";
    }

    public static String test_12_4() {
        BinaryTree treeA = createTestTree();
        int correctResult = 5;
        int experimentalResult = treeA.size();

        if( correctResult == experimentalResult )
            return "test_12_4: PASSED";

        return "test_12_4: *** FAILED ***";
    }

    public static String test_12_5() {
        BinaryTree treeA = createTestTree();
        int correctResult = 2;
        int experimentalResult = treeA.height();

        if( correctResult == experimentalResult )
            return "test_12_5: PASSED";

        return "test_12_5: *** FAILED ***";
    }

    public static String test_12_6() {
        BinaryTree treeA = createTestTree();
        
        if( treeA.contains("B") &&
            treeA.contains("A") &&
            treeA.contains("D") &&
           !treeA.contains("Z") ) return "test_12_6: PASSED";

        return "test_12_6: *** FAILED ***";
    }

    public static String test_12_7() {
        BinaryTree treeA = createTestTree();
        int correctResult = 3;

        if( correctResult == treeA.numLeaves() )
            return "test_12_7: PASSED";

        return "test_12_7: *** FAILED ***";
    }
    
    public static String test_12_8() {
        BinaryTree treeA = createTestTree();
        BinaryTree tree = new BinaryTree("E",treeA,new BinaryTree("E"));

        int correctResult = 3;
        
        if( correctResult == tree.count("E") )
            return "test_12_8: PASSED";

        return "test_12_8: *** FAILED ***";
    }

    public static String test_12_9() {
        BinaryTree treeA = createTestTree();

        if( treeA.isFull() == false ) { return "test_12_9: PASSED"; }
        return "test_12_9: *** FAILED ***";
    }

    public static String test_12_10() {
        BinaryTree treeA = createTestTree();

        if( treeA.isBalanced() == true ) { return "test_12_10: PASSED"; }
        return "test_12_10: *** FAILED ***";
    }
    
    public static String test_12_11() {
        BinaryTree treeA = createTestTree();
    
        if( treeA.pathLength() == 6 ) { return "test_12_11: PASSED"; }
        return "test_12_11: *** FAILED *** val:" + treeA.pathLength();
    }
    
    public static String test_12_12() {
        BinaryTree treeA = createTestTree();
        
        String correctAnswer = "(((E),C,(D)),A,(B))";
        
        if( treeA.reverse().toString().equals(correctAnswer) ) {
            return "test_12_12: PASSED";
        }

        return "test_12_12: *** FAILED *** " + treeA.reverse();
    }
    
    public static String test_12_13() {
        BinaryTree treeA = createTestTree();

        if( treeA.level("E") == 2 ) { return "test_12_13: PASSED"; }
        return "test_12_13: *** FAILED ***";
    }
    
    public static String test_12_14() {
        BinaryTree treeA = createTestTree();
        BinaryTree treeB = new BinaryTree("B");
        
        if( treeA.isDisjointFrom(treeB) ) {
            return "test_12_14: *** FAILED ***";
        }

        return "test_12_14: PASSED";
    }

    public static String test_12_15() {
        BinaryTree treeA = createTestTree();

        if( treeA.isValid() ) { return "test_12_15: PASSED"; }
        return "test_12_15: *** FAILED ***";
    }
    
    public static String test_12_16() {
        BinaryTree tree1 = createTestTree();
        BinaryTree tree2 = createTestTree();

        if( tree1.equals(tree2) ) { return "test_12_16: PASSED"; }
        return "test_12_16: *** FAILED ***";
    }
    
    public static void test_traversals() {
        BinaryTree treeA = createTestTree();
        
        //print the correct answers
        System.out.println("Should Be:");
        System.out.println("PreOrder: A B C D E");
        System.out.println("PostOrder: B D E C A");
        System.out.println("LevelOrder: A B C D E");
        System.out.println("InOrder: B A D C E");

        //print the actual answers
        System.out.println();
        System.out.println("Actually is:");
        System.out.print("PreOrder: "); BinaryTree.preOrderPrint(treeA); 
        System.out.println();
        System.out.print("PostOrder: "); BinaryTree.postOrderPrint(treeA);
        System.out.println();
        System.out.print("LevelOrder: "); BinaryTree.levelOrderPrint(treeA);
        System.out.println();
        System.out.print("InOrder: "); BinaryTree.inOrderPrint(treeA);
        System.out.println();
    }

} //end class Driver