java binary tree program for inorder, preorder, postorder

import java.util.Queue;
import java.util.LinkedList;
public class TreeTraverse
{
private static class Node<T>
{
public Node<T> left;
public Node<T>right;
public T data;
public Node (T data)
{
this.data=data;
}
public Node <T>getleft()
{
return this.left;
}
public void setleft(Node <T>left)
{
this.left=left;
}
public Node<T>getright()
{
return this.right;
}
public void setright(Node<T>right)
{
this.right=right;
}
}
public static void preorder(Node<?>n)
{
if(n!=null)
{
System.out.println(n.data+"  ");
preorder(n.getleft());
preorder(n.getright());
}
}
public static void inorder(Node<?>n)
{
if(n!=null)
{
System.out.println(n.data+" ");
preorder(n.getleft());
preorder(n.getright());
}
}
public static void postorder(Node<?>n)
{
if(n!=null)
{
postorder(n.getleft());
postorder(n.getright());
System.out.println(n.data+" ");
}
}
public static void main(final String[]args)
{
Node<Integer>one=new Node<Integer>(1);
Node<Integer>two=new Node<Integer>(2);
Node<Integer>three=new Node<Integer>(3);
Node<Integer>four=new Node<Integer>(4);
Node<Integer>five=new Node<Integer>(5);
Node<Integer>six=new Node<Integer>(6);
Node<Integer>seven=new Node<Integer>(7);
Node<Integer>eight=new Node<Integer>(8);
Node<Integer>nine=new Node<Integer>(9);
one.setleft(two);
one.setright(three);
two.setleft(four);
two.setright(five);
three.setleft(six);
four.setleft(seven);
six.setleft(eight);
six.setright(nine);
System.out.println("PREORDER IS:");
preorder(one);
System.out.println();
System.out.println("INORDER IS:");
inorder(one);
System.out.println();
System.out.println("POSTORDER IS:");
postorder(one);
System.out.println();
}
}

LINKED LIST

import java.io.*;

import java.util.*;

public class LinkedListDemo {

    static public void main(String args[]) throws IOException {

        LinkedList<String> ll = new LinkedList<String>();

        ll.add("AMERICA");

        ll.add("INDIA");

        ll.add("JAPAN");

        System.out.println("LIST = " + ll);

         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String element;

        int position, choice = 0;

        while (choice < 4) {

            System.out.println("\n LinkedList operation: ");

            System.out.println("1. ADD an element: ");

            System.out.println("2. REMOVE an element: ");

            System.out.println("3. CHANGE an element: ");

            System.out.println("4. EXIT");

            System.out.println("Enter your choice: ");

            choice = Integer.parseInt(br.readLine());

            switch (choice) {

                case 1:

                    System.out.println("Enter the element: ");

                    element = br.readLine();

                    System.out.println("At what position: ");

                    position = Integer.parseInt(br.readLine());

                    ll.add(position - 1, element);

                    break;

                case 2:

                    System.out.println("At what position: ");

                    position = Integer.parseInt(br.readLine());

                    ll.remove(position - 1);

                    break;

                case 3:

                    System.out.println("Enter the position: ");

                    position = Integer.parseInt(br.readLine());

                    System.out.println("Enter the new Element: ");

                    element = br.readLine();

                    ll.set(position - 1, element);

                    break;

                default:

                    return;

            }

            System.out.println("List = ");

            Iterator it = ll.iterator();

            while (it.hasNext()) {

                System.out.println(it.next() + " ");

            }

        }

    }

}

Linked List: A data structure is said to linear if its elements from a sequence i.e., a list which displays the relationship of adjacency between the elements is said to be linear any other list is said to be non-linear.

Ex: week days – SUN, MON, TUE, WED, THU, FRI, SAT

Single Linked List: A single linked list or one-way list is a collection of data elements called nodes. Here each node is divided into two parts.

The first part contains the information of the elements. The second part contains the address of the next node in the list.

The first part is called data field or information field and the second part is called the Linked field or next address field.

                                The schematic diagram of a linked list is given below

    

