Write code in Java: A 2-3-4 tree can be used as a sorting machine. Write a sort(
ID: 3699357 • Letter: W
Question
Write code in Java: A 2-3-4 tree can be used as a sorting machine. Write a sort() method that has passed an array of key values from main() and writes them back to the array in sorted order.
*attached are the programming guidelines* please include the objective, scope, limitations, input, etc of the program Instructions to Submit Programming Assignments: i. Please provide a Final Report. 2. Documentation standards should be followed for the programs. That is you should provide commenting for functions and important logical points. tshould include . Objective, Scope and Limitation. Il. Program Code II.At least two different outputs (Screen Shots) III. The environment where the program runs V.A sample is provided below please follow it. 4. Zip all the programs files along with the Final Report in a word document and upload in the WebCT and also one hard copy should be submitted on due date Sample Instructions to follow in the Final Report Document
Explanation / Answer
import java.io.*;
class DataItem
{
public long dData;
public DataItem(long dd)
{ dData = dd; }
public void displayItem()
{ System.out.print("/"+dData);}
}
class Node234
{
private static final int ORDER = 4;
private int numItems;
private Node234 parent;
private Node234 childArray[] = new Node234[ORDER];
private DataItem itemArray[] = new DataItem[ORDER-1];
public void connectChild(int childNum, Node234 child)
{
childArray[childNum] = child;
if(child != null)
child.parent = this;
}
public Node234 disconnectChild(int childNum)
{
Node234 tempNode = childArray[childNum];
childArray[childNum] = null;
return tempNode;
}
public Node234 getChild(int childNum)
{ return childArray[childNum]; }
public Node234 getParent()
{ return parent; }
public boolean isLeaf()
{ return (childArray[0]==null) ? true : false; }
public int getNumItems()
{ return numItems; }
public DataItem getItem(int index)
{ return itemArray[index]; }
public boolean isFull()
{ return (numItems==ORDER-1) ? true : false; }
public int findItem(long key)
{
for(int j=0; j<ORDER-1; j++)
{
if(itemArray[j] == null)
break;
else if(itemArray[j].dData == key)
return j;
}
return -1;
}
public int insertItem(DataItem newItem)
{
numItems++;
long newKey = newItem.dData;
for(int j=ORDER-2; j>=0; j--)
{
if(itemArray[j] == null)
continue;
else
{
long itsKey = itemArray[j].dData;
if(newKey < itsKey)
itemArray[j+1] = itemArray[j];
else
{
itemArray[j+1] = newItem;
return j+1;
}
}
}
itemArray[0] = newItem;
return 0;
}
public DataItem removeItem()
{
DataItem temp = itemArray[numItems-1];
itemArray[numItems-1] = null;
numItems--;
return temp;
}
public void displayNode()
{
for(int j = 0; j<numItems; j++)
itemArray[j].displayItem();
System.out.println("/");
}
}
class Tree234
{
private Node234 root = new Node234();
public int find(long key)
{
Node234 curNode = root;
int childNumber;
while(true)
{
if( (childNumber=curNode.findItem(key)) != -1)
return childNumber;
else if( curNode.isLeaf() )
return -1;
else
curNode = getNextChild(curNode, key);
}
}
public void findMinimum()
{
Node234 curNode = root;
Node234 answer = new Node234();
while((curNode = curNode.getChild(0)) != null)
answer = curNode;
System.out.println("Minimum value is "+answer.getItem(0).dData);
}
public void traverseInOrder()
{
recTraverse(root);
}
private void recTraverse(Node234 curNode)
{
if(curNode.isLeaf())
{
for(int j = 0; j<curNode.getNumItems(); j++)
curNode.getItem(j).displayItem();
return;
}
else
{
for(int j = 0; j < curNode.getNumItems()+1; j++)
{
recTraverse(curNode.getChild(j));
if(j < curNode.getNumItems())
curNode.getItem(j).displayItem();
}
}
}
public void sortTraverse(long[] theArray)
{
int i = 0;
recSortTraverse(root, theArray, i);
}
private int recSortTraverse(Node234 curNode, long[] theArray, int i)
{
if(curNode.isLeaf())
{
for(int j = 0; j<curNode.getNumItems(); j++)
{
theArray[i] = curNode.getItem(j).dData;
i++;
}
return i;
}
else
{
for(int j = 0; j < curNode.getNumItems()+1; j++)
{
i = recSortTraverse(curNode.getChild(j), theArray, i);
if(j < curNode.getNumItems())
{
theArray[i] = curNode.getItem(j).dData;
i++;
}
}
return i;
}
}
public void insert(long dValue)
{
Node234 curNode = root;
DataItem tempItem = new DataItem(dValue);
while(true)
{
if (curNode.isFull() )
{
split(curNode);
curNode = curNode.getParent();
curNode = getNextChild(curNode, dValue);
}
else if (curNode.isLeaf() )
break;
else
curNode = getNextChild(curNode, dValue);
}
curNode.insertItem(tempItem);
}
public void split(Node234 thisNode)
{
DataItem itemB, itemC;
Node234 parent, child2, child3;
int itemIndex;
itemC = thisNode.removeItem();
itemB = thisNode.removeItem();
child2 = thisNode.disconnectChild(2);
child3 = thisNode.disconnectChild(3);
Node234 newRight = new Node234();
if(thisNode==root)
{
root = new Node234();
parent = root;
root.connectChild(0, thisNode);
}
else
parent = thisNode.getParent();
itemIndex = parent.insertItem(itemB);
int n = parent.getNumItems();
for(int j = n-1; j>itemIndex; j--)
{
Node234 temp = parent.disconnectChild(j);
parent.connectChild(j+1, temp);
}
parent.connectChild(itemIndex+1, newRight);
newRight.insertItem(itemC);
newRight.connectChild(0, child2);
newRight.connectChild(1, child3);
}//end split()
public Node234 getNextChild(Node234 theNode, long theValue)
{
int j;
int numItems = theNode.getNumItems();
for(j=0; j<numItems; j++)
{
if( theValue < theNode.getItem(j).dData)
return theNode.getChild(j);
}
return theNode.getChild(j);
}
public void displayTree()
{
recDisplayTree(root, 0, 0);
}
private void recDisplayTree(Node234 thisNode, int level, int childNumber)
{
System.out.print("level="+level+" child="+childNumber+" ");
thisNode.displayNode();
int numItems = thisNode.getNumItems();
for(int j = 0; j < numItems+1; j++)
{
Node234 nextNode = thisNode.getChild(j);
if(nextNode != null)
recDisplayTree(nextNode, level+1, j);
else
return;
}
}
}
public class Tree234App
{
public static void sort(long[] theArray, int counter)
{
Tree234 sortingTree = new Tree234();
for(int j = 0; j < counter; j++)
sortingTree.insert(theArray[j]);
sortingTree.sortTraverse(theArray);
}
public static void main(String[] args) throws Exception
{
long value;
Tree234 theTree = new Tree234();
theTree.insert(50);
theTree.insert(40);
theTree.insert(60);
theTree.insert(30);
theTree.insert(70);
while(true)
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, minimum, traverse, order, or find: ");
char choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value);
break;
case 'm':
theTree.findMinimum();
break;
case 'o':
value = 0;
long[] arrayToSort = new long[20];
int counter = 0;
while(value != -1 && counter < 20)
{
System.out.print("Enter value (enter '-1' to stop): ");
value = getInt();
if(value != -1)
{
arrayToSort[counter] = value;
counter++;
}
}
System.out.println("Before sorting...");
for(int j = 0; j < counter; j++)
System.out.print(arrayToSort[j] + " ");
sort(arrayToSort, counter);
System.out.println("After sorting...");
for(int j = 0; j < counter; j++)
System.out.print(arrayToSort[j] + " ");
System.out.println("");
break;
case 't':
theTree.traverseInOrder();
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
int found = theTree.find(value);
if(found != -1)
System.out.println("Found " + value);
else
System.out.println("Could not find " + value);
break;
default:
System.out.println("Invalid entry!");
}
}
}
public static String getString() throws Exception
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static char getChar() throws Exception
{
String s = getString();
return s.charAt(0);
}
public static int getInt() throws Exception
{
String s = getString();
return Integer.parseInt(s);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.