Create a Node Using java for binary search tree.we will use this node in creating node in binary search tree .Traversing Inorder ,preorder and postorder traversal. It is also used in searching a node or deleting a node.
package com.java.bstds;
public class Node {
int data;
Node left,right;
public Node(int data){
this.data=data;
}
public String toString(){
return hashCode()+"";
}
}
To Implement the logic I am writing following code inside main method so that we can used all services.
package com.java.bstds;
import java.util.Scanner;
public class BST {
public static Node root;
// For Searching element we used below reference
public static Node avail, parent;
public static void main(String[] args) {
System.out.println("Jai shree Ganesh !!!");
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println();
System.out.println(
"1. Create \t2. Inorder Traversal \t3. Preorder Travelsal \t4. Postorder Traversal \t5. Search Element \t6. Delete");
int operation = sc.nextInt();
switch (operation) {
case 1:
System.out.println("How many number of node you want to create");
int noOfNode = sc.nextInt();
for (int i = 0; i < noOfNode; i++) {
System.out.println("Enter the node value to create");
int data = sc.nextInt();
create(data);
}
break;
case 2:
inOrderTraversal();
break;
case 3:
preOrderTraversal();
break;
case 4:
postOrderTraversal();
break;
case 5:
System.out.println("Enter element which you want to search");
int ele = sc.nextInt();
Node avl = search(ele);
if (avl != null) {
System.out.println("Element is " + avail.data);
if (parent != null) {
System.out.println("which parent is " + parent.data);
}
} else {
System.out.println("Element Not Found");
}
break;
case 6:
System.out.println("Enter node value which you want to delete");
int value = sc.nextInt();
delete(value);
break;
default:
System.out.println("Not found any index");
break;
}
}
}
}
To create a node and add element greater than root node is right side of the root and element less than the root will store inside left side of the root.To implement that logic we have gone through below case.
public static void create(int data) {
Node temp = new Node(data);
if (root == null) {
root = temp;
return;
} else {
Node copyRoot = root;
Node newNode = null;
while (copyRoot != null) {
newNode = copyRoot;
if (copyRoot.data > data) {
copyRoot = copyRoot.left;
} else if (copyRoot.data < data) {
copyRoot = copyRoot.right;
} else {
copyRoot = null;
}
}
if (newNode.data > data) {
newNode.left = temp;
} else if (newNode.data < data) {
newNode.right = temp;
} else if (newNode.data == data) {
temp = null;
}
}
}
To implement the Traversal in tree we have three ways to traverse the tree .
1. Inorder Traversal(LNR)
2. Preorder Traversal(NLR)
3. Postorder Traversal(LRN)
So let us see one by one.
1. Inorder traversal : First it will traverse left node then root and then right node.This rule is applicable for all node.
public static void inOrderTraversal() {
if (root == null) {
System.out.println("Empty BST ");
return;
} else {
Node copyRoot = root;
Node[] stack = new Node[20];
int top = -1;
try {
while (true) {
while (copyRoot != null) {
stack[++top] = copyRoot;
copyRoot = copyRoot.left;
}
copyRoot = stack[top--];
if (copyRoot.right != null) {
System.out.print(" " + copyRoot.data + " ");
copyRoot = copyRoot.right;
} else {
System.out.print(" " + copyRoot.data + " ");
copyRoot = null;
}
}
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
2. Preorder Traversal(NLR) : first it will traverse root then left and then right and it is applicable of all node.
public static void preOrderTraversal() {
if (root == null) {
System.out.println("Empty BST");
return;
} else {
Node copyRoot = root;
Node[] stack = new Node[20];
int top = -1;
try {
while (true) {
while (copyRoot != null) {
System.out.print(copyRoot.data + " ");
stack[++top] = copyRoot;
copyRoot = copyRoot.left;
}
copyRoot = stack[top--];
if (copyRoot.right != null) {
copyRoot = copyRoot.right;
} else {
copyRoot = null;
}
}
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
3.Postorder Traversal (LRN):- In this traversal we have first gone through left node the right node and then root node. and it is applicable for all node. Root node will be printed only when its is traverse at 3rd times.
public static void postOrderTraversal() {
if (root == null) {
System.out.println("Empty BST");
return;
} else {
Node copyRoot = root;
Node[] stack = new Node[20];
int top = -1;
try {
while (true) {
while (copyRoot != null) {
if (copyRoot.right != null) {
stack[++top] = copyRoot.right;
}
stack[++top] = copyRoot;
copyRoot = copyRoot.left;
}
copyRoot = stack[top--];
if (top != -1 && copyRoot.right != null && stack[top] == copyRoot.right) {
stack[top] = copyRoot;
copyRoot = copyRoot.right;
} else {
System.out.print(copyRoot.data + " ");
copyRoot = null;
}
}
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
To search a particular element from Binary search tree we are using below method.to search a element basically we want to find the node of element and its parent of the element. this search will also used in deleting a node from BST.
public static Node search(int data) {
avail = null;
if (root == null) {
System.out.println("Empty BST");
return null;
} else {
if (root.data == data) {
avail = root;
parent = null;
return avail;
}
Node copyRoot = root, findTree = null;
if (root.data > data) {
findTree = root.left;
} else {
findTree = root.right;
}
while (findTree != null) {
if (findTree.data == data) {
avail = findTree;
parent = copyRoot;
break;
}
copyRoot = findTree;
if (findTree.data > data) {
findTree = findTree.left;
} else {
findTree = findTree.right;
}
}
}
return avail;
}
To delete a node from BST , we have three way to delete a node.
1. If node have not left and right sub tree.(nought method)
2. If node have only left or right sub tree .(crooked method)
3. if node have both left and right sub tree.(hedge method)
public static void delete(int data) {
if (root == null) {
System.out.println("Empty BST");
return;
}
Node avail = search(data);
if (root == avail && root.left == null && root.right == null) {
root = null;
}
if (avail.left == null && avail.right == null) {
nought(avail);
}
if (avail.left != null && avail.right == null) {
crooked(avail);
}
if (avail.right != null && avail.left == null) {
crooked(avail);
}
if(avail.left!=null && avail.right!=null){
hedge(avail);
}
}
1.) To delete a node which haven't left and right node we called nought method.
public static void nought(Node avail) {
// if(parent==null) or if(root==avail)
if (root == avail) {
root = null;
return;
}
if (parent.left == avail) {
parent.left = null;
} else {
parent.right = null;
}
}
2.) If node have only left or right subtree then we will call crooked method.
public static void crooked(Node avail) {
Node copy = null;
if (avail.left != null) {
copy = avail.left;
} else {
copy = avail.right;
}
if (root == avail) {
root=copy;
return;
}
if(parent.left==avail){
parent.left=copy;
}else{
parent.right=copy;
}
}
3.) If node have both left and right tree then we will call hedge method.
public static void hedge(Node avail){
Node copy=avail.right;
Node q=null;
while(copy!=null){
q=copy;
copy=copy.left;
}
Node avail1=avail,parent1=parent;
Node avail2=search(q.data);
if(avail2.right!=null && avail2.left==null){
crooked(avail2);
}else{
nought(avail2);
}
if(parent1==null){
avail2.right=avail1.right;
avail2.left=avail1.left;
root=avail2;
}else{
if(parent1.right==avail1){
parent1.right=avail2;
}else{
parent1.left=avail2;
}
avail2.right=avail1.right;
avail2.left=avail1.left;
}
}
No comments:
Post a Comment