CS1027b Computer Science Fundamentals II

Learning Outcomes

• Understand the linked implementation of the Binary Tree ADT, and
• Understand how to implement binary tree operations.

General Lab Instructions

• Read through the lab instructions before coming to the lab.
• Read the lecture notes on trees.

IMPORTANT. Submit the .java files that you write for this lab through OWL by 11:55pm on Friday, April 3.

Exercise 1: Understanding the BinaryTreeNode and LinkedBinaryTree classes

• Download the file BinaryTreeNode.java and examine the code to see how the node is implemented. Add getter and setter methods for all the attributes: getData(), getLeft(), getRight(), setData(newData), setLeft(newLeft), and setRight(newRight).
• Download the files LinkedBinaryTree.java, ArrayList.java, ArrayUnorderedList.java, ArrayIterator.java, BinaryTreeADT.java, ElementNotFoundException.java, EmptyCollectionException.java, ListADT.java, LinkedQueue.java, QueueADT.java, LinearNode.java, TestBinaryTree.java, and UnorderedListADT.java.
• Complete the following methods in LinkedBinaryTree.java:
  • getDataRoot, returns the data item stored in the root of the tree
  • isEmpty, returns true if the tree is empty and false otherwise
  • size(BinaryTreeNode< T > r), returns the number of nodes in the subtree with root r. This method must be recursive. Please try to implement this method on your own. If you need help read this hint.
  • contains(BinaryTreeNode< T > r, T targetElement, returns true if the given targetElement is stored in any of the nodes in the subtree with root r. This method must be recursive. Please try to implement this method on your own. If you need help read this hint.
  • iteratorPreOrder, preorder, iteratorPostOrder, and postorder. The first two methods construct an iterator containing the information of the nodes of a tree stored in preorder; the last two methods construct an iterator containing the information on postorder.
    Note: An iterator is an abstract data type that allows us to iterate through the elements of a collection one by one. An iterator provides three operations:
    • next: returns the next element of the collection,
    • hasNext: returns true if there are more elements in the collection; returns false otherwise,
    • remove: removes the last element returned by the iterator.
    Read class TestBinaryTree.java to learn how to use an iterator.
    Hint: Model your code for the above methods on the methods iteratorInOrder and inorder of class LinkedBinaryTree. The main change that you need to make is where the node is visited in preorder and postorder.
  • iteratorLevelOrder, returns a iterator containing the data stored in the nodes of a tree in level order. This method is not recursive. Use class LinkedQueue as the auxiliary data structure needed to perform a level order traversal of the tree. Read the lecture notes on tree traversal. Note that in the queue you will store tree nodes, so what should be the value of the generic type for the declaration of the queue? (LinkedQueue< ??? > queue;)
  • To test your implementation, run program TestBinaryTree. All 6 test must pass; if your program fails any tests use the debugger to find the errors and fix them.