Lab 7 Feedback
Marking scheme:
--------------------
1.9 / 2 -some unit tests failed; TAs, please check for errors
--------------------
TA Comments:
-in breadthFirst you forgot to add the root node to the queue
--------------------
Style checker output:
No style errors found by checkstyle; TAs, please check for poorly named
variables, unusual programming constructs, and other style errors.
--------------------
Unit tester output:
YOUR SUMBISSION FAILED SOME UNIT TESTS
Here is the test output:
java -classpath .:/home/burton/work/teaching/2017F/2030/marking/lab7/_jar/* org.junit.runner.JUnitCore eecs2030.lab7.Lab7Suite
JUnit version 4.12
.................E.E.E.E
Time: 0.024
There were 4 failures:
1) test04b_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree with one element expected:<[hello]> but was:<[]>
2) test04c_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree with two elements expected:<[hello, goodbye]> but was:<[]>
3) test04d_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree with three elements expected:<[hello, goodbye, salut]> but was:<[]>
4) test04e_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree in lab document expected:<[50, 27, 73, 08, 44, 83, 73, 93]> but was:<[]>
FAILURES!!!
Tests run: 20, Failures: 4
--------------------
Your submission:
package eecs2030.lab7;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* A utility class that provides methods for traversing a binary
* search tree.
*
*/
public class TreeTraversal {
private TreeTraversal() {
// empty by design
}
/**
* Returns the list of strings formed by traversing the specified tree using
* an inorder traversal.
*
* @param tree
* a binary search tree
* @return the list of strings formed by traversing the specified tree using
* an inorder traversal
*/
public static List<String> inorder(BinarySearchTree<String> tree) {
return TreeTraversal.inorder(tree.root());
// YOU SHOULD IMPLEMENT inorder(INode) below
}
/**
* Returns the list of strings formed by traversing the specified tree using
* a preorder traversal.
*
* @param tree
* a binary search tree
* @return the list of strings formed by traversing the specified tree using
* a preorder traversal
*/
public static List<String> preorder(BinarySearchTree<String> tree) {
return TreeTraversal.preorder(tree.root());
// YOU SHOULD IMPLEMENT preorder(INode) below
}
/**
* Returns the list of strings formed by traversing the specified tree using
* a postorder traversal.
*
* @param tree
* a binary search tree
* @return the list of strings formed by traversing the specified tree using
* a postorder traversal
*/
public static List<String> postorder(BinarySearchTree<String> tree) {
return TreeTraversal.postorder(tree.root());
// YOU SHOULD IMPLEMENT postorder(INode) below
}
/**
* Returns the list of strings formed by traversing the specified tree using
* a breadth first traversal. The traversal visits nodes of the tree
* starting at the root moving left to right for each level of the tree.
*
* @param tree
* a binary search tree
* @return the list of strings formed by traversing the specified tree using
* a breadth first traversal
*/
public static List<String> breadthFirst(BinarySearchTree<String> tree) {
List<String> result = new ArrayList<>();
INode<String> root = tree.root();
if (root == null) {
return result;
}
// in Java, a LinkedList is a Queue
// to enqueue a node, use the Queue method add
// to dequeue a node, use the Queue method remove
Queue<INode<String>> q = new LinkedList<>();
while (!q.isEmpty())
{
INode<String> n = q.remove();
result.add(n.data());
if (n.left() != null)
{
q.add(n.left());
}
if (n.right() != null)
{
q.add(n.right());
}
}
return result;
}
/**
* Returns the list of strings formed by traversing a tree having the
* specified root using an inorder traversal.
*
* @param root
* the root of the tree
* @return the list of strings formed by traversing a tree having the
* specified root using an inorder traversal
*/
private static List<String> inorder(INode<String> root) {
List<String> result = new ArrayList<>();
if (root == null)
{
return result;
}
result.addAll(inorder(root.left()));
result.add(root.data());
result.addAll(inorder(root.right()));
return result;
}
/**
* Returns the list of strings formed by traversing a tree having the
* specified root using a preorder traversal.
*
* @param root
* the root of the tree
* @return the list of strings formed by traversing a tree having the
* specified root using a preorder traversal
*/
private static List<String> preorder(INode<String> root) {
List<String> result = new ArrayList<>();
if (root == null)
{
return result;
}
result.add(root.data());
result.addAll(preorder(root.left()));
result.addAll(preorder(root.right()));
return result;
}
/**
* Returns the list of strings formed by traversing a tree having the
* specified root using a postorder traversal.
*
* @param root
* the root of the tree
* @return the list of strings formed by traversing a tree having the
* specified root using a postorder traversal
*/
private static List<String> postorder(INode<String> root) {
List<String> result = new ArrayList<>();
if (root == null)
{
return result;
}
result.addAll(postorder(root.left()));
result.addAll(postorder(root.right()));
result.add(root.data());
return result;
}
}