Write a Java program named BSTree.java that will:
1) Generate 20 random integer numbers ranging from 1-99.
2) Build a Binary Search Tree using this set of numbers. Write the add method.
3) After building the tree, display the data into three formats: prefix order, infix order, and postfix order.
4) Write a method to delete an element from the Binary Search Tree. First search the item in your TREE and then delete it.
Code:
import java.util.*;
//Creating Node with Basic Functionalities
class BSTNode
{
BSTNode left, right;
int data;
//An empty node
public BSTNode()
{
left = null;
right =
null;
data = 0;
}
//Creating a node with value n
public BSTNode(int n)
{
left = null;
right =
null;
data = n;
}
//Setting left node
public void setLeft(BSTNode n)
{
left = n;
}
//Setting right node
public void setRight(BSTNode n)
{
right = n;
}
//Function returns left node
public BSTNode getLeft()
{
return left;
}
//Function returns right node
public BSTNode getRight()
{
return
right;
}
//Setting data to node
public void setData(int d)
{
data = d;
}
//Getting data of node
public int getData()
{
return data;
}
}
class BST
{
BSTNode root;
//Initially tree is null
public BST()
{
root = null;
}
//Checking tree is empty or not
public boolean isEmpty()
{
if(root ==
null)
return
true;
else
return
false;
}
//Public method to get call from Main method of other
class
//Private method to get call from within the
class
public void add(int data)
{
root = add(root,
data);
}
//Method to insert data
private BSTNode add(BSTNode node, int
data)
{
//If tree is empty then newNode
will become root
if (node ==
null)
node = new BSTNode(data);
//If tree is non
empty
else
{
//new node data
is less than parent data then make it as left child
//Otherwise make
it as right child
if (data < node.getData())
node.left = add(node.left, data);
else
node.right = add(node.right, data);
}
return node;
}
public void prefixOrder()
{
prefixOrder(root);
}
//Preorder is root->left->right
private void prefixOrder(BSTNode r)
{
if (r !=
null)
{
System.out.print(r.getData() +" ");
prefixOrder(r.getLeft());
prefixOrder(r.getRight());
}
}
public void infixOrder()
{
infixOrder(root);
}
//Inorder is left->root->right
private void infixOrder(BSTNode r)
{
if (r !=
null)
{
infixOrder(r.getLeft());
System.out.print(r.getData() +" ");
infixOrder(r.getRight());
}
}
public void postfixOrder()
{
postfixOrder(root);
}
//Postorder is left->right->root
private void postfixOrder(BSTNode r)
{
if (r !=
null)
{
postfixOrder(r.getLeft());
postfixOrder(r.getRight());
System.out.print(r.getData() +" ");
}
}
public boolean search(int val)
{
return
search(root, val);
}
//Method to search element
private boolean search(BSTNode r, int
val)
{
boolean found =
false;
while ((r != null)
&& !found)
{
int rval = r.getData();
//If searching
value is less that current node data then go left
if (val < rval)
r = r.getLeft();
//If searching
value is less that current node data then go right
else if (val > rval)
r = r.getRight();
//If value is
equal to current node data
else
{
found = true;
break;
}
found = search(r, val);
}
return
found;
}
public void delete(int k)
{
if
(isEmpty())
System.out.println("Tree Empty");
else if (search(k)
== false)
System.out.println("Sorry "+ k +" is not present");
else
{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
System.out.println("\nAfter Deletion");
System.out.println("\nPrefix order: ");prefixOrder();
System.out.println("\nInfix order: ");infixOrder();
System.out.println("\nPostfix order: ");postfixOrder();
}
}
private BSTNode delete(BSTNode root, int
k)
{
BSTNode p, p2,
n;
//If desired value found
if (root.getData()
== k)
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
//If single node
present in tree
if (lt == null && rt == null)
return null;
//If node
doesn't contain left node
else if (lt == null)
{
p = rt;
return p;
}
//If node
doesn't contain right node
else if (rt == null)
{
p = lt;
return p;
}
//If node
contains both the children
else
{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
//If desired value is less than
current node value then go left
if (k <
root.getData())
{
n = delete(root.getLeft(), k);
root.setLeft(n);
}
//If desired value is greater than
current node value then go right
else
{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
}
public class BSTree
{
public static void main(String args[])
{
//Creating object to Random()
class
Random r=new
Random();
//Creating object to BST
class
BST bst = new BST();
//Generating 20 random
numbers
for(int
i=0;i<20;)
{
int
value=r.nextInt(100);
if(value!=0)
{
bst.add(value);
i++;
}
}
System.out.println("\nPrefix order:
");bst.prefixOrder();
System.out.println("\nInfix order:
");bst.infixOrder();
System.out.println("\nPostfix
order: ");bst.postfixOrder();
Scanner sc=new
Scanner(System.in);
System.out.print("\nEnter deleting
node value: ");
int deleteValue=sc.nextInt();
bst.delete(deleteValue);
}
}
Output Screenshot:
Write a Java program named BSTree.java that will: 1) Generate 20 random integer numbers ranging from...
Write a Java program that creates and manipulates a directory of names, telephone numbers. The following information will be stored for each person in the directory: - Name (Last, First) - Home telephone number You should keep the entire collection ordered by key value (the combination of last and first names). Your program should be able to perform the following basic functions: - Search and display the contents of a particular entry - Display the entire directory - Delete an...
Write a Java program that will create a random list (array) randomize a search item to be found in the list sequentially search the array for that item. You must code the search and not use a search function. Display each comparison in the array; the element contents and the index. display whether the item was found or not. Now take that code and alter it to have two lists. Both lists randomize between 1 and 50. While traversing one list,...
Write a Java program with a single-dimension array that holds 11 integer numbers and sort the array using a bubble sort. Next, identify the median value of the 11 integers. Here are the steps your program must accomplish. algorithm (either flowchart or pseudocode) that you will use to write the program Step 1. Create an Place the algorithm in a Word document. 6. Ste the Step 2. Code the program in Eclipse and ensure the following steps are accomplished. 1....
C++
C++
Write a program to input eight integer numbers into an array named grade. As each number is input, add the number into a total. After all numbers are input, display the numbers and their average. (You can use cin to take number or use rand() to assign random numbers to the array.)
1. Write a C code that do the following: Generate array of random integer numbers of size 25 Fill the array with random integers ranging from [1-100] Find the maximum number of the array and its location Find the minimum number of the array and its location Search for a number in the array Print the array Flip the array Sort this array Quit the program when the user choose to exit
JAVA CODE Write a JAVA program to do the following. Input an integer x. (Should work with “big” numbers.) Create a completely-skewed BST S containing 1, 2, . . . , x. Create a BST R containing x integers without repetitions gen- erated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced. Measure the...
Write Java program to compare time consumed by linear search and binary search to search for non-exit element in arrays of length 1000, 100000,500000,1000000. Hints: - Use Random class, method nextInt(a.length) to generate random numbers. - Select an element that is greater than a.length. - Use Arrays.sort(a) to sort the array before using binarySearch.
In java, write a program that gets 10 integer numbers from the user using user input, and then calculates and display the sum of the numbers that have been read. Program Requirements: Write the program in three versions with three loops. Put all three loops in the main method of your source code. version1: use a while loop. version2: use a do-while loop. version 3: use a for loop. For each version, use a loop to input 10 int numbers from the user...
You are to write a program name expressionTree.java that evaluates an infix expression entered by the user. The expression may contain the following tokens: (1) Integer constants (a series of decimal digits). (2) One alphabetic character - "x" (representing a value to be supplied later). (3) Binary operators (+, -, *, / and % (modulo)). (4) Parentheses You will parse the input expression creating an expression tree with the tokens, then use the postOrder tree traversal algorithm to extract...
c# prograaming language
1. write a program that generates 10,000 random integers in the
range of 0-9 and them in binary search tree.
2. use any sort algorithm (insertion, bubble, quick...) to
display a list of each of the integers and how many times they
appear.
3. at last, add ruction to the BinarySearchTree class that count
the number of edges in a tree.
Write a program that generates 10,000 random integers in the range of 0-9 and store them...