[JAVA] PLEASE MAKE CODE AS SIMPLE AS POSSIBLE!!!

(1)Objective: Binary Search Tree traversal (2 points)

Use traversal.pptx as guidance to write a program to build a binary search tree Dictionary. IBST KVpair are; is the Inventory record from the input record.

Download traversal-lab.pptx, inventory.txt, BinNode.java, BSTNode.java, BST.java, Dictionary.java and Inventory.java from Moodle.

Perform specifications as follow:

(a)Provide Delete and Retrieve functions for user to access the database.

(b)Modify BST.java to add printpostOrder, printpreOrder methods.

(c)At the end, display inorder, postorder and preorder of the tree.

(2)Objective: Provide range search function for Dictionary (2 points)

Add printRang method to BST.java that, given a low key value, and high key value, print all records in sorted order whose values fall between the two given keys. (Both low key and high key do not have to be keys on the list)

(3)Objective: Replacing recursive calls programming technique with using

Stack data structure (2 points)

Modify the StringTree.java to add method to traversal the tree using java.util.Stack instead of recursion. At the end, display the tree to ensure the order of records is the same as the recursive method. Download the stringFile.txt from Moodle as input for the database.

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

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

}

/** Source code example for "A Practical Introduction to Data Structures and Algorithm Analysis, 3rd Edition (Java)" by Clifford A. Shaffer Copyright 2008-2011 by Clifford A. Shaffer */

/** 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(); };

/** Source code example for "A Practical Introduction to Data Structures and Algorithm Analysis, 3rd Edition (Java)" by Clifford A. Shaffer Copyright 2008-2011 by Clifford A. Shaffer */

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 + " "); }

}

/** Source code example for "A Practical Introduction to Data Structures and Algorithm Analysis, 3rd Edition (Java)" by Clifford A. Shaffer Copyright 2008-2011 by Clifford A. Shaffer */

/** Binary tree node implementation: Pointers to children @param E The data element @param Key The associated key for the record */ class BSTNode implements BinNode { private Key key; // Key for this node private E element; // Element for this node private BSTNode left; // Pointer to left child private BSTNode 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 l, BSTNode 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 left() { return left; } public void setLeft(BSTNode p) { left = p; }

/** Get and set the right child */ public BSTNode right() { return right; } public void setRight(BSTNode p) { right = p; }

/** @return True if a leaf node, false otherwise */ public boolean isLeaf() { return (left == null) && (right == null); } }

/** Source code example for "A Practical Introduction to Data Structures and Algorithm Analysis, 3rd Edition (Java)" by Clifford A. Shaffer Copyright 2008-2011 by Clifford A. Shaffer */

/** 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(); }

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

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

// StringTree.java

//

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

import java.util.*;

public class StringTree

{

private Node root;

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

// Creates an initially empty tree.

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

public StringTree()

{

root = null;

}

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

// Adds a string to the tree.

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

public void addString (String str)

{

root = addStringToSubTree(str, root);

}

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

// Adds a string to the subtree with the given root node

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

private Node addStringToSubTree (String str, Node node)

{

Node result = node;

if (node == null)

result = new Node(str);

// If the new string comes before the string in the node, add

// the new string to the left child. Otherwise, add it to the

// right child.

else

if (str.compareTo(node.value) < 0)

node.left = addStringToSubTree(str, node.left);

else

node.right = addStringToSubTree(str, node.right);

return result;

}

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

// Prints the result of a depth-first traversal of the tree using

// recursion.

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

public void traverseWithRecursion()

{

traverseWithRecursion(root);

}

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

// Prints the elements in the specified tree using recursion.

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

private void traverseWithRecursion (Node node)

{

if (node != null)

{

traverseWithRecursion (node.left);

System.out.print (node.value+" ");

traverseWithRecursion (node.right);

}

}

}

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

// Node for a binary tree of Strings.

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

class Node

{

public String value;

public Node left;

public Node right;

public Node (String value)

{

this.value = value;

this.left = left;

this.right = right;

}

}

stringFile.txt

CV06C1250B MA06C1042A MA06C1043A SU04D1043B SU04D1042B CV06C1250A CV06D1250B HY09F3014A KI04D1297A