Java ------Binary-sort tree Problem Description: The problem to be solved is the
ID: 3866594 • Letter: J
Question
Java ------Binary-sort tree
Problem Description:
The problem to be solved is the building of a binary tree in RAM using methods that recursively call themselves to construct the tree. If the values are stored correctly, they can be retrieved in numeric order by merely traversing the tree and checking the values for numeric order. It is not the world’s best sort algorithm but it has two points in its favor: (a) it can be used to insert values that occur leisurely but that can be retrieved in numeric order at a moment’s notice, and (b) it will give you some practice using recursion.
The program will have 3 classes; (1) the class containing the “main” method, (2) a class named treeSort and (3) a class named node. Objects of the node class will be used as nodes in the sort-tree while an object of the treeSort class will receive long integer numeric values and create nodes to contain them in the tree. You can think of the tree as a “two-dimensional linked-list” and like any linked list, it exists in RAM but is built dynamically. The “main” method will generate the random values and send them to the sortTree by calling a method.
SortTree will then have at least four methods:
public boolean insert(long value)
This method will be called by “main” and will insert the value into the tree. If the value to be inserted is a duplicate of one already in the tree, the insertion will be terminated without any node being created and the value “true” will be returned to the caller. Otherwise insert will return the value “false”.
public long [] retrieve( )
This method will create an array of type “long” and will fill it with the values in sorted order from the tree. Since the insert method can count the number of values currently in the tree, creating the array should be able to use this value to size the array exactly.
public boolean isPresent(long value)
This method will search the tree for the argument value and if found, will return “true” If the value is not found, “false” will be returned.
public int getCount( )
This method will return the number of values currently in the tree. It will count only the actual values, not the duplicates for which “insert” returned “false”.
Explanation / Answer
import java.util.*;
class Node
{
Node left;
Node right;
long val;
Node(long val_) //
{
val = val_;
}
}
class SortTree
{
Node root;
int treeSize;
public boolean isPresent(long value)
{
Node curr = root;
while(curr!=null)
{
if(curr.val==value)
{
return true;
}
else if(curr.val > value) // look at left subtree
{
curr = curr.left;
}
else
{
curr = curr.right; // go to right subtree
}
}
return false;
}
public boolean insert(int value) {
Node newNode = new Node(value);
if (root == null) {
root = newNode;
treeSize++; // tree is empty
return true;
}
Node curr = root;
Node parent = null;
while (true) {
parent = curr;
if (value <= curr.val) {
if (value == curr.val)
return false; // duplicate
curr = curr.left;
if (curr == null) {
parent.left = newNode;// left node
treeSize++;
return true;
}
} else {
curr = curr.right;
if (curr == null) {
parent.right = newNode;// right node
treeSize++;
return true;
}
}
}
}
public int getCount()
{
return treeSize; // Return tree size
}
public long [] retrieve()
{
long[] array = new long[treeSize];
int[] index = new int[1];
inorder(root, array, index);
return array;
}
public void inorder(Node root, long[] array, int[] index)
{
if(root!=null)
{
inorder(root.left, array, index);
// System.out.print(" " + root.val);
array[index[0]++] = root.val;
inorder(root.right, array, index);
}
}
}
class Main
{
public static void main(String[] args)
{
SortTree st = new SortTree();
st.insert(2);
st.insert(1);
st.insert(3);
System.out.println(st.getCount()); // Print 3
System.out.println(st.isPresent(1)); // Print rue
System.out.println(st.isPresent(4));// Print false
st.insert(1); // duplicate
System.out.println(st.getCount()); // Again print 3
long[] a = st.retrieve();
System.out.println(Arrays.toString(a)); // Print 1 2 3
}
}
The output of above program would be:
3
true
false
3
[1, 2, 3]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.