QUEUE DATA STRUCTURE

QUEUE:

Queue is a linear list of elements in which insertion takes place at REAR end and deletions can takes place from FRONT end .QUEUE is also called as FIFO (FIRST IN FIRST OUT) Data Structure.

A common example:  QUEUE at Bank is the best example, where every person enters in to the QUEUE from rear end and after payment/deposit exits from the front end.

INSERTION operation: The insertion operation on the QUEUE is done from the rear end.

DELETION operation: The deletion operation is done from the front end.

Initially when the QUEUE is empty then, front=0, rear=0 and count=0.

When we insert elements in to the Queue then

               a[rear] = item;

                rear++;

                count++;

When we want to delete elements from the Queue then

        if(count != 0){  

          a[front];

           front++;

           count--;

          }

Different types of QUEUE’s are

1)      Linear Queue: Normal First In First Out QUEUE  is known as Linear Queue.

2)      Circular Queue: In this, we can use free space efficiently. In circular Queue the gap between rear and front is equal to two.

3)      Priority Queue: In this type elements are processed as per the priority, it doesn’t follow FIFO order.

4)      DE-Queue (Double Ended Queue): In this, we can insert and delete elements from the both ends known as doubly Ended Queue. It is categorized in to two types. They are

i)                    Input Restricted Queue: Append can be done from one side only and serving can be done from both sides.

ii)                   Output Restricted Queue:  Append can be done from the both sides and serving can be done from one side only.

QUEUE PROGRAM:

import java.io.DataInputStream;

class DemoQueue {

    DataInputStream dis = new DataInputStream(System.in);

    int a[];

    int i, front = 0, rear = 0, n, item, count = 0;

    void getData() {

        try {

            System.out.println("Enter the limit: ");

            n = Integer.parseInt(dis.readLine());

            a = new int[n];

        } catch (Exception e) {

            System.out.println(e.getMessage());

        }

    }

    void enQueue() {

        try {

            if (count < n) {

                System.out.println("Enter the element to be added: ");

                item = Integer.parseInt(dis.readLine());

                a[rear] = item;

                rear++;

                count++;

            } else {

                System.out.println("QUEUE IS FULL");

            }

        } catch (Exception e) {

            e.printStackTrace();

        }

    }

    void deQueue() {

       if(count != 0){

           System.out.println("The item selected is: " + a[front]);

           front++;

           count--;

       }else{

           System.out.println("QUEUE IS EMPTY");

           if(rear == n)

               rear = 0;

       }

    }

    void display() {

        int m = 0;

        if (count == 0) {

            System.out.println("QUEUE IS EMPTY");

        } else {

            for (i = front; m < count; i++, m++) {

                System.out.println(" " + a[i % n]);

            }

        }

    }

}

public class UsingQueue {

    static public void main(String args[]) {

        DataInputStream dis = new DataInputStream(System.in);

        int ch;

        DemoQueue obj = new DemoQueue();

        obj.getData();

        try {

            do {

                System.out.println("1.ENQUE" + "\n" + "2.DEQUEUE" + "\n" + "3.DISPLAY" + "\n" + "4.EXIT");

                System.out.println("Enter your choice");

                ch = Integer.parseInt(dis.readLine());

                switch (ch) {

                    case 1:

                        obj.enQueue();

                        break;

                    case 2:

                        obj.deQueue();

                        break;

                    case 3:

                        obj.display();

                    case 4:

                        break;

                    default:

                        System.out.println("invalid choice...");

                }

            } while (ch != 4);

        } catch (Exception e) {

            e.printStackTrace();

        }

    }

}

STACK

     A Stack is a linear list of elements in which insertion and deletions can takes place from only one end called top of the stack.

A common example of stack is a collection of trays on which the operations can be performed by inserting and deleting the new tray from top end only.

PUSH operation: The insertion operation on the stack is called PUSH operation.

POP operation: The deletion operation from the stack is called POP operation.

    The insertion and deletion can be done by only at the top of the stack.

