Breadth-First Search/Level order Traversal in a Binary Tree

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package levelordertraversalbfs;

/* Write a program for Level order traversal in Binary tree

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Here we are using Linked List queue to Store tree node for Level order traversing

*/

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class LLNode
{
    LLNode link;
    Node data;
   
    public LLNode()
    {
        link = null;
        data = null;
    }
    public LLNode(Node data , LLNode n)
    {
        this.data = data;
        link = n;
    }

    public LLNode getLink() {
        return link;
    }

    public void setLink(LLNode link) {
        this.link = link;
    }

    public Node getData() {
        return data;
    }

    public void setData(Node data) {
        this.data = data;
    }
   
}

class LL_Queue
{
    LLNode front , rear;
   
    int size;
   
    public LL_Queue()
    {
        front =null;
        rear =null;
        size = 0;
    }
    public int getSize()
    {
        return size;
    }
    public boolean isEmpty()
    {
        return front==null;
    }
   
    public void enqueue(Node data)
    {
        LLNode nptr = new LLNode(data,null);
       
        if(front==null)
        {
            front = nptr;
            rear = nptr;
           
        }
        else
        {
            rear.setLink(nptr);
            rear = nptr;
           
        }
        size++;
       
    }
    public Node dequeue()
    {
        if(isEmpty())
        {
         return null;
        }
        else
        {
            Node d = front.getData();
            front = front.getLink();
            return d;
        }
       
    }
}

class Node
{
    Node Left , Right;
    int data;
   
    public Node()
    {
        Left = null;
        Right = null;
        data = 0;
    }
    public Node(int d)
    {
        Left = null;
        Right = null;
        data = d;
    }

    public Node getLeft() {
        return Left;
    }

    public void setLeft(Node Left) {
        this.Left = Left;
    }

    public Node getRight() {
        return Right;
    }

    public void setRight(Node Right) {
        this.Right = Right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
   
}

class Binary_tree
{
    Node root;
   
    public Binary_tree()
    {
        root = null;
    }
    public boolean isEmpty()
    {
        return root ==null;
    }
    public void insert(int data)
    {
        root = insert_tree(root,data);
    }
    public Node insert_tree(Node node, int data)
    {
        if(node==null)
        {
            node  = new Node(data);
        }
        else
        {
            if(node.getLeft()==null)
            {
                node.Left = insert_tree(node.Left,data);
            }
            else
            {
                node.Right = insert_tree(node.Right,data);
            }
        }
        return node;
    }
   
    public void Level_order()
    {
        Level_order_traversal(root);
    }
    public void Level_order_traversal(Node root)
    {
        Node temproot;
        LL_Queue lq = new LL_Queue();
        if(root==null)
        {
            System.out.print("No data");
        }
        else
        {
        lq.enqueue(root);
        while(!lq.isEmpty())
        {
            temproot = lq.dequeue();
            System.out.print("-->"+temproot.getData());
            if(temproot.getLeft()!=null)
            {
                lq.enqueue(temproot.getLeft());
            }
            if(temproot.getRight()!=null)
            {
                lq.enqueue(temproot.getRight());
            }
        }
        }
    }
   
}



public class LevelOrderTraversalBFS {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
       
        Binary_tree bt = new Binary_tree();
       
        char ch;
        Scanner sc = new Scanner(System.in);
        do
        {
     
        System.out.println("enter data");
       
        int data = sc.nextInt();
       
        bt.insert(data);
        System.out.println("enter y to add more values to binary tree");
       
        ch = sc.next().charAt(0);
        }while(ch=='y'||ch=='Y');
        System.out.println();
        System.out.print("Level order traversal :->");
        bt.Level_order();
    }
   
}

Linked List Queue Implementation

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.

Write a Program for Linked List queue Implementation

 */
package linkedlistqueue;

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class Node
{
    Node link;
    int data;
   
    public  Node()
    {
        link = null;
        data = 0;
    }
    public Node(int data , Node n)
    {
        this.data = data;
        link = n;
    }

    public Node getLink() {
        return link;
    }

    public void setLink(Node link) {
        this.link = link;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
   
}

class LL_queue
{
    Node front, rear;
    int size;
   
    public LL_queue()
    {
        front = rear = null;
        size = 0;
    }
    public int getSize()
    {
        return size;
    }
    public boolean isEmpty()
    {
        return front==null;
    }
    public void enqueue(int data)
    {
        Node nptr = new Node(data , null);
       
        if(front==null)
        {
            front = rear = nptr;
        }
        else
        {
            rear.setLink(nptr);
            rear = nptr;
        }
    }
   
    public void dequeue()
    {
        if(isEmpty())
        {
            System.out.println("No data present");
        }
        else
        {
            int data = front.getData();
            System.out.println("Dequeued data is :"+data);
            front  = front.getLink();
        }
    }
   
    public void display()
    {
        Node current = front;
        while(current.getLink()!=null)
        {
            System.out.println("->"+current.getData());
            current = current.getLink();
        }
        System.out.println("->"+current.getData());
    }
   
}



public class LinkedListQueue {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        char choice;
        LL_queue lq = new LL_queue();
       
        do
        {
        System.out.println("Press 1 for enqueue");
        System.out.println("Press 2 for dequeue");
        System.out.println("Press 3 for display");
        int option = sc.nextInt();
        switch(option)
        {
            case 1:
                do
                {
                    System.out.println("Insert data:->");
                int data = sc.nextInt();
                lq.enqueue(data);
                System.out.println("If you want to insert more data press Y");
                choice = sc.next().charAt(0);
                }while(choice=='Y'||choice=='y');
                break;
                case 2:
                do
                {
               
                lq.dequeue();
                System.out.println("If you want to delete more data press Y");
                choice = sc.next().charAt(0);
                }while(choice=='Y'||choice=='y');
                break;
                case 3:
                lq.display();
                break;
                default:
                System.out.println(" no valid option -- exit");
                break;
       
           
        }
        System.out.println("Do you want to go to main menu");
        choice = sc.next().charAt(0);
        }while(choice=='Y'||choice=='y');
       
       
        // TODO code application logic here
    }
   
}

