Please ask the user to input a low range and a high range and then print the ran
ID: 3805483 • Letter: P
Question
Please ask the user to input a low range and a high range and then print the range between them.
Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys from the inventory.txt file. (Both low key and high key do not have to be a key on the list).
****Please seperate the information in text file by product id, car_name, details, Price, etc
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
BST.java
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 + " ");
}
}
BSTNode.java
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); }
}
BinNode.java
/** ADT for binary tree nodes */
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();
}
Explanation / Answer
public class BinarySearchTree {
/**
* Construct the tree.
*/
public BinarySearchTree( ) {
root = null;
}
/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( Comparable x ) {
root = insert( x, root );
}
/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( Comparable x ) {
root = remove( x, root );
}
/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) {
root = removeMin( root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( ) {
return elementAt( findMin( root ) );
}
/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public Comparable findMax( ) {
return elementAt( findMax( root ) );
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return root == null;
}
/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
throw new DuplicateItemException( x.toString( ) ); // Duplicate
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;
return t;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match
}
return null; // Not found
}
/** The tree root. */
protected BinaryNode root;
// Test program
public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );
for( int i = 1; i < NUMS; i+= 2 )
t.remove( new Integer( i ) );
if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 2; i < NUMS; i+=2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );
for( int i = 1; i < NUMS; i+=2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( "Find error2!" );
}
}
}
// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of this package.
class BinaryNode {
// Constructors
BinaryNode( Comparable theElement ) {
element = theElement;
left = right = null;
}
// Friendly data; accessible by other package routines
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
/**
* Exception class for duplicate item errors
* in search tree insertions.
* @author Mark Allen Weiss
*/
public class DuplicateItemException extends RuntimeException {
/**
* Construct this exception object.
*/
public DuplicateItemException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message ) {
super( message );
}
}
/**
* Exception class for failed finds/removes in search
* trees, hash tables, and list and tree iterators.
* @author Mark Allen Weiss
*/
public class ItemNotFoundException extends RuntimeException {
/**
* Construct this exception object.
*/
public ItemNotFoundException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public ItemNotFoundException( String message ) {
super( message );
}
}