Question
I have to implement a generic BST. The classes are mostly written, I just have to do the methods that are incomplete so that the
I have to implement a generic BST. The classes are mostly written, I just have to do the methods that are incomplete so that the Generic BST is functioning. I have also attached the exception and node classes.
----------------------------------BINARY SEARCH TREE CLASS----------------------------
NOTE: I have completed the insert and delete methods myself, but I'm not sure how to do the "retrieve method".
>>"retrieve method" description: <<
Looks for the item in the tree that is equivalent to the item.
Parameters:
item - The item that is equivalent to the item we are looking for. Equality is determined by the equals method of the item.
Returns:
The item if it's in the tree, null if it is not.
import java.util.Iterator;
/*
*/
/**
* BinarySearchTree is an ordered binary tree, where the element in each node
* comes after all the elements in the left subtree rooted at that node
* and before all the elements in the right subtree rooted at that node.
* For this assignment, we can assume that there are no elements that are
* identical in this tree.
* A small modification will allow duplicates.
*/
public class BinarySearchTree
private TreeNode
// the root is inherited from BinaryTree.
/**
* Create an empty BinarySearchTree.
*/
public BinarySearchTree() {
super();
}
/**
* Creates a BinarySearchTree with a single item.
* @param item The single item in the tree.
*/
public BinarySearchTree(E item) {
super(item);
}
/**
* This method is not allowed in a BinarySearchTree.
* It's description from the subclass:
*
* {@inheritDoc}
* @throws UnsupportedOperationException if this method is invoked.
*/
public void attachLeftSubtree(BinaryTree
throw new UnsupportedOperationException();
}
/**
* This method is not allowed in a BinarySearchTree.
* It's description from the subclass:
*
* {@inheritDoc}
* @throws UnsupportedOperationException if this method is invoked.
*/
public void attachRightSubtree(BinaryTree
throw new UnsupportedOperationException();
}
/**
Looks for the item in the tree that is equivalent to the item.
@returns item if it's present in the tree, null if it is not.
*/
public E retrieve(E item) {
return null;
}
/**
Inserts new item in the tree while maintaing its order. if item
already exists then nothing happens
*/
public void insert(E item) {
root=insert(root,item);
}
/**
direct access to the tree is not public and operated through this method
*/
private TreeNode
if(node ==null){
return new TreeNode
}
if(itemIn.compareTo(node.item)<0){
node.left=insert(node.left,itemIn);
return node;
}
node.right=insert(node.right,itemIn);
return node;
}
/**
Finds the item that is equivalent to the item and removes it,
if it's in the tree.
@returns The actual item that was removed,
or null if it is not in the tree.
*/
public void delete(E item) {
root=delete(root,item);
}
/**
direct access to the tree is not public and operated through this method
*/
private TreeNode
if(root==null){
return null;
}
else if(item.compareTo(root.item)<0)
{
root.left=delete(root.left,item);
}
else if(item.compareTo(root.item)>0)
{
root.right=delete(root.right,item);
}
else
{
if(root.left==null&&root.right==null){
return null;
}
else if(root.right==null){
return root.left;
}
else if (root.left==null){
return root.right;
}
else{
root.item=findMax(root.left);
root.left=delete(root.left,root.item);
}
}
return root;
}
/**
Returns true if the value is contained in the binary search tree and false otherwise
@param data the value that's being searched for
@return boolean evaluation
*/
public boolean contains(E item){
return contains(root,item);
}
/**
direct access to the tree is not public and operated through this method
*/
private boolean cotains(TreeNode
if(root==null){
return false;
}
else if(item.compareTo(root.item)<0){
return contains(root.left,item);
}
else if(item.compareTo(root.item>0)){
return contains(root.right,item);
}
else{
return true;
}
}
/**
This method assumes root is non-null, since this is only called by
delete() on the left subtree, and only when that subtree is non-empty.
*/
private E findMax(TreeNode
while(root.right!=null){
root=root.right;
}
return root.item;
}
/**
* Internal test harness.
* @param args Not used.
*/
public static void main(String[] args) {
// NOTE TO STUDENT: something to get you started.
BinarySearchTree
String s1 = new String("optimal");
String s2 = new String("needs");
String s3 = new String("programmers");
String s4 = new String("CSC115");
tree.insert(s1);
tree.insert(s2);
tree.insert(s3);
tree.insert(s4);
String test = tree.retrieve("needs");
if (test != null && !test.equals("")) {
System.out.println("retrieving the node that contains "+s2);
if (test.equals(s2)) {
System.out.println("Confirmed");
} else {
System.out.println("retrieve returns the wrong item");
}
} else {
System.out.println("retrieve returns nothing when it should not");
}
Iterator
System.out.println("printing out the contents of the tree in sorted order:");
while (it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.println();
DrawableBTree
dbt.showFrame();
}
}
---------------------------------- END OF BINARY SEARCH TREE CLASS----------------------------
---------------------------------- BINARY TREE CLASS----------------------------
NOTE: I have completed the methods in this class but I am not certain if they are correct because i have not got all the classes working together yet.
import java.util.Iterator;
/*
* NOTE TO STUDENT:
* Comment and implement all incomplete methods.
* Any methods that have comments are already complete and
* you must not change them.
* You may add methods that you find helpful, remembering
* that no public method allows access to a TreeNode directly.
* Remove this comment and provide your own header.
*/
/**
* BinaryTree is a basic generic BinaryTree data structure.
* It is referenced based, using TreeNodes to connect the tree.
* It contains any element determined by the placeholder E.
* The basic ADT is adapted from Java, Walls & Mirrors, by Prichard and Carrano.
*/
public class BinaryTree
/* The root is inherited by any subclass
* so it must be protected instead of private.
*/
protected TreeNode
/**
* Create an empty BinaryTree.
*/
public BinaryTree() {
}
/**
* Create a BinaryTree with a single item.
* @param item The only item in the tree.
*/
public BinaryTree(E item) {
root = new TreeNode
}
/**
* Used only by subclasses and classes in the same package (directory).
* @return The root node of the tree.
*/
protected TreeNode
return root;
}
/**
* Creates a binary tree from a single item for the root and two subtrees.
* Once the two subtrees are attached, their references are nullified to prevent
* multiple entries into this tree.
* @param item The item to be inserted into the root of this tree.
* @param leftTree A binary tree, which may be empty.
* @param rightTree A binary tree, which may be empty.
*/
public BinaryTree(E item, BinaryTree
root = new TreeNode
attachLeftSubtree(leftTree);
attachRightSubtree(rightTree);
}
/**
* Attaches a subtree to the left of the root node, replacing any subtree that was
* previously there.
* @param left The new left subtree of the root.
* This subtree may be empty.
* Once attached, this parameter reference is nullified to prevent multiple
* access to this tree.
* @throws TreeException if this tree is empty.
*/
public void attachLeftSubtree(BinaryTree
if (root == null) {
throw new TreeException("Cannot attach to an empty tree.");
}
if (left == null) {
return;
}
root.left = left.root;
left.root.parent = root;
left = null;
}
/**
* @return a preorder iterator of the binary tree.
*/
public Iterator
return new BinaryTreeIterator
}
/**
* @return an inorder iterator of the binary tree.
*/
public Iterator
return new BinaryTreeIterator
}
/**
* @return a postorder iterator of the binary tree.
*/
public Iterator
return new BinaryTreeIterator
}
/* NOTE TO STUDENT:
* Comment and complete the following methods.
*/
public boolean isEmpty() {
return root==null;
}
public void attachRightSubtree(BinaryTree
if(root==null){
throw new TreeException("Cannot attach to an empty tree.");
}
if (right==null){
return;
}
root.right=right.root;
right.root.parent=root;
right=null;
}
public int height() {
return height(root);
}
/*
* NOTE TO STUDENT:
* The height of a tree is recursively defined as:
* 1 + the maximum (height of the left subtree rooted at node
* or height of right subtree rooted at node.
*/
private int height(TreeNode
if (node==null) return 0;
int lh=height(node.left);
int rh=height(node.right);
if(lh>rh) return lh+1;
return rh+1;
}
/* NOTE TO STUDENT:
* You do not need to implement a main method for this class
* To test your BinaryTree, compile and run the Expression class.
*/
}
---------------------------------- END OF BINARY TREE CLASS----------------------------
---------------------------------- BINARY TREE ITERATOR CLASS----------------------------
NOTE: I am supposed to write traversal methods for inorder and postorder traversals.
import java.util.LinkedList;
import java.util.Iterator;
/*
* NOTE TO STUDENT:
* Comment and implement the two incomplete methods.
* Any method that have comments are already complete and
* you must not change them.
* You may add methods that you find helpful, remembering
* that no public method allows acces to a TreeNode directly.
* Remove this comment and provide your own header.
*/
/**
* BinaryTreeIterator is an iterator specific to a BinaryTree.
* One of three orders are available:
*
- preorder
- inorder
- postorder
*
*
*
*
*/
public class BinaryTreeIterator
private TreeNode
private E curr;
private LinkedList
/**
* Non-public constructor : only a BinaryTree is allowed access.
* Creates a a Binary tree iterator.
* @param order One of the three orders: inorder, preorder, or postorder.
* @param root The root of the BinaryTree.
* @throws TreeException if any of the actual parameters are not valid.
*/
BinaryTreeIterator(String order, TreeNode
this.root = root;
curr = null;
list = new LinkedList
switch(order) {
case "preorder":
preorder(root);
break;
case "inorder":
inorder(root);
break;
case "postorder":
postorder(root);
break;
default:
throw new TreeException("unable to assess the interator order:"+
" choose {inorder, inorder, postorder");
}
}
/* Required methods from Iterator. Comments inherited from that class.*/
// One of the Iterator required methods.
public boolean hasNext() {
return list.size() != 0;
}
// One of the Iterator required methods.
public E next() {
return list.remove();
}
/**
* Even though this method is required by the Iterator,
* it should never be allowed.
* No one should remove an item during a traversal.
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Recursive helper method.
* Fills the list with tree items in 'pre' order.
* @param node The root node of a subtree.
*/
private void preorder(TreeNode
if (node != null) {
list.add(node.item);
preorder(node.left);
preorder(node.right);
}
}
private void inorder(TreeNode
}
private void postorder(TreeNode
}
}
---------------------------------- END OF BINARY TREE ITERATOR CLASS----------------------------
---------------------------------- TREE NODE CLASS----------------------------
/**
* CSC115 Assignment 5 : BinarySearchTree
* TreeNode.java
* Created for use by CSC115 Summer 2016
*/
/**
* TreeNode is a protected class, used exclusively by a BinaryTree object.
* It is th node that registers an item's location in a tree.
*/
class TreeNode
E item;
TreeNode
TreeNode
TreeNode
/**
* Creates a tree node.
* @param item The element contained within the tree.
* @param parent The reference to the node that is the parent of this node.
* Note that the root node of a tree has a null parent reference.
* @param left The reference to the node that is the left child of this node.
* Note that if there is no left child, this reference is null.
* @param right The reference to the node that is the right child of this node.
* Note that if there is no right child, this reference is null.
*/
TreeNode(E item, TreeNode
this.item = item;
this.parent = parent;
this.left = left;
this.right = right;
}
/**
* Creates a tree node with a null or absent parent reference.
* @param item The element contained within the tree.
* @param left The reference to the node that is the left child of this node.
* Note that if there is no left child, this reference is null.
* @param right The reference to the node tha tis the right child of this node.
* Note that if there is no right child, this reference is null.
*/
TreeNode(E item, TreeNode
this(item,null,left,right);
}
/**
* Creates a tree node with no parent and no left or right children.
* @param item The element contined within the tree.
*/
TreeNode(E item) {
this(item,null,null);
}
}
----------------------------------END OF TREE NODE CLASS----------------------------
----------------------------------TREE NODE EXCEPTION CLASS----------------------------
/**
* TreeException.java
* Created for use by CSC115 Summer 2016
*/
/**
* An exception thrown when illegal operations or requests
* are made in a Binary Tree ADT.
*/
public class TreeException extends RuntimeException {
/**
* Creates an exception.
* @param msg The message to the calling program.
*/
public TreeException(String msg) {
super(msg);
}
/**
* Creates an exception without a message.
*/
public TreeException() {
super();
}
}
----------------------------------END OF TREE NODE EXCEPTION CLASS----------------------------
----------------------------------INVALID EXPRESION EXCEPTION CLASS----------------------------
/**
* An exception thrown when an Arithmetic expression is determined to be invalid.
*/
public class InvalidExpressionException extends RuntimeException {
/**
* Creates an exception.
* @param msg The message to the calling program.
*/
public InvalidExpressionException(String msg) {
super(msg);
}
/**
* Creates an exception without a message.
*/
public InvalidExpressionException() {
super();
}
}
---------------------------------- END OF INVALID EXPRESION EXCEPTION CLASS----------------------------
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Advances In Spatial Databases 2nd Symposium Ssd 91 Zurich Switzerland August 1991 Proceedings Lncs 525
Authors: Oliver Gunther ,Hans-Jorg Schek
1st Edition
3540544143, 978-3540544142
