Created
April 10, 2014 17:35
-
-
Save jayeshsolanki93/10405053 to your computer and use it in GitHub Desktop.
Binary Search Tree in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.BufferedReader; | |
import java.io.IOException; | |
import java.io.InputStreamReader; | |
import java.util.ArrayDeque; | |
class IntBSTNode { | |
protected int key; | |
protected IntBSTNode left, right; | |
public IntBSTNode() { | |
left = right = null; | |
} | |
public IntBSTNode(int el) { | |
this(el, null, null); | |
} | |
public IntBSTNode(int el, IntBSTNode lt, IntBSTNode rt) { | |
key = el; | |
left = lt; | |
right = rt; | |
} | |
} | |
class IntBST { | |
protected IntBSTNode root; | |
public IntBST() { | |
root = null; | |
} | |
protected void visit(IntBSTNode p) { | |
System.out.print(p.key + " "); | |
} | |
public IntBSTNode search(int el) { | |
return search(root, el); | |
} | |
public IntBSTNode search(IntBSTNode p, int el) { | |
while (p != null) { | |
if (el == p.key) | |
return p; | |
else if (el < p.key) | |
p = p.left; | |
else | |
p = p.right; | |
} | |
return null; | |
} | |
public void breadthFirst() { | |
IntBSTNode p = root; | |
ArrayDeque<Object> q = new ArrayDeque<Object>(); | |
if (p != null) { | |
q.add(p); | |
while (!q.isEmpty()) { | |
p = (IntBSTNode) q.remove(); | |
visit(p); | |
if (p.left != null) | |
q.add(p.left); | |
if (p.right != null) | |
q.add(p.right); | |
} | |
} | |
} | |
public void preorder() { | |
preorder(root); | |
} | |
protected void preorder(IntBSTNode p) { | |
if (p != null) { | |
visit(p); | |
preorder(p.left); | |
preorder(p.right); | |
} | |
} | |
public void inorder() { | |
inorder(root); | |
} | |
protected void inorder(IntBSTNode p) { | |
if (p != null) { | |
inorder(p.left); | |
visit(p); | |
inorder(p.right); | |
} | |
} | |
public void postorder() { | |
postorder(root); | |
} | |
protected void postorder(IntBSTNode p) { | |
if (p != null) { | |
postorder(p.left); | |
postorder(p.right); | |
visit(p); | |
} | |
} | |
public void insert(int el) { | |
IntBSTNode p = root, prev = null; | |
while (p != null) { | |
prev = p; | |
if (p.key < el) | |
p = p.right; | |
else | |
p = p.left; | |
} | |
if (root == null) | |
root = new IntBSTNode(el); | |
else if (prev.key < el) | |
prev.right = new IntBSTNode(el); | |
else | |
prev.left = new IntBSTNode(el); | |
} | |
public void deleteByMerging(int el) { | |
IntBSTNode tmp, node, p = root, prev = null; | |
while (p != null && p.key != el) { | |
prev = p; | |
if (p.key < el) | |
p = p.right; | |
else | |
p = p.left; | |
} | |
node = p; | |
if (p != null && p.key == el) { | |
if (node.right == null) | |
node = node.left; | |
else if (node.left == null) | |
node = node.right; | |
else { | |
tmp = node.left; | |
while (tmp.right != null) | |
tmp = tmp.right; | |
tmp.right = node.right; | |
node = node.left; | |
} | |
if (p == root) | |
root = node; | |
else if (prev.left == p) | |
prev.left = node; | |
else | |
prev.right = node; | |
} else if (root != null) | |
System.out.println("key " + el + " is not in the tree"); | |
else | |
System.out.println("the tree is empty"); | |
} | |
} | |
public class BST { | |
public static void main(String args[]) throws IOException { | |
IntBST tree = new IntBST(); | |
int choice; | |
int el; | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
do { | |
System.out.println("Enter your choice:"); | |
System.out | |
.println("1.INSERT \t2.DELETE \t3.TRAVERSE \t4.SEARCH \t5.EXIT"); | |
choice = Integer.parseInt(br.readLine()); | |
switch (choice) { | |
case 1: | |
System.out.println("\t\tEnter a number:"); | |
System.out.print("\t\t"); | |
el = Integer.parseInt(br.readLine()); | |
tree.insert(el); | |
break; | |
case 2: | |
System.out.println("\t\tEnter a number:"); | |
System.out.print("\t\t"); | |
el = Integer.parseInt(br.readLine()); | |
tree.deleteByMerging(el); | |
break; | |
case 3: | |
System.out.println("\t\tEnter your choice:"); | |
System.out | |
.println("\t\t1.BREADTH FIRST TRAVERSAL \t2.DEPTH FIRST TRAVERSAL"); | |
System.out.print("\t\t"); | |
choice = Integer.parseInt(br.readLine()); | |
switch (choice) { | |
case 1: | |
tree.breadthFirst(); | |
break; | |
case 2: | |
System.out.println("\t\tEnter your choice:"); | |
System.out | |
.println("\t\t1.PREORDER\t 2.INORDER\t 3.POSTORDER"); | |
System.out.print("\t\t"); | |
choice = Integer.parseInt(br.readLine()); | |
switch (choice) { | |
case 1: | |
tree.preorder(); | |
break; | |
case 2: | |
tree.inorder(); | |
break; | |
case 3: | |
tree.postorder(); | |
break; | |
default: | |
System.out | |
.println("\t\tInvalid argument,return to main menu"); | |
break; | |
} | |
break; | |
default: | |
System.out | |
.println("\t\tInvalid argument,return to main menu"); | |
break; | |
} | |
break; | |
case 4: | |
System.out.println("\t\tEnter a number:"); | |
System.out.print("\t\t"); | |
el = Integer.parseInt(br.readLine()); | |
if (tree.search(el) != null) | |
System.out.println("\t\tElement is present"); | |
else | |
System.out.println("\t\tElement is not present"); | |
break; | |
case 5: | |
break; | |
} | |
} while (choice != 5); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment