Java Binary Seach Tree program Write an interactive BST analyzer program. The it
ID: 3574506 • Letter: J
Question
Java Binary Seach Tree program
Write an interactive BST analyzer program. The items you store in the tree will be integers. You will create a binary search tree. Your program will visually display the top 5 levels of the tree and will have these menu options:
20
|
10-------------------------^----------------------- 50
| |
3-----------^----------- 17 42-----------^----------- 90
| | | |
----^---- 15----^---- 37----^---- 48 74----^----100
| | | | | | | |
. -^- . . -^- . -^- . -^- . -^- 45-^- 66-^- 79 -^-105
3, 10, 15, 17, 20, 37, 42, 43, 44, 45, 48, 50, 65, 66, 74, 79, 90, 100, 105, 110, 150,
Tree Height:7
Tree Root:20
Tree Count:21
(A)dd item (B)alance Tree (D)elete Item (F)ind item (I)nitialize Tree (N)ew Tree (Q)uit
Enter Choice:
(Notice the numbers 43, 44, 65, 110 and 150 are in the BST, but not able to display in the 5 levels of the visual tree because they are on deeper levels)
Additional Requirements:
The user can enter either uppercase of lower case commands. ‘B’ should behave the same as ‘b’
The (I)nitialize Tree command will fill the tree with 31 integers of your choice. The resulting tree will have a height of 5 and will be balanced.
Assume the root is on level zeroExample run:
|
. -------------------------^----------------------- .
| |
. -----------^----------- . . -----------^----------- .
| | | |
. ----^---- . . ----^---- . . ----^---- . . ----^---- .
| | | | | | | |
. -^- . . -^- . . -^- . . -^- . . -^- . . -^- . . -^- . . -^- .
Empty List
Tree Height:0
No Root: Tree is empty
Tree Count:0
(A)dd item (B)alance Tree (D)elete Item (F)ind item (I)nitialize Tree (N)ew Tree (Q)uit
Enter Choice:i
50
|
20-------------------------^-----------------------100
| |
15-----------^----------- 25 75-----------^-----------120
| | | |
5----^---- 18 23----^---- 34 60----^---- 94 110----^----150
| | | | | | | |
2-^- 12 16-^- 19 22-^- 24 30-^- 36 55-^- 65 80-^- 97 105-^-115 130-^-190
2, 5, 12, 15, 16, 18, 19, 20, 22, 23, 24, 25, 30, 34, 36, 50, 55, 60, 65, 75, 80, 94, 97, 100, 105, 110, 115, 120, 130, 150, 190,
Tree Height:5
Tree Root:50
Tree Count:31
(A)dd item (B)alance Tree (D)elete Item (F)ind item (I)nitialize Tree (N)ew Tree (Q)uit
Enter Choice:d
Enter integer to delete from tree:50
50 was deleted from tree
Explanation / Answer
import java.util.Scaner;
class BSTNode
{
BSTNode left, right;
int data;
/* Constructor */
public BSTNode()
{left = null;
data = 0;
}
/* Constructor */
public BSTNode(int n)
{
right = null;
left = null;
data = n;
}
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get right node */
public BSTNode getright()
{
return right;
}
public BSTNode getleft()
{
return left;
}
public void setData(int d)
{
Dta = d;
}
public int getData()
{
return dta;
}
}
class BST
{
private BSTNode rot;
public BST()
{
rot = null;
}
public boolean isEmpty()
{
return rot == null;
}
public void insert(int dta)
{
rot = insert(rot, dta);
}
private BSTNode insert(BSTNode node, int dta)
{
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;
}
public void delte(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sory "+ k +" is not present");
else
{
rot = delete(rot, k);
System.out.println(k+ " deltd from the tree");
}
}
private BSTNode delete(BSTNode rot, int k)
{
BSTNode p, p2, n;
if (rot.getData() == k)
{
BSTNode lt, rt;
lt = rot.getLeft();
rt = rot.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
P = rt;
return P;
}
else if (rt == null)
{
P = lt;
return P;
}
else
{
P2 = rt;
P = rt;
while (P.getLeft() != null)
P = P.getLeft();
P.setLeft(lt);
return p2;
}
}
if (k < rot.getData())
{
n = delete(rot.getrightt(), k);
rot.setrightt(n);
}
else
{
n = delete(rot.getleft(), k);
rot.setleftt(n);
}
return rot;
}
public int countNodes()
{
return countNodes(rot);
}
private int countNodes(BSTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getright());
l += countNodes(r.getleftt());
return l;
}
}
public boolean search(int val)
{
return search(rot, val);
}
private boolean search(BSTNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.getData();
if (val < rval)
r = r.getright();
else if (val > rval)
r = r.getleftt();
else
{
found = true;
break;
}
found = serch(r, val);
}
return found;
}
public void inorder()
{
inorder(rot);
}
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getrightt());
System.out.print(r.getData() +" ");
inorder(r.getleftt());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(rot);
}
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getrightt());
preorder(r.getleft());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(rot);
}
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getleft());
postorder(r.getright());
System.out.print(r.getData() +" ");
}
}
}
public class BinarySearchTreeAnalyzer
{
public static void main(String[] args)
{
Scaner scan = new Scaner(System.in);
BST bst = new BST();
System.out.println("Binary Search Tree analyzer ");
char ch;
do
{
System.out.println(" Binary Search Tree analyzer Operations ");
System.out.println("1. insert ");
System.out.println("2. delete");
System.out.println("3. count nodes");
System.out.println("4. search");
System.out.println("5. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("type integer element to insert");
bst.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to delete");
bst.delete( scan.nextInt() );
break;
case 3 :
System.out.println("Nodes = "+ bst.countNodes());
break;
case 4 :
System.out.println("type integer element to search");
System.out.println("Search result : "+ bst.search( scan.nextInt() ));
break;
case 5 :
System.out.println("Empty status = "+ bst.isEmpty());
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
bst.postorder();
System.out.print(" Pre order : ");
bst.preorder();
System.out.print(" In order : ");
bst.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Note:if any errors shown please post a coment
thank you!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.