write a program to build a binary search tree Dictionary. Input records are from inventory.txt. The data for the BST KVpair are; Key is the PartNo and Element is the Inventory record from the input record.

Use inventory.txt, BinNode.java, BSTNode.java, BST.java, Dictionary.java and Inventory.java found below.

Dictionary.java

/** The Dictionary abstract class. */

public interface Dictionary {

/** 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

GT12C1068A,YUKON XL,07-14 GMC YUKON XL RT Front fender brace Lower Bracket Hinge,24.00

NI27E1251B,ALTIMA SDN,13-15 NISSAN ALTIMA SDN RT Front fender liner From 10-12 (CAPA),63.00

NI23H1297A,ALTIMA SDN,13-15 NISSAN ALTIMA SDN LT Front fender liner From 10-12 (CAPA),48.00

CV15F1067A,SILVERADO 1500 (NEW),07-13 CHEVY SILVERADO 1500 LT Front fender brace Lower Bracket Hinge,23.00

HY07E1288A,SONATA,15-16 HYUNDAI SONATA Front bumper cover 2.4L Std Type w/o Park Assist prime (CAPA),326.00

CV20B1225B,SILVERADO 1500 HYBRID,09-13 CHEVY SILVERADO 1500 HYBRID LT Front fender brace Lower Bracket Hinge,23.00

CV39A1251A,AVALANCHE,07-13 CHEVY AVALANCHE RT Front fender brace Lower Bracket Hinge,24.00

CV39A1250A,SUBURBAN,07-14 CHEVY SUBURBAN RT Front fender brace Lower Bracket Hinge,24.00

AC12C1250AQ,MDX,07-13 ACURA MDX LT Front fender liner (CAPA),68.00

AC12C1251AQ,MDX,07-13 ACURA MDX RT Front fender liner (CAPA),68.00

BinNode.java

/** ADT for binary tree nodes */

public interface BinNode {

/** Get and set the element value */

public E element();

public void setElement(E v);

/** @return The left child */

public BinNode left();

/** @return The right child */

public BinNode right();

/** @return True if a leaf node, false otherwise */

public boolean isLeaf();

}

BST.java

import java.lang.Comparable;

/** Binary Search Tree implementation for Dictionary ADT */

class BST, E>

implements Dictionary {

private BSTNode 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 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 inserthelp(BSTNode rt,

Key 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;

}

/** Remove a node with key value k

@return The tree with the node removed */

private BSTNode removehelp(BSTNode 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 temp = getmin(rt.right());

rt.setElement(temp.element());

rt.setKey(temp.key());

rt.setRight(deletemin(rt.right()));

}

}

return rt;

}

private BSTNode getmin(BSTNode rt) {

if (rt.left() == null) return rt;

return getmin(rt.left());

}

private BSTNode deletemin(BSTNode rt) {

if (rt.left() == null) return rt.right();

rt.setLeft(deletemin(rt.left()));

return rt;

}

private void printhelp(BSTNode 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 + " ");

}

}

//********************************************************************

// Inventory.java

//

//********************************************************************

public class Inventory

{

protected String PartNo;

protected String Model;

protected String Description;

protected Double ListPrice;

//-----------------------------------------------------------------

// Constructor: Sets up this inventory using the specified

// information.

//-----------------------------------------------------------------

public Inventory() {

}

public String GetPartNo()

{

return PartNo;

}

public void SetInventory (String ePartNo, String eModel, String eDescription, Double eListPrice)

{

PartNo = ePartNo;

Model = eModel;

Description = eDescription;

ListPrice = eListPrice;

}

//-----------------------------------------------------------------

// Returns a string including the basic inventory information.

//-----------------------------------------------------------------

public String toString()

{

String result = null;

if (PartNo != null)

{

result = "Part Number: " + PartNo + " ";

result += "Model: " + Model + " ";

result += "List Price: "+ Double.toString(ListPrice) + " ";

result += "Description: " + Description + " ";

}

return result;

}

//-----------------------------------------------------------------

//

//-----------------------------------------------------------------

}