NOTE: Projects will not be graded if:
Your complete project isnotin aSINGLExxxxxP5.java file, where xxxxx is the first 5 characters ofyour last name andP5 is the project number.
It does not readinputfrom System.in. i.e. command prompt.
It’s not uploaded in CANVAS.
Using package or any java utilities such as arraylist, LinkedList, map, queue….i.e.
the whole code should be written by yourself as explained in class.
Write an efficient java program xxxxxP5.java that reads n, name and idno from input and inserts them in a btree of degree 3(2-3Tree). Then reads k idno from input and queries the btree.
To compile: javac xxxxxP5.java
To execute: java xxxxxP5
Your java program skeleton should be as follow: // More explanation in 4/14 lecture
import java.util.*; import java.io.*;
public class xxxxxP5{ //btree3 is 2-3Tree
PrintStream prt = System.out;
int deg; // degree of Btree
node root = null; //root of the btree3
// class used for search
private class SearchResult{
node leaf; boolean found;
// SearchResult Constructor
SearchResult(node t, boolean k){
leaf = t; found = k;
} // endSearchResult Constructor
} // end class SearchResult
// class node
private class node {
int count; // current no. of data in the node
int[] id; String[] name; node link[], parent;
node(int x, String s, int k) { // node Constructor
count = 1; // Allocate k spaces for id, name and link arrays
id = new int[k]; name = new String[k]; link = new node[k];
String[1] = s; id[1] = x; //NOTE:id[0]&name[0] are not used
} // end node Constructor
} // end class node
// SEARCH FOR X in BTree
private SearchResult search(int x) {
return search(x, root);
} // end serach
// Search for x in BTree with root t
private SearchResult search(int x, node t) {
} // end search method
// Inorder Traversal of BTree starting from root
private void inorder() {
prt.printf("\nInorder: "); // contents of the BTree
inorder(root); prt.printf("\n");
} // end inorder method
// Inorder Traversal, BTree starting from node t
private void inorder(node t){
if (t == null) return;
inorder(t.link[0]);
for (int i = 1; i
prt.printf(t.id[i] + " ");
inorder(t.link[i]);
} // end for
} // end inorder method
private void insert(int x, String s){ // insert x & s in BTree
prt.printf("\nInsert %d, %s", x, s);
if (root == null){ // insert x into empty BTree
root = new node(x, s, deg); return;
} // end if root == null
SearchResult r = search(x); // First search for x
if( r.found == false) insert(x, s, r.leaf); // insert if x is not in btree
else prt.printf(" Ooops..Duplicate...");
} // end insert method
// insert id & name in leaf node t
private void insert(int x, String s, node t){
//insert x, s and pointer T2=null in leaf node t
} // end insert method
private void readinput() { // read input
int j, x; String s; deg = 3;
try{
Scanner inf = new Scanner(System.in);
int n = inf.nextInt(); //read no. of data
// read input and create BTree
for(j = 1; j
x = inf.nextInt(); //read next idno
s = inf.next(); //read next name
insert(x, s);
} // end for
inorder(); // print inorder traversal of btree
int n = inf.nextInt(); //read no. of data to query
// Query BTree
for(j = 1; j
x = inf.nextInt(); //read next idno
SearchResult t = search(x);
if (t.found == false) prt.printf("\n %d does not EXIST.", x);
else prt.printf("\nName of %d is %s.", x, t.name);
} // end Query BTree
} // end readinput method
// main method
public static void main(String[] args) throws Exception{
// Make sure to change the name in next line
System.out.print("\n\tG. Dastghaiby Fard COMP182 Project 5, "
+ "\n\t BTree Insertion & Query program " + java.time.LocalDate.now());
xxxxxP5 t = new xxxxxP5 (); //xxxxxis the first 5 char of yourlast name
t.readinput();
} // end main method
} // end xxxxxP5 class