Description

Learning Outcomes

• Understand the linked list implementation of a binary tree
• Design and implement operations in the tree structure
• Apply recursion to traversals and other algorithms in a binary tree
• Pre-Lab

• Create a new Java project called Lab10
• Download the files: java, LinkedBinaryTree.java, ArrayList.java,

ArrayUnorderedList.java, ArrayIterator.java, BinaryTreeADT.java, ListADT.java,

ElementNotFoundException.java, EmptyCollectionException.java, LinkedQueue.java,

QueueADT.java, LinearNode.java, TestBinaryTree.java, and UnorderedListADT.java     Save these downloaded files into the Lab10 src folder

Exercise 1 – Completing the BinaryTreeNode class

1. Open BinaryTreeNode.java. Note that it is currently very short.

2. Add the following getter methods: .
3. Add the following setter methods: , and setRight(newRight).

Exercise 2 – Completing the LinkedBinaryTree class

1. Open LinkedBinaryTree.java. Note that there are several errors throughout this file, although not as many now as there were before you completed the above exercise (since the getters and setters in BinaryTreeNode are called many times from this class).
2. Complete the method getDataRoot() to return the data item stored in the root of the tree.

3. Complete the method to return true if the tree is empty and false otherwise
4. Complete the method to return 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 get stuck, then read this hint.

LAB 10                                                     Computer Science Fundamentals II

5. Complete the method contains(BinaryTreeNode<T> r, T targetElement) to return 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 get stuck, then read this hint.
6. Complete the methods iteratorPreOrder() and preorder() to work together to construct an iterator that recursively traverses the tree in pre-order (see note below).
7. Complete the methods iteratorPostOrder() and postorder() to work together to construct an iterator that recursively traverses the tree in post-order (see note below). 8. If you need help with any of the preorder or postorder iterator methods, read class TestBinaryTree.java to learn how to use the iterator. You can also model your code for these methods on the existing iteratorInOrder() and inorder() The main change you will need to make is where the node is being visited.
8. Complete the method iteratorLevelOrder() to return an iterator containing the data stored in the nodes of the tree in level order. This method is not recursive. Use class LinkedQueue.java as the auxiliary data structure needed to perform a level order traversal of the tree. Review 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;)
9. Open TestBinaryTree.java and run it. All 6 tests must pass to indicate that your code was entered correctly. If any of these tests are failing, use the Debugger and/or print lines to find the errors and fix them. Start by reviewing the BinaryTreeNode to check if you accidentally assigned a value to an incorrect variable.