treeAlgorithms/TestTree.java

Go to the documentation of this file.

package treeAlgorithms;

import static org.junit.Assert.*;

import java.util.ArrayList;

import org.junit.Test;

public class TestTree {

    @Test
    public void testOrderedCheck() {
        TreeNode<Integer> four = new TreeNode<Integer>(4);
        TreeNode<Integer> six = new TreeNode<Integer>(6);
        TreeNode<Integer> eight = new TreeNode<Integer>(8);
        TreeNode<Integer> twelve = new TreeNode<Integer>(12);
        TreeNode<Integer> ten = new TreeNode<Integer>(10);
        TreeNode<Integer> thirteen = new TreeNode<Integer>(13);
        TreeNode<Integer> sixteen = new TreeNode<Integer>(16);
        TreeNode<Integer> thirtyTwo = new TreeNode<Integer>(32);
        TreeNode<Integer> sixtyFour = new TreeNode<Integer>(64);
        six.setLeft(four);
        twelve.setLeft(ten);
        twelve.setRight(thirteen);
        eight.setLeft(six);
        eight.setRight(twelve);
        thirtyTwo.setRight(sixtyFour);
        sixteen.setLeft(eight);
        sixteen.setRight(thirtyTwo);
        assertTrue("Tree is ordered by was not recognized", Algorithms.isOrdered(sixteen));
        eight.setValue(96);
        assertFalse("Tree is not ordered but was not recognized", Algorithms.isOrdered(sixteen));
        eight.setValue(8);
        thirteen.setValue(5);
        assertFalse("Tree is not ordered but was not recognized", Algorithms.isOrdered(sixteen));
    }

    @Test
    public void testStringTreeBuild() {
        final String[] words = new String[] { "t'was", "brillig", "and", "the",
                "slighty", "toves", "did", "gyre", "and", "gimble", "in",
                "the", "wabe", "all", "mimsy", "were", "the", "borogroves",
                "and", "moonraths", "outgrabe" };
        TreeBuilder<String> builder = new TreeBuilder<String>();
        for (String word : words) {
            builder.addNode(word);
        }
        TreeNode<String> root = builder.getTree();
        assertTrue("String tree is not ordered", Algorithms.isOrdered(root));
    }

    @Test
    public void testInOrder() {
        class OrderedVisit<T extends Comparable<T>> implements
                Algorithms.NodeVisitor<T> {
            private ArrayList<T> mValues = new ArrayList<T>();

            @Override
            public void visit(TreeNode<T> node) {
                Comparable<T> val = node.getValue();
                mValues.add((T) val);
            }

            public ArrayList<T> getValues() {
                return mValues;
            }
        } // class OrderedVisit

        Character vals[] = new Character[] { 'A', 'B', 'D', 'E', 'H', 'I', 'F',
                'C', 'G' };
        Character ordered[] = new Character[] { 'A', 'B', 'C', 'D', 'E', 'F',
                'G', 'H', 'I' };
        TreeBuilder<Character> builder = new TreeBuilder<Character>(vals);
        TreeNode<Character> root = builder.getTree();
        OrderedVisit<Character> visitor = new OrderedVisit<Character>();
        Algorithms.inOrder(root, visitor);
        ArrayList<Character> treeVals = visitor.getValues();
        int ix = 0;
        boolean OK = true;
        for (Character ch : ordered) {
            if (!ch.equals(treeVals.get(ix))) {
                OK = false;
            }
            ix++;
        }
        assertTrue("In order traversal failed", OK);
    }

}