Initially top =-1 , when the STACK is empty. And when we PUSH new elements into the STACK (12,13,14) then top=2.

When we pop two elements from the STACK, then top=0.

1) STACK OVERFLOW: It is the situation where, there is no place in the STACK to perform PUSH operation.

2) STACK UNDERFLOW: It is the situation where, the STACK is empty and we cannot POP elements from the STACK.

The Operations which can be performed on STACK are:

1) PUSH: Adding an element into the STACK

2) POP: Removing an element from the STACK

3) DISPLAY : Showing all elements which are present in the STACK

JAVA PROGRAM implementing STACK operations 

import java.util.Scanner;

class Stack {

int[] a;

int top;

public Stack(int n) {

a = new int[n];

top = -1;

}

public void push(int val) {

if (top == a.length - 1) {

System.out.println("Stack overflow...");

} else {

top++;

a[top] = val;

}

}

public void pop() {

if (top == -1) {

System.out.println("Stack underflow...");

} else {

System.out.println("Element popped" + a[top]);

top--;

}

}

public void display() {

if (top == -1) {

System.out.println("Stack empty...");

} else {

for (int i = top; i >= 0; i--) {

System.out.println("Stack element: " + a[i]);

}

}

}

}

public class UseStack {

static public void main(String args[]) {

Scanner sc = new Scanner(System.in);

Stack s;

int n;

System.out.println("Enter the size of the stack: ");

n = sc.nextInt();

s = new Stack(n);

int choice;

do {

System.out.println("1.PUSH" + "\n" + "2.POP" + "\n" + "3.DISPLAY" + "\n" + "0.EXIT");

System.out.println("Enter your choice");

choice = sc.nextInt();

switch (choice) {

case 1:

int value;

System.out.println("Enter element to push");

value = sc.nextInt();

s.push(value);

break;

case 2:

s.pop();

break;

case 3:

s.display();

case 0:

break;

default:

System.out.println("invalid choice...");

}

} while (choice != 0);

}

}

DATA STRUCTURES

             The word data is derived from Datum, which means fact. Hence data can be defined as the collection of raw facts. The difference between data and information is that information can be derived after processing the data. Thus we can define information as the processed data.

             To handle a collection of data items, it is better to select a structure and that structure can be called as Data Structure. It can be defined as “Collection of data elements organized in a specified manner and a set of functions to store, retrieve and manipulate the individual data elements”.

Various operations performed on the Data Structure:

• INSERTION: is a process of adding an element or a set of elements to the Data Structure.
• DELETION: is a process of removing the data elements from the given Data Structure.
• TRAVERSING: is a process of visiting each & every data element at least once.
• SORTING: is a process of arranging the given data elements in either ascending or descending order.
• SEARCHING: is a process of finding a given element in a given Data Structure.
• MERGING: operation combines two sorted Data Structures into a single Data Structure.

Representation of a Data Structure: There are 2 types of representation of Data Structure

1. Sequential representation (using ARRAY’S) : in this elements are arranged sequentially in the memory. Hence arrays are suitable for this representation.
2. Random Representation (using LINKED LIST’S): in this Data elements are arranged randomly in the memory.
   
   
   
   Classification of Data Structures:
   1. PRIMITIVE DATA STRUCTURES: are called as data types in programming languages.Ex: int , float, char and double.
   2. SIMPLE DATA STRUCTURES: these are normally constructed with the help of primitive Data Structures. These are also called as user defined Data Types (defined by the user).Ex: Array, structure, union, class and enumerated Data Type.
   3. COMPOUND DATA STRUCTURES: these can be constructed with the help of primitive and Simple Data Structures. These are of 2 types.
   1. Linear Data Structures: in the linear Data Structures the relationship of adjacency is maintained between the Data Items. Ex: STACKS, QUEUES and LINKED LIST’S
   2. Non-Linear Data Structure: in this Data Structures adjacency is not maintained between Data items. Ex: Trees and Graphs.