Dynamic Circular Array Queue

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

 /* Write a Program for dynamic circular array queue */
package dynamic_array_queue;

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class dynamic_circular_queue
{
    int queue[];
    int size ;
    int front;
    int length;
    int rear;
   
    public dynamic_circular_queue(int size)
    {
        this.size = size;
        queue = new int[size];
        front = rear = -1;
        length =0;
    }
   
    public boolean isEmpty()
    {
        return front==-1;
    }
   
    public boolean isFull()
    {
        return (rear+1)%size==front;
    }
   
    public int getsize()
    {
        return length;
    }
   
    public void resize_array()
    {
        int old_array[];
        int oldsize = size;
        size = 2*size;
        old_array = queue;
        queue = new int[size];
       
        for(int i=0;i<old_array.length;i++)
        {
            queue[i] = old_array[i];
        }
       
        if(rear<front)
        {
            for(int i =0;i<front;i++)
            {
                queue[i+oldsize] = this.queue[i];
            }
            rear = rear+oldsize;
        }
    }
    public void enqueue(int data)
    {
        if(isFull())
        {
            resize_array();
            rear = (rear+1)%size;
            queue[rear] = data;
        }
        else
        {
            if(front==-1)
            {
                front=0;
                rear=0;
                queue[rear]=data;
            }
            else
            {
                rear = (rear+1)%size;
                queue[rear] = data;
               
                System.out.println(data);
            }
            length++;
        }
    }
   
    public void dequeue()
    {
        if(isEmpty())
        {
            System.out.println("Queue is empty");
        }
        else
        {
            int data = queue[front];
            System.out.println("Dequeued data--->" + data);
            length--;
           
            if(front==rear)
            {
                front =-1;
                rear = -1;
            }
            else
            {
                front = (front+1)%size;
            }
        }
    }
    public void display()
    {
        char choice;
        Scanner sc = new Scanner(System.in);
       
        char ch;
       
        do
        {
        System.out.println("press 1 to enqueue");
        System.out.println("press 2 to dequeue");
        System.out.println("press 3 to see all inserted data");
        int c = sc.nextInt();
        switch(c)
                {
        case 1:
        do
        {
            System.out.print("Insert data");
            int data = sc.nextInt();
            enqueue(data);
            System.out.print("Do you want to insert more data");
          choice = sc.next().charAt(0);
        }while(choice =='Y'||choice=='y');
        break;
        case 2:
        do
        {
            dequeue();
            System.out.print("Do you want to delete more data");
          choice = sc.next().charAt(0);
        }while(choice =='Y'||choice=='y');
        break;
        case 3:
            if(front>=0)
            {
               
        for(int i=front;i<queue.length && front!=-1;i++)
        {
            System.out.println("-->"+queue[i]);
        }
            }
           if(front>=0&&rear<=front)
            {
       for(int i=0;i<=rear;i++)
        {
            System.out.println("-->"+queue[i]);
        }
               
                }
           
        break;
        default:
        System.out.print("invalid input exit");
            break;
           
                }
        System.out.print("Do you want to go back to menu press y");
         ch = sc.next().charAt(0);
        }while(ch=='Y'||ch=='y');
    }
   
}

public class Dynamic_array_queue {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
         System.out.print("Enter the  size of queue");
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        dynamic_circular_queue aq = new dynamic_circular_queue(size);
        aq.display();
    }
   
}

Circular Array Queue

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* Write a program for circular array queue */

