Objectives: To gain experience with Binary Search Trees and building your own Li
ID: 3688021 • Letter: O
Question
Objectives:
To gain experience with Binary Search Trees and building your own LinkedList.
Documentation:
Explain the purpose of the program as detail as possible - 10%.
Develop a solution for the problem and mention algorithms to be used -10%
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 45%
Naming of program as required 5%
Print out of source code 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
To gain experience with Binary Search Trees and building your own LinkedList. Documentation: Explain the purpose of the program as detail as possible - 10%. Develop a solution for the problem and mention algorithms to be used -10% 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 45% Naming of program as required 5% Print out of source code 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.jarExplanation / Answer
import java.util.*;
public class BSTree {
static LinkedList<Integer> treeList = new LinkedList<Integer>();
private int data;
private int root;
private BSTree left;
private BSTree right;
static int c = 0;
// This is the actual binary tree
static BSTree tree = new BSTree(100);
public BSTree(int data){
this.data = data;
}
public void setData(int data){
this.data = data;
}
public int getData(){
return data;
}
public void setRoot(int root){
this.root = root;
}
public int getRoot(){
return root;
}
public void setLeft(BSTree left){
this.left = left;
}
public BSTree getLeft(){
return left;
}
public void setRight(BSTree next){
this.right = next;
}
public BSTree getRight(){
return right;
}
public void setLeft(int data){
BSTree temp = new BSTree(data);
temp.left = null;
temp.right = null;
temp.data = data;
this.left = temp;
}
public void setRight(int data){
BSTree temp = new BSTree(data);
temp.left = null;
temp.right = null;
temp.data = data;
this.right = temp;
}
// 1) Generate 100 random integer numbers ranging from 1 - 99 [CHECK]
//Precondition: No inputs.
//Postcondition: Prints out the layout of the output
// as well as the 100 random integers, console log, and sorted BSTree
public static void main(String args[]){
int count = 0;
System.out.println();
System.out.println(" [BINARY SEARCH TREE] ");
System.out.println("[---- 100 Random Unsorted Integers (Between 0 - 99) ----] ");
System.out.println(" Random Number Count ");
for(int i = 0; i <= 100; i ++){
int random = (int)(Math.random() * 100);
treeList.add(random);
System.out.println(" " + treeList.get(i) + " " + count);
count++;
}
System.out.println("-----------------------------------------------------");
System.out.println("[Console]:");
// Initialized the root as the very first value in the Linked List
BSTree myBinarySearchTree = new BSTree(treeList.get(0));
myBinarySearchTree.setRoot(treeList.get(0));
// Adds sequentially the values in the treeList (linked list)
// into the BSTree tree that was initialized to hold the values
// as a binary search tree would
for(int i = 0; i < treeList.size(); i++){
//System.out.println(treeList.get(i));
myBinarySearchTree.add(treeList.get(i));
}
System.out.println("-----------------------------------------------------");
System.out.println(" [Infix Recursive Method print out]"
+ " (Duplicates are not included): ");
BSTree.printInfix(myBinarySearchTree);
System.out.println("-----------------------------------------------------");
}
//Precondition: Takes in BSTree root to use root value
//Postcondition: No return. Prints the root's left and right values or return nothing
private static void printInfix(BSTree root){
if(root == null){
//System.out.println(" if");
return;
} else{
c++;
printInfix(root.getLeft());
System.out.println(" " + root.getData());
printInfix(root.getRight());
}
}
//Precondition: Takes in an integer
//Postcondition: returns false if data == data; otherwise returns true plus how the node is inserted
public boolean add(int data) {
if (data == this.data){
System.out.println("Inserting this.data " + data);
return false;
}
else if (data < this.data) {
if (left == null) {
System.out.println("Inserting new node " + data + " to left");
left = new BSTree(data);
return true;
} else{
return left.add(data);
}
} else if (data > this.data) {
if (right == null) {
System.out.println("Inserting new node " + data + " to right");
right = new BSTree(data);
return true;
} else
System.out.println("Inserting " + data + " to right");
return right.add(data);
}
return false;
}
}
sample output
[BINARY SEARCH TREE]
[---- 100 Random Unsorted Integers (Between 0 - 99) ----]
Random Number Count
78 0
29 1
52 2
34 3
87 4
27 5
68 6
Terminal
68 6
77 7
44 8
79 9
4 10
17 11
93 12
50 13
69 14
64 15
70 16
40 17
97 18
Terminal
28 19
38 20
42 21
56 22
31 23
99 24
17 25
2 26
13 27
22 28
71 29
28 30
84 31
Terminal
93 32
19 33
92 34
24 35
38 36
94 37
33 38
87 39
49 40
97 41
52 42
16 43
57 44
Terminal
-----------------------------------------------------
[Console]:
Inserting this.data 78
Inserting new node 29 to left
Inserting new node 52 to right
Inserting 34 to right
Inserting new node 34 to left
Inserting new node 87 to right
Inserting new node 27 to left
Inserting 68 to right
Inserting new node 68 to right
Inserting 77 to right
Inserting 77 to right
HelloWorld.java
Compile | Execute | Share Project
Inserting this.data 52
-----------------------------------------------------
[Infix Recursive Method print out]
(Duplicates are not included):
2
4
5
7
8
9
10
82
84
85
86
87
92
93
94
95
97
99
-----------------------------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.