Question: Partner Lab 2: The BSDT (Binary Search Dog Tree) ---------------- Important: Although this is a Partner assignment, each student must submit their own copy --
Partner Lab 2: The BSDT (Binary Search Dog Tree)
----------------
Important: Although this is a Partner assignment, each student must submit their own copy -- not doing this will result in a grade of zero. Working with a partner is optional. If you do choose to work with a partner, please specify their name when submitting your assignment.
All of your classes should be properly encapsulated, follow all proper coding conventions discussed in class, and be logically constructed following good Object Oriented design. Your submitted code should compile and run without errors.
-----------------
Description: The Binary Search Tree (BST) is a powerful new tool in our toolbox!. It allows us to access, insert, and delete elements in O(log N)! However, we need a special variant that will allow us to work with our canine friends.
Assignment Steps:
- Create a "Dog" class with the following attributes:
- Name
- Weight
Include a constructor and getter methods, and override toString() to display all info (you may let NetBeans do this for you).
- Create a BinarySearchDogTree class that maintains all of the Binary Search Tree properties as described in class, and implements the following methods:
- boolean addDog(String name, double weight): Adds a Dog object to the tree. Returns true on success or false on failure (if Dog with that name already exists).
- boolean removeDog(String name): If the dog with that name exists, remove it and return true. Otherwise return false.
- boolean containsDog(String name): Returns true if a dog with the specified name exists in the tree, or false otherwise.
- double getDogWeight(String name): Returns the weight of the dog with the specified name if it exists in the tree, or returns -1 otherwise.
- void displayInOrder(): Displays the elements of the tree in order using an in-order traversal.
- void switchSortCriteria(String criteria): Specifies whether your tree is sorted by the dog's name or weight. If the tree contains elements already, it will re-order those elements using the criteria specified. The criteria parameter may be equal to name or weight.
- In your main method, perform the following tasks:
- Create an instance of your tree.
- Specify the sort criteria to name using your switchSortCriteria() method.
- Create 5 instances of your Dog class and add them to your list.
- Display your list
- Switch the sort criteria to weight using your switchSortCriteria() method.
- Display your re-sorted list
Note: You may assume that no dog weights will be duplicated. Maintaining a sorted BST with duplicate values is possible, but adds complexity beyond the scope of this assignment.
This code that follows has to be implemented in my code:
public class BSTree {
class Node
{
int data;
Node leftChild;
Node rightChild;
Node(int data)
{
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}
private Node root;
public BSTree()
{
root = null;
}
public void add(int data)
{
root = addRecursive(root, data);
}
private Node addRecursive(Node current, int data)
{
if (current == null) //valid leaf node to add our new node to
{
return new Node(data);
}
else if (data < current.data)
{
current.leftChild = addRecursive(current.leftChild, data);
return current;
}
else if (data > current.data)
{
current.rightChild = addRecursive(current.rightChild, data);
return current;
}
else //it already exists
{
return current;
}
}
public boolean containsValue(int data)
{
return containsRecursive(root, data);
}
private boolean containsRecursive(Node current, int data)
{
if (current == null)
{
return false;
}
else if (data == current.data)
{
return true;
}
else if (data < current.data)
{
return containsRecursive(current.leftChild, data);
}
else
{
return containsRecursive(current.leftChild, data);
}
}
public void displayInOrder()
{
inOrderTraversal(root);
}
private void inOrderTraversal(Node node)
{
if (node != null)
{
inOrderTraversal(node.leftChild);
System.out.println(" " + node.data);
inOrderTraversal(node.rightChild);
}
}
private int getSmallest(Node root)
{
if (root.leftChild == null)
{
return root.data;
}
else
{
return getSmallest(root.leftChild);
}
}
public void delete(int data)
{
deleteRecursive(root, data);
}
private Node deleteRecursive(Node current, int data)
{
if (current == null)
return null;
else if (data == current.data) //found node to delete
{
//CASE 1: Node has Children
if (current.leftChild == null && current.rightChild == null)
{
return null;
}
//CASE 2: Node has 1 child
else if (current.rightChild == null)
{
return current.leftChild;
}
else if (current.leftChild == null)
{
return current.rightChild;
}
//CASE 3: Node has 2 children (...the tricky case...)
else
{
//Step 1) find smallest value S in right subtree of Node
int smallestVal = getSmallest(current.rightChild);
//Step 2) Replace Node's value with S's value
current.data = smallestVal;
//Step 3) Delete S from right subtree
current.rightChild = deleteRecursive(current.rightChild,
smallestVal);
return current;
}
}
else if (data < current.data)
{
current.leftChild = deleteRecursive(current.leftChild, data);
return current;
}
else
{
current.rightChild = deleteRecursive(current.rightChild,
data);
return current;
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help