package circular_array_queue;

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class circular_queue
{
    int queue[];
    int size;
    int front;
    int rear;
    int length;
   
    public circular_queue(int size)
    {
        this.size = size;
        front = -1;
        rear = -1;
        length =0;
        queue = new int[size];
    }
   
    public boolean isEmpty()
    {
        return front==-1;
    }
   
    public boolean isFull()
    {
        return (rear+1)%size==front;
    }
    public void enqueue(int data)
    {
        if(isFull())
        {
            System.out.println("Buddy: you cannot insert mode data");
        }
        else
        {
            if(front==-1)
            {
                front =0;
                rear=0;
                queue[rear] = data;
            }
            else
            {
                rear = (rear+1)%size;
                queue[rear] = data;
            }
        }
         System.out.println("front value"+front+":rear value :"+rear);
        length++;
    }
   
    public int getSize()
    {
        return length;
    }
   
    public void dequeue()
    {
        if(isEmpty())
        {
            System.out.println("Queue is empty");
        }
        else
        {
            int data = queue[front];
            length--;
            System.out.println("Dequeued data--->" + data);
           
            if(front==rear)
            {
                front =-1;
                rear =-1;
            }
            else
            {
                front = (front+1)%size;
            }
        }
       
    }
    public void display()
    {
        char choice;
        Scanner sc = new Scanner(System.in);
       
        char ch;
       
        do
        {
        System.out.println("press 1 to enqueue");
        System.out.println("press 2 to dequeue");
        System.out.println("press 3 to see all inserted data");
        int c = sc.nextInt();
        switch(c)
                {
        case 1:
        do
        {
            System.out.print("Insert data");
            int data = sc.nextInt();
            enqueue(data);
            System.out.print("Do you want to insert more data");
          choice = sc.next().charAt(0);
        }while(choice =='Y'||choice=='y');
        break;
        case 2:
        do
        {
            dequeue();
            System.out.print("Do you want to delete more data");
          choice = sc.next().charAt(0);
        }while(choice =='Y'||choice=='y');
        break;
        case 3:
            if(front>=0)
            {
               
        for(int i=front;i<size && front!=-1;i++)
        {
            System.out.println("-->"+queue[i]);
        }
            }
           if(front>=0&&rear<=front)
            {
       for(int i=0;i<=rear;i++)
        {
            System.out.println("-->"+queue[i]);
        }
               
                }
           
        break;
        default:
        System.out.print("invalid input exit");
            break;
           
                }
        System.out.print("Do you want to go back to menu press y");
         ch = sc.next().charAt(0);
        }while(ch=='Y'||ch=='y');
    }
   
   
}
public class Circular_array_queue {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        System.out.print("Enter the  size of queue");
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        circular_queue aq = new circular_queue(size);
        aq.display();
        // TODO code application logic here
    }
   
}

Basic Array Queue

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

 /*Write a Program for Basic Array queue Implementation*/

package basic_queue_implementation;

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */


class array_queue
{
    int size;
    int queue[];
    int front;
    int rear;
    int length;
    public array_queue(int size)
    {
        this.size = size;
        queue = new int[size];
        front = -1;
        rear = -1;
        length = -1;
    }
    public boolean isEmpty()
    {
        return front==-1;
    }
    public boolean isFull()
    {
        return front==0 && rear==size-1;
    }
    public int getSize()
    {
        return length;
    }
    public void enqueue(int data)
    {
        if(isFull())
        {
            System.out.println("queue is full: no space to enter");
        }
        else
        {
            if(front==-1)
            {
                front =0;
                rear =0;
                queue[rear] = data;
            }
            else
            {
                queue[++rear] = data;              
            }
            length++;
        }
       
    }
    public void dequeue()
    {
        int data;
        if(isEmpty())
        {
            System.out.println("No more Items to remove");          
        }
        else
        {
           data  = queue[front];
            length--;
            if(front==rear)
            {
                front =-1;
                rear=-1;
            }
            else
            {
                front++;
            }
            System.out.print("Element which has been removed is :->" + data);
        }
       
    }
    public void display()
    {
        char choice;
        Scanner sc = new Scanner(System.in);
       
        char ch;
       
        do
        {
        System.out.println("press 1 to enqueue");
        System.out.println("press 2 to dequeue");
        System.out.println("press 3 to see all inserted data");
        int c = sc.nextInt();
        switch(c)
                {
        case 1:
        do
        {
            System.out.print("Insert data");
            int data = sc.nextInt();
            enqueue(data);
            System.out.print("Do you want to insert more data");
          choice = sc.next().charAt(0);
        }while(choice =='Y'||choice=='y');
        break;
        case 2:
        do
        {
            dequeue();
            System.out.print("Do you want to delete more data");
          choice = sc.next().charAt(0);
        }while(choice =='Y'||choice=='y');
        break;
        case 3:
        for(int i=front;i<=rear && front!=-1;i++)
        {
            System.out.println("-->"+queue[i]);
        }
        break;
        default:
        System.out.print("invalid input exit");
            break;
           
                }
        System.out.print("Do you want to go back to menu press y");
         ch = sc.next().charAt(0);
        }while(ch=='Y'||ch=='y');
    }
   
}



public class Basic_queue_implementation {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        System.out.print("Enter the  size of queue");
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        array_queue aq = new array_queue(size);
        aq.display();
    }
   
}