Homework SourseObjective Binary Search Tree traversal 2 points Use traversa
Objective: Binary Search Tree traversal (2 points)
Use traversal.pptx as guidance to write a program to build a binary search tree Dictionary. Input records from inventory.txt. Both key and Element of BST <Key,E> have the same data from each input record.
public interface BinNode<E> {
/** Get and set the element value */
public E element();
public void setElement(E v);
/** @return The left child */
public BinNode<E> left();
/** @return The right child */
public BinNode<E> right();
/** @return True if a leaf node, false otherwise */
public boolean isLeaf();
}
import java.lang.Comparable;
/** Binary Search Tree implementation for Dictionary ADT */
class BST<Key extends Comparable<? super Key>, E>
implements Dictionary<Key, E> {
private BSTNode<Key,E> root; // Root of the BST
int nodecount; // Number of nodes in the 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(Key k, E e) {
root = inserthelp(root, k, e);
nodecount++;
}
// Return root
public BSTNode getRoot()
{
return root;
}
/** Remove a record from the tree.
@param k Key value of record to remove.
@return The record removed, null if there is none. */
public E remove(Key k) {
E temp = findhelp(root, k); // First find it
if (temp != null) {
root = removehelp(root, k); // Now remove it
nodecount--;
}
return temp;
}
/** Remove and return the root node from the dictionary.
@return The record removed, null if tree is 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 value k, null if none exist.
@param k The key value to find. */
public E find(Key k) { return findhelp(root, k); }
/** @return The number of records in the dictionary. */
public int size() { return nodecount; }
private E findhelp(BSTNode<Key,E> rt, Key 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);
}
/** @return The current subtree, modified to contain
the new item */
private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt,
Key k, E e) {
if (rt == null) return new BSTNode<Key,E>(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;
}
/** Remove a node with key value k
@return The tree with the node removed */
private BSTNode<Key,E> removehelp(BSTNode<Key,E> rt,Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
rt.setLeft(removehelp(rt.left(), k));
else if (rt.key().compareTo(k) < 0)
rt.setRight(removehelp(rt.right(), k));
else { // Found it
if (rt.left() == null) return rt.right();
else if (rt.right() == null) return rt.left();
else { // Two children
BSTNode<Key,E> temp = getmin(rt.right());
rt.setElement(temp.element());
rt.setKey(temp.key());
rt.setRight(deletemin(rt.right()));
}
}
return rt;
}
private BSTNode<Key,E> getmin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt;
return getmin(rt.left());
}
private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt.right();
rt.setLeft(deletemin(rt.left()));
return rt;
}
private void printhelp(BSTNode<Key,E> rt) {
if (rt == null) return;
printhelp(rt.left());
printVisit(rt.element());
printhelp(rt.right());
}
private StringBuffer out;
public String toString() {
out = new StringBuffer(400);
printhelp(root);
return out.toString();
}
private void printVisit(E it) {
out.append(it + \"\ \");
}
}
class BSTNode<Key, E> implements BinNode<E> {
private Key key; // Key for this node
private E element; // Element for this node
private BSTNode<Key,E> left; // Pointer to left child
private BSTNode<Key,E> right; // Pointer to right child
/** Constructors */
public BSTNode() {left = right = null; }
public BSTNode(Key k, E val)
{ left = right = null; key = k; element = val; }
public BSTNode(Key k, E val,
BSTNode<Key,E> l, BSTNode<Key,E> r)
{ left = l; right = r; key = k; element = val; }
/** Get and set the key value */
public Key key() { return key; }
public void setKey(Key k) { key = k; }
/** Get and set the element value */
public E element() { return element; }
public void setElement(E v) { element = v; }
/** Get and set the left child */
public BSTNode<Key,E> left() { return left; }
public void setLeft(BSTNode<Key,E> p) { left = p; }
/** Get and set the right child */
public BSTNode<Key,E> right() { return right; }
public void setRight(BSTNode<Key,E> p) { right = p; }
/** @return True if a leaf node, false otherwise */
public boolean isLeaf()
{ return (left == null) && (right == null); }
}
public interface Dictionary<Key, E> {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param k The key for the record being inserted.
@param e The record being inserted. */
public void insert(Key k, E e);
/** Remove and return a record.
@param k The key of the record to be removed.
@return A maching record. If multiple records match
\"k\", remove an arbitrary one. Return null if no record
with key \"k\" exists. */
public E remove(Key k);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public E removeAny();
/** @return A record matching \"k\" (null if none exists).
If multiple records match, return an arbitrary one.
@param k The key of the record to find */
public E find(Key k);
/** @return The number of records in the dictionary. */
public int size();
};
//
inventory.txt
traverse
CT16C1288B
DT14B1225F
MI15B1250A
MI15B1251A
HO03N1095A
HY07D1095BQ
KI04D2593C
DG12A1240AQ
HY03G2593BQ
TO30A1310A
HO03N1095AQ
HO01H1351C
HO01H1350C
FT18A1288B
LR15A1000A
BM12E1000A
VW02B3113A
NI23H1230AQ
LX03D2503A
LX03D2502A
LX03D2502A
VW22A3113B
VW22B3113A
Solution
public class BST<E, K extends Sortable> implements Dictionary<E, K> {
BSTNode<E, K> root; // the root of the BST.
// constructor
public BST() {
this(null);
}
// parametrized constructor
public BST(BSTNode<E, K> root) {
this.root = root;
}
// arranging nodes when cases like deleting node
public BSTNode<E, K> MinAttach(BSTNode<E, K> right, BSTNode<E, K> left) {
if(right.getLeft() == null) {
right.setLeft(left);
return right;
}
else {
right.setLeft(MinAttach(right.getLeft(), left));
return right;
}
}
// deleting entry ..passing key
public void delete(K key) {
this.root = deleteNodeRecursively(root, key);
}
// deleting nodes
public BSTNode<E, K> DeleteDoubNode(BSTNode<E, K> node) {
if(node.getLeft() == null) {
//at the bottom of the nodes.
return node.getRight();
}
else {
//set the left node as the right of the one we found at the bottom.
node.setLeft(DeleteDoubNode(node.getLeft()));
}
return node;
}
// recursively deleting node
public BSTNode<E, K> deleteNodeRecursively(BSTNode<E,K> node, K key) {
// check right node to delete
if(key.compareTo(node.getKey()) == 0) {
// check for leaf
if((node.getLeft() == null) && (node.getRight() == null)) {
return null;
}
//check node with right child
else if((node.getLeft() == null) && (node.getRight() != null)) {
return node.getRight();
}
//check node with left child
else if((node.getLeft() != null) && (node.getRight() == null)) {
return node.getLeft();
}
// check node with two children
else if((node.getLeft() != null) && (node.getRight() != null)) {
BSTNode<E, K> replacementNode = findMin(node.getRight());
BSTNode<E, K> backupLeft = node.getLeft();
replacementNode.setRight(DeleteDoubNode(node.getRight()));
replacementNode.setLeft(backupLeft);
return replacementNode;
}
else {
return node;
}
}
//check key is less than
else if(key.compareTo(node.getKey()) < 0) {
if(node.getLeft() != null) {
node.left = deleteNodeRecursively(node.getLeft(), key);
return node;
}
}
//check key is greater than
else {
if(node.getRight() != null) {
node.right = deleteNodeRecursively(node.getRight(), key);
return node;
}
}
return node;
}
// returns depth of tree
public int depth() {
return depthPostOrder(root, 0);
}
// find minimum value of BST
public BSTNode<E, K> findMin(BSTNode<E, K> node) {
while(node.getLeft() != null) {
node = node.getLeft();
}
return node;
}
// BST inorder
public void inorder(BSTNode<E,K> node) {
if(node != null) {
inorder(node.getLeft()); //get first left keys
System.out.println(\"key: \" + node.getKey().toString() + \" element: \" + node.getElement().toString());
inorder(node.getRight());
}
}
// inserting new element
public void insert(K key, E element) {
if(root == null) {
root = new BSTNode<E, K>(key, element, null, null);
}
else {
insertBelow(root, key, element);
}
}
// recursive preorder depth
int depthPostOrder(BSTNode<E,K> node, int current_depth) {
if(node != null) {return Math.max(depthPostOrder(node.getLeft(), current_depth+1), depthPostOrder(node.getRight(), current_depth+1));
}
else return current_depth;
}
// printing whole tree
public void printTree() {
//printing recursively
System.out.println(\"\ Outputting BSTree...\");
inorder(root);
}
// serach method
public E search(K key) {
BSTNode<E, K> nodeFound;
nodeFound = searchingNode(key);
if(nodeFound == null) {
return null; //not found
}
else return searchingNode(key).getElement(); //call another helper method.
}
// searching node
public BSTNode<E, K> searchingNode(K key) {
if(key == null) {
return null;
}
if(root == null) {
return null; //if empty tree
}
//if both keys are equal
if(key.compareTo(root.getKey()) == 0) {
return root;
}
//less than root key
else if(key.compareTo(root.getKey()) < 0) {
return searchBelow(root.getLeft(), key); //call the recursive search method.
}
//greater than root key
else if(key.compareTo(root.getKey()) > 0) {
return searchBelow(root.getRight(), key); //call the recursive search method.
}
else {
System.out.println(\"ERROR occured\");
return null;
}
}
}
