Lab 7 Feedback
Marking scheme:
--------------------
1.2 / 2 -some unit tests failed; TAs, please check for errors
--------------------
TA Comments:
-in inorder, preorder, and postorder, you need the results of the recursive traversals:
private static List<String> inorder(INode<String> root) {
List<String> result = new ArrayList<>();
if (root == null) {
return result;
}
List<String> goLeft = TreeTraversal.inorder(root.left()); // you need this result
List<String> goRight = TreeTraversal.inorder(root.right()); // you need this result
result.addAll(goLeft);
result.add(root.data());
result.addAll(goRight);
return result;
}
the preorder and postorder traversals are similar, except that you recursively
perform preorder and postorder traversals
-in breadthFirst, you should follow the instructions in the lab document:
public static List<String> breadthFirst(BinarySearchTree<String> tree) {
List<String> result = new ArrayList<>();
INode<String> root = tree.root();
// 1. If the node is null then return.
if (root == null) {
return result;
}
// 2. Create an empty queue q of nodes.
Queue<INode<String>> q = new LinkedList<>();
// 3. Add the root node
q.add(root);
// 4. While q is not empty
while (!q.isEmpty()) {
// i) Dequeue the node n from the front of q
INode<String> n = q.remove();
// ii) Visit n
result.add(n.data());
// iii) If n has a left child then enqueue the left child in q
if (n.left() != null) {
q.add(n.left());
}
// iv) If n has a right child then enqueue the right child in q
if (n.right() != null) {
q.add(n.right());
}
}
return result;
}
--------------------
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.E.E
Time: 0.023
There were 6 failures:
1) test02e_preorder(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree in lab document expected:<[50, 27, 08, 44, 73, 83, 73, 93]> but was:<[50, 08, 27, 44, 73, 73, 83, 93]>
2) test03e_postorder(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree in lab document expected:<[08, 44, 27, 73, 93, 83, 73, 50]> but was:<[08, 27, 44, 73, 73, 83, 93, 50]>
3) test04b_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree with one element expected:<[hello]> but was:<[]>
4) test04c_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree with two elements expected:<[hello, goodbye]> but was:<[]>
5) test04d_breadthFirst(eecs2030.lab7.TreeTraversalTest)
java.lang.AssertionError: failed for tree with three elements expected:<[hello, goodbye, salut]> but was:<[]>
6) 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: 6
--------------------
Your submission:
package eecs2030.lab7;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import javax.swing.tree.TreeNode;
/**
* A utility class that provides methods for traversing a binary search tree.
*
*/
public class TreeTraversal {
private TreeTraversal() {
// empty by design
}
static List<String> result = new ArrayList<>();
/**
* 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) {
result.clear();
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) {
result.clear();
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) {
result.clear();
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<>();
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) {
if (root == null) {
return result;
}
TreeTraversal.inorder(root.left());
result.add(root.data());
TreeTraversal.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) {
if (root == null) {
return result;
}
result.add(root.data());
TreeTraversal.inorder(root.left());
TreeTraversal.inorder(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) {
if (root == null) {
return result;
}
TreeTraversal.inorder(root.left());
TreeTraversal.inorder(root.right());
result.add(root.data());
return result;
}
}