Binary search traversal we can do with two ways.
1.) Breadth First Traversal(BFS) :- we use level order traversal for it.
2.) Depth Order Traversal(DFS) :- we can implement DFS with three ways.
- Preorder Traversal :- it will print as first ROOT Node, then LEFT, after that RIGHT(NLR).
- Inorder Traversal :- it will print as first LEFT tree, then Root node, after that RIGHT(LNR).
- Postorder Traversal :- it will print as first LEFT tree, then RIGHT tree, after that Root node(LRN).
package com.java.recursion;
public class Node {
int data;
Node left,right;
public Node(int data){
this.data=data;
left=right=null;
}
public String toString(){
return hashCode()+"";
}
}
Implementation class for BFS and DFS traversal using recursion.
package com.java.recursion;
import java.util.Scanner;
public class TraversalBST {
public static Node root;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("1. Create \t2. Preorder \t3. Inorder \t4. Postorder \t5. lebelorder");
int operation=sc.nextInt();
switch(operation){
case 1:
System.out.println("How many node you want to create");
int noOfNode=sc.nextInt();
for(int i=0;i<noOfNode;i++){
System.out.println("Enter node value");
int data=sc.nextInt();
create(data);
}
break;
case 2:
preOrder(root);
break;
case 3:
inOrder(root);
break;
case 4:
postOrder(root);
break;
case 5:
lebelOrder(root);
break;
}
}
}
private static void create(int data) {
Node temp=new Node(data);
if(root==null){
root=temp;
return;
}
Node copy=root;
Node CR=root;
while(copy!=null){
CR=copy;
if(copy.data>data){
copy=copy.left;
}else if(copy.data<data){
copy=copy.right;
}
}
if(CR.data>data){
CR.left=temp;
}else if(CR.data<data){
CR.right=temp;
}
}
private static void preOrder(Node root) {
if(root==null){
return;
}
System.out.print(root.data+" , ");
preOrder(root.left);
preOrder(root.right);
}
private static void inOrder(Node root) {
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.data+" , ");
inOrder(root.right);
}
private static void postOrder(Node root) {
if(root==null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+" , ");
}
private static void lebelOrder(Node root) {
// TODO Auto-generated method stub
int h=height(root);
System.out.println("Height is : "+h);
for(int i=1;i<=h;i++){
lebelOrderDisplay(root,i);
}
}
private static void lebelOrderDisplay(Node root, int level) {
if(root==null){
return;
}
if(level==1){
System.out.print(root.data+" , ");
}
if(level>=1){
lebelOrderDisplay(root.left,level-1);
lebelOrderDisplay(root.right,level-1);
}
}
private static int height(Node root){
if(root==null){
return 0;
}
int leftHeight=height(root.left);
int rightHeight=height(root.right);
if(leftHeight<rightHeight){
return leftHeight+1;
}else{
return rightHeight+1;
}
}
}
No comments:
Post a Comment