CS206: Data Structures

Lab4: Sorted Binary Trees

Professor Blank

Goals:

  1. Use command-line javac and java
  2. Use JUnit for testing
  3. define BinaryTree and Node after textbook chapter 6
  4. Use generics

Rubric:

  1. Not only must you have the correct answer, but it must also be formatted with proper indentation.
  2. Points are assigned to each test

This lab is worth 100 points.

Due date: Wed, Feb 22, 2017, beginning of lab.

[Your name in next cell as a level-2 header. Delete this line when done.]

[Enter your text here]

For this lab, we will use cells to merely create the Java files, and execute command-line commands.

For example, in the next cell we use the %%file magic to create a file named "Node.java"

Your code should add a constructor that takes a value. Node should have three properties:

  • left
  • right
  • value
In [ ]:
%%file Node.java

public class Node<T> {
   // your code here
}

In the next cell, we will call the command-line which will compile the file Node.java in the shell:

In [ ]:
! javac Node.java

We will create a new file, "TestNode.java" and write many JUnit tests to test every aspect of our code.

In [ ]:
%%file TestNode.java

import junit.framework.TestCase;
    
public class TestNode extends TestCase {
    public void testConstructor() {
        // add your tests here
    }
}

To compile this, we need to include the TestCase class. We do this by including the junit4.jar file on the Java Class Path:

In [ ]:
! javac -cp /usr/share/java/junit4.jar:. TestNode.java

Finally, we can now run the TestNode tests:

In [ ]:
! java -cp /usr/share/java/junit4.jar:. org.junit.runner.JUnitCore TestNode

Now, your turn. Do the same thing with your BinaryTree class. That is:

  • first, define the class
  • compile it
  • create a TestBinaryTree.java file
  • write lots of tests
  • compile it
  • run it

You should be able to create a BinaryTree like:

BinaryTree<Integer> bt = new BinaryTree<Integer>();
bt.add(56);

The BinaryTree class should have five methods (based on code in chapter 6 of textbook):

  1. bt.add(value); - inserts value in tree in sorted position, if it isn't already there
  2. bt.print(); - prints tree out in nice way
  3. bt.count(); - counts the number of Nodes in tree
  4. bt.depth(); - returns the maximum depth of tree
  5. bt.contains(value); - returns true if the tree contains value

add(VALUE) should take a value and insert it into the tree in its correct, sorted position (if that value is not already in the tree).

print() should print out tree in a manner that you can see the Binary tree shape

count() should return number of nodes in tree

depth() should return the maxium depth of tree. A tree with one node is depth 1.

contains(VALUE) returns true if the tree contains VALUE, and false otherwise.

In [ ]:
%%file BinaryTree.java

public class BinaryTree<T> {
    // paste your code here
}
In [ ]:
! javac BinaryTree.java

As before, make sure you test all of your code.

In [ ]:
%%file TestBinaryTree.java

import junit.framework.TestCase;

public class TestBinaryTree extends TestCase {
    // put your code here
}
In [ ]:
! javac -cp /usr/share/java/junit4.jar:. TestBinaryTree.java
In [ ]:
! java -cp /usr/share/java/junit4.jar:. org.junit.runner.JUnitCore TestBinaryTree

Reflections

The reflection cell is the most import cell in this lab... in all labs. In your reflection, you should:

  • Reflect! Think and comment on what you have learned this lab, and this week.
  • Connect the ideas onto your own life, and experiences.
  • Comment on what you found challenging, and what you found intuitive.
  • How did this lab match your expectations?

Put your reflections in the cell below. You should write more than a paragraph. Remember:

  • don't indent paragraphs
  • use Markdown highlighting
  • use the spell checker

You should delete all of the cells except yours when you are done. Make sure to submit your lab.

[Please enter your text here]