Binary search trees (BST), sometimes called ordered or sorted binary trees, are a class of data structures used to implement lookup tables and dynamic sets. They store data items, known as keys, and allow fast insertion and deletion of such keys, as well as checking whether a key is present in a tree.
The common properties of binary search trees are as follows:
- One node is designated the root of the tree.
- Each internal node contains a key and has two subtrees.
- The leaves (final nodes) of the tree contain no key. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.
- Each subtree is itself a binary search tree.
- The left subtree of a node contains only nodes with keys strictly less than the node’s key.
- The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
import java.io.*;
class node {
int data;
node left, right;
public node(int x) {
data = x;
left = null;
right = null;
}
}
class BST {
node root;
public void insert(int x) {
if (root == null) {
node p = new node(x);
root = p;
} else
insertdata(root, x);
}
private void insertdata(node n, int x) {
if (n.data == x) {
System.out.println("Value already present");
return;
} else if (n.data > x) {
if (n.left == null) {
node p = new node(x);
n.left = p;
} else
insertdata(n.left, x);
} else if (n.data < x) {
if (n.right == null) {
node p = new node(x);
n.right = p;
} else
insertdata(n.right, x);
}
}
public void printInC() {
if (root == null) {
System.out.println("Tree empty");
}
printIn(root);
}
private void printIn(node n) {
if (n != null) {
printIn(n.left);
System.out.print(" " + n.data);
printIn(n.right);
}
}
public void printPreC() {
if (root == null) {
System.out.print("Tree empty");
}
printPre(root);
}
private void printPre(node n) {
if (n != null) {
System.out.print(" " + n.data);
printPre(n.left);
printPre(n.right);
}
}
public void printPostC() {
if (root == null) {
System.out.print("Tree empty");
}
printPost(root);
}
private void printPost(node n) {
if (n != null) {
printPost(n.left);
printPost(n.right);
System.out.print(" " + n.data);
}
}
public void search(int x) {
searchnew(root, x);
}
private void searchnew(node n, int x) {
if (n == null) {
System.out.println("Data Not Found");
return;
}
if (n.data == x)
System.out.println("Data Found");
else if (n.data > x)
searchnew(n.left, x);
else if (n.data < x)
searchnew(n.right, x);
}
}
class Bstdemo {
public static void main(String ankur[]) throws IOException {
BST b = new BST();
BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
int ch;
do {
System.out.println();
System.out.println("##MENU##");
System.out.println("1.Insert");
System.out.println("2.Display Tree Inorder");
System.out.println("3.Display Tree Preoder");
System.out.println("4.Display tree Postorder");
System.out.println("5.Search");
System.out.println("6.Exit");
System.out.println("Enter Option");
ch = Integer.parseInt(obj.readLine());
switch (ch) {
case 1:
{
System.out.println("Enter Element");
int x = Integer.parseInt(obj.readLine());
b.insert(x);
break;
}
case 2:
b.printInC();
break;
case 3:
b.printPreC();
break;
case 4:
b.printPostC();
break;
case 5:
{
System.out.println("Enter Element to search");
int s = Integer.parseInt(obj.readLine());
b.search(s);
break;
}
}
} while (ch != 6);
}
}
/*
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
1
Enter Element
17
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
1
Enter Element
13
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
1
Enter Element
21
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
1
Enter Element
10
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
1
Enter Element
15
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
1
Enter Element
24
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
2
10 13 15 17 21 24
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
3
17 13 10 15 21 24
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
4
10 15 13 24 21 17
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
5
Enter Element to search
10
Data Found
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
5
Enter Element to search
13
Data Found
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
5
Enter Element to search
17
Data Found
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
5
Enter Element to search
26
Data not found
##MENU##
1.Insert
2.Display Tree Inorder
3.Display Tree Preoder
4.Display tree Postorder
5.Search
6.Exit
Enter Option
6
Process Exit...
*/