Description
The motivation behind this problem is to practice implementing binary trees and understand how stacks are used by compilers to implement recursion. You will be writing a sorting algorithm. You will first insert all the integer keys to be sorted into an initially empty binary search tree T, and then traverse T to
retrieve the keys in sorted order. But instead of implementing the traversal recursively, you will use a
stack.
a. You can use your stack implementation from the previous assignment but you may need to update the type stored. You are also allowed to use Java’s Stack.
b. Implement a binary search tree class. Each node in your implementation should have fields for a key and left and right subtrees but should not have a parent reference. The methods in the BST
include
i. Return the key at the root
ii. Return the left subtree of the root
iii. Return the right subtree of the root
iv. Test if the tree is empty
v. Construct an empty tree
vi. Test if the tree contains a given value
vii. Insert a new Integer into the BST
1. In the Weiss book there is an example insertion method. Your method will be similar but you must support duplicate values.
Your method will be similar but you must support duplicate values.
/*
Internal method to insert into a subtree.
@param x the item to insert.
@program t the node that roots the subtree.
@return the new root of the subtree.
*/
Private BinaryNode<AnyType> insert(AntType x, BinaryNode<>AnyType)
{
If ( t== null)
Return new BinaryNode<> ( x, null, null);
int compareResult = x.compareTo ( t.element );
if ( CompareResult < 0 )
t.left = insert ( x, t.left );
else if ( compareREsult > 0 )
t.right = inser ( x, t.right );
else
; // Duplicate, do nothing
return t;
}
c. What type of tree traversal do you need to implement to retrieve the keys from your binary search tree in sorted order? Implement it without recursion, instead
using your stack to simulate the recursion.
i. Hints: What type of object needs to be stored on the stack? Exactly which object needs to be pushed when you are about to start the traversal of the left subtree? When do you pop the stack and what do you do with the result that is popped? What do you do when the stack is empty?
d. Implement a class called SortIntegers. Include a method called “sortIntegerArray” which will take as an argument an array of Integers, it will then insert them into the binary search tree class you implemented above, then use the tree traversal method you implemented in part c to sort the integers.
Return an array of the Integers sorted.
e. You are not required to turn in any testing methods.
