SOLVE IN JAVA!!!

BST.java

import java.util.ArrayList;

/** BST implementation for Dictionary ADT */ class BST, E> implements Dictionary { private BSTNode root; // Root of BST private int nodecount; // Size of BST

/** Constructor */ BST() { root = null; nodecount = 0; }

/** Reinitialize tree */ public void clear() { root = null; nodecount = 0; }

/** * Insert a record into the tree. * * @param k * Key value of the record. * @param e * The record to insert. */ public void insert(K k, E e) { root = inserthelp(root, k, e); nodecount++; }

/** * Remove a record from the tree. * * @param k * Key value of record to remove. * @return Record removed, or null if there is none. */ public E remove(K k) { E temp = findhelp(root, k); // find it if (temp != null) { root = removehelp(root, k); // remove it // System.out.println("called removehelp"); nodecount--; } return temp; }

/** * Remove/return root node from dictionary. * * @return The record removed, null if empty. */ public E removeAny() { if (root == null) return null; E temp = root.element(); root = removehelp(root, root.key()); --nodecount; return temp; }

/** * @return Record with key k, null if none. * @param k * The key value to find. */ public E find(K k) { return findhelp(root, k); }

/** @return Number of records in dictionary. */ public int size() { return nodecount; }

private E findhelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) return findhelp(rt.left(), k); else if (rt.key().compareTo(k) == 0) return rt.element(); else return findhelp(rt.right(), k); }

private BSTNode inserthelp(BSTNode rt, K k, E e) { if (rt == null) return new BSTNode(k, e); if (rt.key().compareTo(k) > 0) rt.setLeft(inserthelp(rt.left(), k, e)); else rt.setRight(inserthelp(rt.right(), k, e)); return rt; }

private BSTNode getmin(BSTNode rt) { if (rt.left() == null) return rt; else return getmin(rt.left()); }

private BSTNode deletemin(BSTNode rt) { if (rt.left() == null) return rt.right();

else { rt.setLeft(deletemin(rt.left())); return rt; } }

/** * Remove a node with key value k * * @return The tree with the node removed */ private BSTNode removehelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) rt.setLeft(removehelp(rt.left(), k)); else if (rt.key().compareTo(k) temp = getmin(rt.right()); rt.setElement(temp.element()); rt.setKey(temp.key()); rt.setRight(deletemin(rt.right())); } } return rt; }

/** * Creates a list storing the the nodes in the subtree of a node, ordered * according to the inorder traversal of the subtree. */

protected void inorderElements(BSTNode v, ArrayList elts) { // elts.add(v.element()); if (v.left() != null) inorderElements(v.left(), elts); // recurse on left child elts.add(v.element()); if (v.right() != null) inorderElements(v.right(), elts); // recurse on right child }

/** Returns an iterable collection of the tree nodes. */ public Iterable values() { ArrayList elements = new ArrayList(); if (size() != 0) inorderElements(root, elements); // assign positions in order return elements; }

public Iterable findAll(K k) { ArrayList al = new ArrayList(); findAllhelp(root, k, al); return al; }

protected void findAllhelp(BSTNode rt, K k, ArrayList a) { if (rt == null) return; if (rt.key().compareTo(k) > 0) findAllhelp(rt.left(), k, a); else if (rt.key().compareTo(k) == 0) { a.add(rt.element()); findAllhelp(rt.right(), k, a); } else findAllhelp(rt.right(), k, a); }

/* the following are for solving the exercises in Shaffer, ch. 5 */

public Iterable range(K a, K b) { ArrayList elements = new ArrayList(); rangehelp(root, elements, a, b); return elements; }

protected void rangehelp(BSTNode v, ArrayList elts, K a, K b) { // insert implementation } }

Add a method levelorderElements() to the BST.java binary search tree dic- mentation. In level order of level 1, then all nodes of level 2, and so on. Within a level, the order is left to right; i.e., in ascending order. Model your method on inorderEle- ments). Test your method by changing the calls to inorderElements) in values() to levelorderElements). This way, values) will return the val- ues in the dictionary in level order. Hint: Preorder traversals make use of a stack through recursive calls. Consider making use of another data structure to help implement the levelorder traversal