CS20b Tree and Binary Tree

Project 3a

Working With First-Child Next-Sibling Tree Representation

Complete the required exercise using the cs20b.tree.Tree class presented in class as well as one of the choice exercises.

• (REQUIRED) Implement either a PreOrder or PostOrder TreeIterator using the TreeIterator class as the base class of the class you create.
• (CHOOSE ONE) Without using a TreeIterator, create a new method called isAncestor that takes two IComparables and returns true when the first one is the ancestor of the second. If either parameter is not found in the tree, your method should throw the InvalidTreeArgument exception. The prototype for this method should be: bool isAncestor( Type ancestor, Type descendant ) throws InvalidTreeArgument;
• (CHOOSE ONE) Without using a TreeIterator, create a new method called findMin that takes no arguments and returns the minimum IComparable found in this binary tree. If the root of the tree is null, your method should throw the InvalidTreeArgument exception. The prototype for this method should be: Type findMin( ) throws InvalidTreeArgument; Create a test driver program that exercises each of these methods, prints the tree and the results of each operation.

Project 3b

Complete the required exercise using the cs20b.binarytree.BinaryTree class presented in class as well as one of the choice exercises.

• (REQUIRED) Implement a PreOrder or PostOrder TreeIterator using the TreeIterator class as the base class of the class you create.
• (CHOOSE ONE) Without using a TreeIterator, create a new method called level that takes no arguments and calculates the level value for this binary tree. Recall that the level value for a tree will match the greatest level value of each and every node in this tree. If the root of the tree is null, your method should throw the InvalidTreeArgument exception. The prototype for this method should be: bool level( ) throws InvalidTreeArgument;
• (CHOOSE ONE) Without using a TreeIterator, create a new method called isLeaf that takes an IComparable and attempts to located its corresponding TreeNode inside this tree. If it finds such a TreeNode, this method should return true if that TreeNode is in fact a leaf in this tree; return false otherwise. If the root of the tree is null, your method should throw the InvalidTreeArgument exception. The prototype for this method should be: bool isLeaf( Type data ) throws InvalidTreeArgument;

Create a test driver program that exercises each of these exercises and prints the tree before and after each operation.