I am very confused about this program, asking 5 th time not sure about any solut

Question

I am very confused about this program, asking 5 th time not sure about any solutions. I have shown the input file (72, ,outdoor bag95, ,café123, ,employee coupon................(lot more)) below. I wanted to test program of binary search keys (72, 95, 123...) and total time to complete the search. Please explain with your input file and results using screen shot).

Q) Implement Search (T data) to search for a node having value of key = data in a Binary Search Tree.

Use the Binary Search Tree to build a search tree using the given input file that consists of two fields: key and the corresponding description. Use the search tree created to find the description associated with a given set of keys. The input file (input1.txt) the key and corresponding descriptions in a comma separated file. test the program for the given search keys and determine the total time taken to complete the search. Wanted code in java.

Clues:

You have to create nodes only for the key values, not the other fields,(Test file looks like this)

72, ,outdoor bag95, ,café123, ,employee coupon................(lot more)

Theses are the 3key values: 72, 95, 123, these 3 key values need to store in BST.

Similarly with the input file, you read the first line and only search for the key value. 72 not the other fields after the key.

**** clue2:

The data given in the comma separated file is in the following format:

[Product ID],[Product Qty./Weight],[Product Description]

You need to parse the data from the file and store as objects in BST form.

The search method should take input the Product ID as the search key and should return Product Description if found in the BST.

Please provide the good solution.

Explanation / Answer

Given below is the code . With just 3 values in input file , the time taken is very neglible. You can test with your input file with many entries. Please do rate the answer if it helped. Thank you.

To indent code in eclipse, select code by pressing Ctrl+A and then Ctrl+i

//BST with 2 generic parameters for key and value
public class BinarySearchTree<K extends Comparable<K>, V> {
class Node
{
K key;
V value;
Node right, left;
Node(K key, V value)
{
this.key = key;
this.value = value;
}
}
private Node root;
public BinarySearchTree()
{
root = null;
}
public boolean insert(K key, V value)
{
if(root == null)
{
root = new Node(key, value);
return true;
}
else
{
Node curr = root;
while(curr != null)
{
if(curr.key.equals(key)) //duplicate
return false;
else if(key.compareTo(curr.key) < 0)
{
if(curr.left == null)
{
curr.left = new Node(key, value);
return true;
}
else
curr = curr.left;
}
else
{
if(curr.right == null)
{
curr.right = new Node(key, value);
return true;
}
else
curr = curr.right;
}
}
}
return false;
}
V search(K key)
{
Node curr = root;
while(curr != null)
{
if(curr.key.equals(key)) //found match
return curr.value;
else if(key.compareTo(curr.key) < 0)
curr = curr.left;
else
curr = curr.right;
}
return null; //not found in loop above
}
private void inOrderPrint(Node n)
{
if(n == null)return;
inOrderPrint(n.left);
System.out.println("Key:" + n.key + ", Value: " + n.value);
inOrderPrint(n.right);
}
public void print()
{
inOrderPrint(root);
System.out.println("-----------------");
}
}

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class ProductBST {
//searches the BST for the key and times the search operation
private static void timedSearch(BinarySearchTree<Integer, String> bst, Integer key)
{
long start = System.currentTimeMillis();
String value = bst.search(key);
long end = System.currentTimeMillis();
long elapsedMilliSecs = (end - start);
//System.out.println(start + " " + end);
if(value == null)
System.out.println("Key " + key + " not found");
else
System.out.print("Key: " +key + ", Value: " + value);
System.out.println("Search took " + elapsedMilliSecs + " milli secs.");
}
public static void main(String[] args) {
//bst with key as Integer and value as String type
BinarySearchTree<Integer, String> bst = new BinarySearchTree<Integer, String>();
Scanner keybd = new Scanner(System.in);
String filename;
System.out.println("Enter input filename");
filename = keybd.next();
try {
Scanner infile = new Scanner(new File(filename));
String line;
while(infile.hasNextLine())
{
line = infile.nextLine().trim();
if(line.isEmpty())
continue;
String[] tokens = line.split(",");
bst.insert(Integer.parseInt(tokens[0]), tokens[2]);
}
infile.close();
System.out.println("The BST contents are ");
bst.print();
Integer key;
String ans = "y";
while(ans.equalsIgnoreCase("y"))
{
System.out.print("Enter the key to search: ");
key = keybd.nextInt();
timedSearch(bst, key);
System.out.println("Search another? y/n: ");
ans = keybd.next();
}
} catch (FileNotFoundException e) {
System.out.println(e.getMessage());
}
}
}

input file:

72, ,outdoor bag
95, ,café
123, ,employee coupon

output

Enter input filename
products.txt
The BST contents are
Key:72, Value: outdoor bag
Key:95, Value: café
Key:123, Value: employee coupon
-----------------
Enter the key to search: 95
Key: 95, Value: caféSearch took 0 milli secs.
Search another? y/n:
y
Enter the key to search: 100
Key 100 not found
Search took 0 milli secs.
Search another? y/n: n

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.