For this project you will develop methods to manipulate a Binary Search Tree. Bi
ID: 3836243 • Letter: F
Question
For this project you will develop methods to manipulate a Binary Search Tree. Binary Search Trees are a fundamental data structure in computing, and are the underlying structure of the TreeSet and TreeMap classes in the Java Collection Frameworks. As before, we will be using the software of the BRIDGES project, which allows us to visualize the shape of the Binary Search Tree, and to see how it is altered by your methods.
The given source code includes a class called BinarySearchTree_Bridges. This class implements a Binary Tree, using the BSTElement class from Bridges to represent the nodes in the tree. Similar to the TreeMap in the Java Collection Framework, each element in the tree will store both a key and the value associated with that key. The given Driver source code uses Student objects as the test data, where the key associated with each Student is the name field. But any Object that is Comparable could also be stored in this Binary Search Tree.
The given BinarySearchTree_Bridges class has a method to search (i.e., “get”) the tree for a given target key.
For this assignment you must complete the methods in the BinarySearchTree_Bridges class to perform the following operations.
1. public void resetColor ( Color c )
This method traverses the entire tree and sets the color of each node to the specified color c.
2. public E last ( Color c )
This method locates and returns the maximum value in the tree, and also changes the color of every node along the path from the root to the maximum value to be the specified color c.
3. public E first ( Color c )
This method locates and returns the minimum value in the tree, and also changes the color of every node along the path from the root to the minimum value to be the specified color c.
4. public int countAndColorMajors (Color c , String theMajor)
This method traverses the entire tree. Each node is examined, and if the value stored at that node is a Student object, and if the major field of that Student object equals the parameter theMajor, then that node is set to the specified color c. The total number of nodes that are colored by this method is returned. Note that this is the only method in this assignment that assumes that the data stored in the tree are Student objects. Your code can always check whether a value stored in the tree is a Students object using the instanceof operator in Java.
For example: if ( foo instanceof Student ) { .... }
5. public void colorRange ( Color c, K minVal, K maxVal )
This method resets the color of every item in the tree whose key is greater-thanor-equal-to minVal, and less-than maxVal, to be the specified color c.
6. public void deleteSmall ( K key )
This method removes from the tree every item whose key is less-than-or-equal-to the given parameter key. To remove these keys you should directly alter the pointers in the tree using setLeft and setRight methods to “splice out” the small values.
7. public void deleteLarge ( K key )
This method removes from the tree every item whose key is greater-than the give parameter key.
8. public E colorLower ( K key, Color c )
This method locates and returns the largest value in the tree that is strictly less than the given parameter key. If no such item exists, then the value null is returned. If the item exists, then the method changes the color of that node to be the specified color c.
9.public E colorHigher ( K key, Color c )
This method locates and returns the smallest value in the tree that is strictly greater than the given parameter key. If no such item exists, then the value null is returned. If the item exists, then the method changes the color of that node to be the specified color c.
As always, you should implement all these methods in the most efficient manner possible. Your code should not traverse more nodes in the tree than is necessary.
The given Driver code will test your methods and display the tree that is produced by your code. You should create additional test cases to insure that your code is correct, instead of relying only on the given test cases.
Deliverables:Hand in a paper copy of your BinarySearchTree_Bridges.java file. Be sure that your code is readable (the code must not spill over the line onto the next line). Your code must use good programming style (proper indentation, good use of comments, well chosen, meaningful variable names, etc.)
package csc205_project02.binarySearchTrees;
import bridges.base.BSTElement;
import bridges.base.Color;
public class BinarySearchTree_Bridges< K extends Comparable , E > {
/** The root of the binary tree */
public BSTElement<K,E> root;
/** Constructs an empty tree, with no nodes at all. Size = 0 */
public BinarySearchTree_Bridges() {
root = null;
}
/** Constructs a new binary tree with data in its root, leftTree
* as its left subtree and rightTree as its right subtree. */
public BinarySearchTree_Bridges(K key, E data, BinarySearchTree_Bridges<K,E> leftTree, BinarySearchTree_Bridges<K,E> rightTree) {
root = new BSTElement< K, E > (key, data);
root.setLabel( data.toString() );
if (leftTree != null)
root.setLeft( leftTree.root );
else
root.setLeft(null);
if (rightTree != null)
root.setRight( rightTree.root );
else
root.setRight(null);
}
/** Search for the element whose key is target, and return the value associated with
* that key, or null, if the target is not present in the tree
* Color every node on the search path to the target with the given color.
*/
public E get ( Color theColor, K target )
{
BSTElement<K, E> curr = root; // pointer to the current node being examined
if ( root == null ) // consider the case of the empty tree
return null;
boolean found = false;
while ( curr != null && ! found ) {
curr.getVisualizer().setColor( theColor ); // color each node on the search path
if ( curr.getKey().equals( target )) {
found = true;
return ( curr.getValue() );
} else if ( curr.getKey().compareTo( target ) < 0 ) {
curr = curr.getRight(); // move down to the right child
} else {
curr = curr.getLeft(); // move down to the left child
}
}
return null; // the target key was not found
}
/** reset the color of every node in the tree to be the specified color */
public void resetColors ( Color theColor )
{
}
/** Color every node on the path from the root node to the minimum value in the
* tree with the given color
* @return the element with the smallest key, or null, if there is no such element
*/
public E first ( Color theColor )
{
return null;
}
/** Color every node on the path from the root node to the maximum value in the
* tree with the given color
* @return the element with the largest key, or null, if there is no such element
*/
public E last ( Color theColor )
{
return null;
}
/** return the number of Students with the given major, and color all those
* Students with the specified color.
*/
public int countAndColorMajors ( Color theColor, String theMajor )
{
return -1;
}
/** set the color of every node that is greater-than-or-equal-to minValue
* but less-than maxValue to be the given color
*/
public void colorRange ( Color theColor, K minValue, K maxValue )
{
}
/** Remove from the tree every node that is less-than-or-equal-to than the given key */
public void deleteSmall ( K key )
{
}
/** Remove every node from the tree that is greater-than the given key */
public void deleteLarge( K key )
{
}
/** locate and return the greatest element in this set that is strictly less than
* the given key, and color it with the given color, if it exists
*
* @return the greatest element in this set strictly less than
* the given key, or null if there is no such element.
*/
public E colorLower ( K key, Color theColor )
{
return null;
}
/** locate and return the smallest element in this set that is strictly greater-than
* the given key, and color it with the given color, if it exists
*
* @return the smallest element in this set strictly greater than
* the given key, or null if there is no such element.
*/
public E colorHigher ( K key, Color theColor )
{
return null;
}
/** represent the tree as a one-dimensional sequence of its elements, using a preorder traversal */
public String toString() {
StringBuilder sb = new StringBuilder();
preOrderTraverse(root, sb);
return sb.toString();
}
/** represent the tree as a one-dimensional sequence of its elements, using an inorder traversal */
public String outputTreeUsingInorder() {
StringBuilder sb = new StringBuilder();
inOrderTraverse( root, sb );
return sb.toString();
}
private void preOrderTraverse(BSTElement< K, E > currPos, StringBuilder sb) {
if (currPos == null) { // BASE CASE
;
}
else { // GENERAL CASE
sb.append( currPos.getValue().toString() + " " );
preOrderTraverse(currPos.getLeft(), sb);
preOrderTraverse(currPos.getRight(), sb);
}
}
private void inOrderTraverse(BSTElement< K, E > currPos, StringBuilder sb) {
if (currPos == null) {
;
}
else {
inOrderTraverse(currPos.getLeft(), sb);
sb.append(currPos.getValue().toString() + " ");
inOrderTraverse(currPos.getRight(), sb);
}
}
}
Explanation / Answer
import bridges.base.BSTElement;
import bridges.base.Color;
public class BinarySearchTree_Bridges< K extends Comparable , E > {
public BSTElement<K,E> root;
public BinarySearchTree_Bridges() {
root = null;
}
public BinarySearchTree_Bridges(K key, E data, BinarySearchTree_Bridges<K,E> leftTree, BinarySearchTree_Bridges<K,E> rightTree) {
root = new BSTElement< K, E > (key, data);
root.setLabel( data.toString() );
if (leftTree != null)
root.setLeft( leftTree.root );
else
root.setLeft(null);
if (rightTree != null)
root.setRight( rightTree.root );
else
root.setRight(null);
}
public E get ( Color theColor, K target )
{
BSTElement<K, E> curr = root;
if ( root == null )
return null;
boolean found = false;
while ( curr != null && ! found ) {
curr.getVisualizer().setColor( theColor );
if ( curr.getKey().equals( target )) {
found = true;
return ( curr.getValue() );
} else if ( curr.getKey().compareTo( target ) < 0 ) {
curr = curr.getRight();
} else {
curr = curr.getLeft();
}
}
return null;
}
public void resetColors ( Color theColor )
{
}
public E first ( Color theColor )
{
return null;
}
public E last ( Color theColor )
{
return null;
}
public int countAndColorMajors ( Color theColor, String theMajor )
{
return -1;
}
public void colorRange ( Color theColor, K minValue, K maxValue )
{
}
public void deleteSmall ( K key )
{
}
public void deleteLarge( K key )
{
}
public E colorLower ( K key, Color theColor )
{
return null;
}
public E colorHigher ( K key, Color theColor )
{
return null;
}
public String toString() {
StringBuilder sb = new StringBuilder();
preOrderTraverse(root, sb);
return sb.toString();
}
public String outputTreeUsingInorder() {
StringBuilder sb = new StringBuilder();
inOrderTraverse( root, sb );
return sb.toString();
}
private void preOrderTraverse(BSTElement< K, E > currPos, StringBuilder sb) {
if (currPos == null) { // BASE CASE
;
}
else { // GENERAL CASE
sb.append( currPos.getValue().toString() + " " );
preOrderTraverse(currPos.getLeft(), sb);
preOrderTraverse(currPos.getRight(), sb);
}
}
private void inOrderTraverse(BSTElement< K, E > currPos, StringBuilder sb) {
if (currPos == null) {
;
}
else {
inOrderTraverse(currPos.getLeft(), sb);
sb.append(currPos.getValue().toString() + " ");
inOrderTraverse(currPos.getRight(), sb);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.