Click here to Skip to main content
15,894,896 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
the prompt is to write a program
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.


What I have tried:

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) {
if (t==null)
return newSearchResult(null,false);

// end if t == null
// t is not null, so search current node for x and proper link

node cur=t;
while(t != null){
cur=t;
k=t.count;
for (i = 1; i <= k; i++)
if (x == t.data[i])
return new SearchResult(t, true);

if (x < t.data[1])
t = t.link[0];
while( x < t.data[k])
k--;
t = t.link[k];
}
}

returnnew SearchResult(cur, false);

} // 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 <= t.count; 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
  
n = deg -1;
  
node T2;
or (T2= null ;;){// INFINITE LOOP
if (t.count < n){
  
data[j] = x;
link[j] = T2;
if (T2 != null)
}
node tmp = new node(x, deg+1);
tmp.link[0] = t.link[0];
for(j = 1; j <= t.count){
tmp.data[j] = t.data[j];
tmp.link[j] = t.link[j];
  
T2 = newnode(all data to the right of middle data);
  
x = data[j];
if (t == root) {
T1 = newnode(x) // new root
T1.link[0]= t;
T1.link[1]= T2;
root = T1;// root changed
T2.parent = T1;
t.parent = T1;
return;
  
}
t = t.parent;
}}

} // 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 <= n; 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 <= n; 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. Project 5, "

+ "\n\t BTree Insertion & Query program " + java.time.LocalDate.now());

xxxxxP5 t = new xxxxxP5 (); // xxxxx is the first 5 char of your last name

t.readinput();

} // end main method

} // end xxxxxP5 class
Posted
Updated 26-Apr-20 19:41pm
Comments
Patrice T 26-Apr-20 18:33pm    
and the errors are ...
Member 14768145 26-Apr-20 23:57pm    
error: <identifier> expected
error: ';' expected
Patrice T 27-Apr-20 0:06am    
Use Improve question to update your question.
So that everyone can pay attention to this information.
include line number.

1 solution

First off, do yourself a favour and indent your code so it's actually possible to work out what is going on there.

Secondly, look at teh error message - if I paste that code into an online compiler, it tells me teh first eror is on line 90:
Main.java:90: error:  expected
returnnew SearchResult(cur, false);
And a quick glance at that and it's obvious what the problem is: you need a space between "return" and "new".
Fix that, compile again, look at the first error.

Repeat this for all the other errors until you get a clean compilation, and you can start looking at runtime errors - and use the debugger for that!
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900