Need to fill the insert, delete and retrieve using java generics pls /* * CSC 11
ID: 3913726 • Letter: N
Question
Need to fill the insert, delete and retrieve using java generics pls
/*
* CSC 115 Assignment 4: Fun with BinaryTree's
* BinaryTreeIterator.java
*/
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> extends BinaryTree {
// the root is inherited from BinaryTree.
/**
* Create an empty BinarySearchTree.
*/
public BinarySearchTree() {
super(null);
}
/**
* 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 left) {
throw new UnsupportedOperationException("Unsuported Operation");
}
public void attachRightSubtree(BinaryTree right) {
throw new UnsupportedOperationException("Unsuported Operation");
}
public void insert(TreeNode item, TreeNode root) {
if (root==null){
root = item;
}
if (item){
}
}
public E retrieve(E item) {
return null;
}
public E delete(E item) {
return null;
}
/**
* Internal test harness.
* @param args Not used.
*/
public static void main(String[] args) {
// NOTE TO STUDENT: something to get you started.
BinarySearchTree tree = new 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 it = tree.inorderIterator();
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 = new DrawableBTree(tree);
dbt.showFrame();
}
}
Additional classes to work with : (they are completed)
/**
* 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 the node that registers an item's location in a tree.
*/
class TreeNode<E> {
E item;
TreeNode<E> parent;
TreeNode<E> left;
TreeNode<E> right;
/**
* 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<E> parent, TreeNode<E> left, TreeNode<E> right) {
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<E> left, TreeNode<E> right) {
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);
}
}
The student: /*
* CSC 115 Assignment 4: Fun with BinaryTree's
* BinaryTree.java
*/
import java.util.Iterator;
/**
* 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 <i>Java, Walls & Mirrors,</i> by Prichard and Carrano.
*/
public class BinaryTree <E> {
/* The root is inherited by any subclass
* so it must be protected instead of private.
*/
protected TreeNode<E> root;
/**
* Create an empty BinaryTree.
*/
public BinaryTree (E item, E root) {
item = null; // make it empty
this.root = null; // if root is null so is the rest of the tree
}
/**
* Create a BinaryTree with a single item.
* @param item The only item in the tree.
*/
public BinaryTree(E item) {
root = new TreeNode<E>(item);
}
/**
* Used only by subclasses and classes in the same package (directory).
* @return The root node of the tree.
*/
protected TreeNode<E> getRoot() {
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 <i>this</i> 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.
* @return
*/
public BinaryTree (E item, BinaryTree <E> leftTree, BinaryTree <E> rightTree) {
root = new TreeNode<E>(item);
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 <i>this</i> tree.
* @throws TreeException if <i>this</i> tree is empty.
*/
public void attachLeftSubtree(BinaryTree <E> left) {
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<E> preorderIterator() {
return new BinaryTreeIterator<E>("preorder",root);
}
/**
* @return an inorder iterator of the binary tree.
*/
public Iterator<E> inorderIterator() {
return new BinaryTreeIterator<E>("inorder", root);
}
/**
* @return a postorder iterator of the binary tree.
*/
public Iterator<E> postorderIterator() {
return new BinaryTreeIterator<E>("postorder",root);
}
/* NOTE TO STUDENT:
* Comment and complete the following methods.
*/
public boolean isEmpty() { // if the root is null, then the tree is null.
if (this.root == null){
return true;
}
return false;
}
public void attachRightSubtree(BinaryTree <E> right) {
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() {
int h,l,r = 0;
l = height(root.left);
r = height(root.right);
if (l >= r) {
h = l;
} else {
h = r ;
}
return h;
}
/*
* 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<E> node) {
if(node.left != null){
return 1 + height(node.left);
}
else if(node.right != null){
return 1 + height(node.right);
}
return 0; // else the height will just be zero
}
/* 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.
*/
}
The student: /*
* CSC 115 Assignment 4: Fun with BinaryTree's
* BinaryTreeIterator.java
*/
import java.util.LinkedList;
import java.util.Iterator;
/**
* BinaryTreeIterator is an iterator specific to a BinaryTree.
* One of three orders are available:
* <ol>
* <li>preorder</li>
* <li>inorder</li>
* <li>postorder</li>
* </ol>
*/
public class BinaryTreeIterator<E> implements Iterator<E> {
private TreeNode<E> root;
private E curr;
private LinkedList<E> list;
/**
* 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<E> root) {
this.root = root;
curr = null;
list = new LinkedList<E>();
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<E> node) {
if (node != null) {
list.add(node.item);
preorder(node.left);
preorder(node.right);
}
}
private void inorder(TreeNode<E> node) { // in order traversal such that you view the left tree, root, right tree.
if (node != null){
inorder(node.left);
list.add(node.item);
inorder(node.right);
}
}
private void postorder(TreeNode<E> node) { // post order such that we view the left tree, right tree and then the root.
if (node != null){
postorder(node.left);
postorder(node.right);
list.add(node.item);
}
}
}
Explanation / Answer
insert, delete and retrieve using java generics:
Solution:
//Main Method and Class
import java.util.*;
class BinaryTree
{
public static void main (String[] args)
{
BinarySearchTree ds = new BinarySearchTree();
ds.add(10);
ds.add(20);
ds.add(30);
ds.add(40);
System.out.println(ds.search(30));
ds.remove(20);
ds.add(50);
System.out.println(ds.search(50));
System.out.println(ds.getRandom());
}
}
//Second Class
class BinarySearchTree
{
ArrayList<Integer> arr; // A resizable array
// A hash where keys are array elements and vlaues are
// indexes in arr[]
HashMap<Integer, Integer> hash;
// Constructor (creates arr[] and hash)
public BinarySearchTree()
{
arr = new ArrayList<Integer>();
hash = new HashMap<Integer, Integer>();
}
// A Theta(1) function to add an element to BinarySearchTree
// data structure
void add(int x)
{
// If ekement is already present, then noting to do
if (hash.get(x) != null)
return;
// Else put element at the end of arr[]
int s = arr.size();
arr.add(x);
// And put in hash also
hash.put(x, s);
}
// A Theta(1) function to remove an element from BinarySearchTree
// data structure
void remove(int x)
{
// Check if element is present
Integer index = hash.get(x);
if (index == null)
return;
// If present, then remove element from hash
hash.remove(x);
// Swap element with last element so that remove from
// arr[] can be done in O(1) time
int size = arr.size();
Integer last = arr.get(size-1);
Collections.swap(arr, index, size-1);
// Remove last element (This is O(1))
arr.remove(size-1);
// Update hash table for new index of last element
hash.put(last, index);
}
// Returns a random element from BinarySearchTree
int getRandom()
{
// Find a random index from 0 to size - 1
Random rand = new Random(); // Choose a different seed
int index = rand.nextInt(arr.size());
// Return element at randomly picked index
return arr.get(index);
}
// Returns index of element if element is present, otherwise null
Integer search(int x)
{
return hash.get(x);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.