In Java Please Objectives: To gain experience with Binary Search Trees and build
ID: 3857763 • Letter: I
Question
In Java Please
Objectives:
To gain experience with Binary Search Trees and building your own LinkedList.
Documentation:
Explain the purpose of the program as detail as possible - 8%.
Develop a solution for the problem and mention algorithms to be used -12%
List data structures to be used in solution. - 5%.
Give a description of how to use the program and expected input/output - 5%
Explain the purpose of each class you develop in the program. - 5%.
Programming:
For each method, give the pre and post conditions and invariant, if any - 10%
Program execution according to the requirements given 50%
Naming of program as required 5%
Description of Program
You are to write a program name BSTree.java that will:
Generate 100 random integer numbers ranging from 1 – 99.
Store these numbers in a data structure of your choice and display the data on the screen. DO NOT SORT THIS DATA STRUCTURE.
Now build a Binary Search Tree using this set of numbers. You MUST insert the values into the tree starting from the first element of your Data Structure and go sequentially.
After building the tree, use an infix recursive method to display the data on the screen.
To build the Binary Search Tree, you must create your own Linked List.
What to turn in
Turn in BSTree.java, BStree.class OR BSTree.jar in the A#5 folder in iCollege (D2L) no later than
Explanation / Answer
import java.util.*;
/* Class Node */
class Node
{
Node left, right;
int data;
/* Constructor */
public Node(int n)
{
left = null;
right = null;
data = n;
}
}
/* Class BST */
class BST
{
private Node root;
/* Constructor */
public BST()
{
root = null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private Node insert(Node node, int data)
{
if (node == null)
node = new Node(data);
else
{
if (data <= node.data)
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(Node r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data +" ");
inorder(r.right);
}
}
}
/* Class BSTTree */
public class BSTTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BST bst = new BST();
System.out.println("Linked List Binary Search Tree Test ");
char ch;
/* Accept input */
int co=1;
do
{
Random rand = new Random();
int n = rand.nextInt(99) + 1;
bst.insert( n );
co++;
} while (co!=100);
System.out.print(" In order : ");
bst.inorder();
}
}
========================================================
Output:
Linked List Binary Search Tree Test
In order : 3 3 4 5 5 7 8 8 8 8 9 9 10 11 11 13 15 16 17 18 18 18 18 19 19 21 22 24 26 26 27 28 29 29 30 31 32 33 34 35 36 38 38 43 45 45 46 46 47 48 48 48 49 50 50 52 53 53 53 55 56 57 57 58 58 59 59 61 63 64 66 66 67 71 71 73 73 73 74 74 76 77 78 79 80 82 85 87 89 91 92 93 94 96 96 97 97 97 99
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.