Can someone help me with this Data Structures (Binary Search Tree) assignment? T
ID: 3762865 • Letter: C
Question
Can someone help me with this Data Structures (Binary Search Tree) assignment? Thanks.
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
Explanation / Answer
package com.bst;
/* Class BSTNode */
class BSTNode {
BSTNode left, right;
int data;
/* Constructor */
public BSTNode() {
left = null;
right = null;
data = 0;
}
/* Constructor */
public BSTNode(int n) {
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BSTNode n) {
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n) {
right = n;
}
/* Function to get left node */
public BSTNode getLeft() {
return left;
}
/* Function to get right node */
public BSTNode getRight() {
return right;
}
/* Function to set data to node */
public void setData(int d) {
data = d;
}
/* Function to get data from node */
public int getData() {
return data;
}
}
package com.bst;
class BST {
private BSTNode root;
/* Constructor */
public BST() {
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty() {
return root == null;
}
/* Functions to insert data */
public void insert(int data) {
root = insert(root, data);
}
/* Function to insert data recursively */
private BSTNode insert(BSTNode node, int data) {
if (node == null)
node = new BSTNode(data);
else {
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Function to count number of nodes recursively */
private int countNodes(BSTNode r) {
if (r == null)
return 0;
else {
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
/* Functions to search for an element */
public boolean search(int val) {
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BSTNode r, int val) {
boolean found = false;
while ((r != null) && !found) {
int rval = r.getData();
if (val < rval)
r = r.getLeft();
else if (val > rval)
r = r.getRight();
else {
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorder() {
inorder(root);
}
private void inorder(BSTNode r) {
if (r != null) {
inorder(r.getLeft());
System.out.print(r.getData() + " ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
}
package com.bst;
import java.util.Random;
import java.util.Scanner;
/* Class BinarySearchTree */
public class BStree {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BST bst = new BST();
System.out.println("Binary Search Tree Test ");
int numbers[] = new int[100];
Random random = new Random();
int low = 1, high = 99;
for (int i = 0; i < 100; i++) {
int randomNum = random.nextInt((high - low) + 1) + low;
numbers[i] = randomNum;
}
System.out.println("Random Numbers are :");
for (int i = 0; i < 100; i++) {
System.out.print(numbers[i] + " ");
}
for (int i = 0; i < 100; i++) {
bst.insert(numbers[i]);
}
System.out.println(" infix recursive :");
bst.inorder();
}
}
OUTPUT:
Binary Search Tree Test
Random Numbers are :
18 50 29 34 12 44 80 87 22 4 54 54 94 90 51 64 94 22 41 47 55 79 73 49 14 29 13 14 72 71 61 95 98 56 66 11 29 57 43 38 85 42 39 13 89 91 17 81 54 63 54 59 31 74 38 78 91 66 25 57 6 88 70 79 2 67 40 92 28 32 75 64 94 57 41 70 61 79 28 83 13 3 52 97 82 2 3 28 59 99 87 2 3 17 52 33 83 40 21 85
infix recursive :
2 2 2 3 3 3 4 6 11 12 13 13 13 14 14 17 17 18 21 22 22 25 28 28 28 29 29 29 31 32 33 34 38 38 39 40 40 41 41 42 43 44 47 49 50 51 52 52 54 54 54 54 55 56 57 57 57 59 59 61 61 63 64 64 66 66 67 70 70 71 72 73 74 75 78 79 79 79 80 81 82 83 83 85 85 87 87 88 89 90 91 91 92 94 94 94 95 97 98 99