Due Date: Friday, Feb. 22, 2013, 23:59:59
Weight:
4%
Using the BST interface from project two, solve the following problems recursively. Submit a java source code file to the Curator. Comment your code and implement as efficiently as possible.
1. Sentinel Node
One slight variation to binary search trees is to replace all null references with a reference to a sentinel node. The sentinel node is created when the BST is first instantiated and exists as long as the BST exists.
The slight advantage of a sentinel node occurs in searching. The null check for the case of when the element being hunted is not present in the tree can be eliminated. The search starts by setting the data contents of the sentinel node to the element to be found. This ensures that the element will always be found. If the recursive search terminates by locating the element in the sentinel then the driver returns a failure for the search.
- Code a recursive method to
transpose a null terminated BST into a sentinel
terminated BST.
- Modify your BST find method to implement the search on a sentinel terminated BST.
2. Full Nodes
Write a method that returns the number of full nodes in the BST.
3. Tree Pruning
Write an implementation of an algorithm to remove all the nodes in a BST that are within a specified range, inclusively. Be careful to consider all special pruning cases.
// Pre: lower and upper are valid objects of
type T, such that}
// lower <= upper, according to
type T's compareTo().
// Post: The resulting BST
contains no element, e, such that
// lower <= e <=
upper.
//
public void rangePrune(T lower, T upper)
{
rangePruneHelper(lower, upper, root);
4. Level Elements
Write an implementation of an algorithm to return all the elements at a specified level in a BST.
// Pre: L >= 0.}
// Returns: Vector object
containing all the elements X found in the
// BST at
level L.
// The order in which the elements occur is
not guaranteed
//
public Vector<T>
elementsAtLevel(int L) {
Vector<T>
elemsL = new Vector<T>();
elementsAtLevelHelper(root, elemsL,
L);
return
elemsL;
| For manually graded assignments, only the student's last Curator submission will be evaluated. There are no exceptions to this policy! |
The CS 3114 programming projects are individual work. Each submission must be pledged by including the commented posted pledge in the submitted file. The Va Tech Honor Code is in effect for all submitted work in CS
3114.
"On my honor, I have neither given nor received unauthorized aid on this assignment." |
