Binary Search Tree Implementation

/*
 Write a program to implement simple Binary Search tree Implementation and demonstrate.
1) Inorder traversal
2) Postorder traversal
3) Preorder traversal
 */
package binary_search_tree;

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class Node
{
   Node Left;
   Node Right;
   int data;
 
   public Node()
   {
       Left = null;
       Right = null;
       data = 0;
   }
 
   public Node(int data)
   {
       Left = null;
       Right = null;
       this.data = data;
   }

    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
{
    Node root;
    Node parent;
 
    public Binary()
    {
        root = null;
    }
 
    public void insert(int data)
    {
        root = insert(root,data);
    }
 
    public Node insert(Node node,int data)
    {
        if(node==null)
        {
             parent = node;
             node = new Node(data);
           
        }
        else
        {
         
                    if(data>=node.getData())
                    {
//                        if(node.getRight()==null)
//                            {

                        node.Right = insert(node.Right,data);
//                            }
                    }
         
                     else if(data<=node.getData())
                     {
//                        if(node.getLeft()==null)
//                        {
                        node.Left = insert(node.Left,data);
//                        }
                     }
        }
        return node;
    }
 
    public void preorder()
    {
        preorder(root);
    }
 
    public void preorder(Node node)
    {
        if(node!=null)
        {
        System.out.print(node.getData() + " ");
        preorder(node.getLeft());
        preorder(node.getRight());
        }
    }
 
    public void inorder()
    {
       inorder(root);
    }
 
    public void inorder(Node node)
    {
        if(node!=null)
        {
            inorder(node.getLeft());
        System.out.print(node.getData() + " ");
     
        inorder(node.getRight());
        }
    }
 
    public void postorder()
    {
        postorder(root);
    }
 
    public void postorder(Node node)
    {
        if(node!=null)
        {
     
        postorder(node.getLeft());
        postorder(node.getRight());
        System.out.print(node.getData() + " ");
        }
    }
 
}
public class Binary_Search_Tree {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
     
        Binary bt = new Binary();
        char ch;
        Scanner sc = new Scanner(System.in);
        do
        {
            System.out.print("insert the values");
            int data = sc.nextInt();
            bt.insert(data);
            System.out.print(" Do you want to insert the values");
         ch = sc.next().charAt(0);
        }while(ch=='y' || ch== 'Y');
        System.out.print("preorder traversal--->");
        bt.preorder();
        System.out.print("Inorder traversal--->");
        bt.inorder();
        System.out.print("Postorder traversal--->");
        bt.postorder();
     
    }
 
}

Binary Tree Implementation

/* Write a Program for Simple Binary Tree implementation and demonstrate
1) Inorder traversal
2) Postorder traversal
3) Pre order traversal

*/


package binary_tree;

import java.util.Scanner;

/**
 *
 * @author shashank
 */

class Node
{
    Node Left;
    Node Right;
    String data ;
 
    public Node()
    {
        Left = null;
        Right = null;
        data = null;
    }
 
    public Node(String data)
    {
        this.Left = null;
        this.Right = null;
        this.data = data;
    }

    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 String getData() {
        return data;
    }

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

class Binary
{

    Node root;
    int c = 0;
    public Binary()
    {
        root = null;
    }
 
    public void insert_binary(String data)
    {
        root = insert_binary_tree(root,data);
    }
 
    public Node insert_binary_tree(Node node,String d)
    {
     
        if(node==null)
        {
            node = new Node(d);
        //    System.out.print("i am here again" + c);
     
        }
     
        else
        {
            if(node.getRight()==null)
            {
                node.Right = insert_binary_tree(node.Right,d);
          //      c = 1;
            }
            else
            {
                 node.Left = insert_binary_tree(node.Left,d);
             //    c = 2;
            }
         
        }
        return node;
    }
    public void preorder()
    {
        preorder_traversal(root);
    }
    public void preorder_traversal(Node preO)
    {
        if(preO!=null)
        {
            System.out.print(preO.getData() + " ");
            preorder_traversal(preO.getLeft());
            preorder_traversal(preO.getRight());
         
        }
    }
 
     public void inorder()
    {
        inorder_traversal(root);
    }
    public void inorder_traversal(Node inO)
    {
        if(inO!=null)
        {
           inorder_traversal(inO.getLeft());
            System.out.print(inO.getData() + " ");
            inorder_traversal(inO.getRight());
         
        }
    }
       public void postorder()
    {
        postorder_traversal(root);
    }
    public void postorder_traversal(Node po)
    {
        if(po!=null)
        {
            postorder_traversal(po.getLeft());
            postorder_traversal(po.getRight());
            System.out.print(po.getData() + " ");
         
        }
    }
 
}
public class Binary_Tree {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
     
        char ch;
        Binary b = new Binary();
        Scanner sc = new Scanner(System.in);
        do
        {
     
        System.out.println("enter data");
     
        String data = sc.next();
     
        b.insert_binary(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.print("Post order :->");
        b.postorder();
        System.out.println();
        System.out.print("Pre order :->");
        b.preorder();
        System.out.println();
        System.out.print("In order :->");
        b.inorder();
    }
 
}

Hashing - Linear Probing

/* Hashing using Linear Probing */

/*Write a Program to create your own Hash Map data Structure and prevent collision using Linear Probing*/

/*Linear probing is a strategy for resolving the hash collision by placing the key into the closest possible empty cell.

In order to add an item to the hash table , we will first create

1) Customize function to calculate hashcode.

2) Calculate index using hash function h(x) = (key.hashcode()+i)%HASH_TABLE_SIZE.

3)In order to find next possible empty cell we will use rehashing technique.

In Linear probing we will calculate the threshold/Load_factor and once the size is greater than max size,we will initialize a new array as 2*old_table_size and copy the old array elements into the new initialized array.

Please find below source code of program in order to implement Linear Probing hashing */




package hashing_closed_addressing;

import java.util.Scanner;

/**
 *
 * @author shashank
 */

class hash_code
{
 
    int hash_table_size =11;
    String hash_table[] = new String[hash_table_size];
    String hash_key[] = new String[hash_table_size];
    char hash_value[];
    private float threshold = .75f;
    int maxsize;
    int currentsize = 0;
 
 
    public int hash_code(String key)
    {
        hash_value = key.toCharArray();
        int hash_code=0;
     
        for(int i=0;i<hash_value.length;i++)
        {
            hash_code = hash_code + hash_value[i];
        }
        return hash_code;
    }
 
    public void setthreshold(float threshold)
    {
        this.threshold = threshold;
        maxsize = (int)(hash_table.length * threshold);
     
    }
 
    public int hash_function(String key,int i)
    {
        int hash_val = hash_code(key);
        int index = (hash_val+i)%hash_table.length;
        return index;
    }
 
    public void hash_map(String key,String value)
    {
     
     
        int i =0;
       maxsize = (int)(hash_table.length * threshold);
     
            //System.out.println(" i a here buddy");
        while(i<hash_table_size)
        {
            int index = hash_function(key,i);
            if(hash_table[index]==null)
            {
                hash_table[index] = value;
                hash_key[index] = key;
                currentsize++;
                break;
            }
            i++;
        }
     
        if(currentsize>maxsize)
        {
           // System.out.println(" i a here buddy");
            resize_Array();
        }
                           
    }
 
    public String get_value(String key)
    {
        int i =0;
        int index =0;
   
        while(i<hash_table_size)
        {
         index = hash_function(key,i);
        if(hash_table[index]==null)
        {
            System.out.println("No value at given index");
        }
        else if(hash_key[index].equals(key))
        {
            return hash_table[index];
        }
        i++;
        }
        return "No data";
    }
 
    public void resize_Array()
    {      
     
         hash_table_size = 2*(hash_key.length);
        maxsize = (int)(hash_table_size * threshold);
        String[] old_hash_table = hash_table;
        String[] old_hash_key = hash_key;
         hash_table = new String[hash_table_size];
         hash_key = new String[hash_table_size];
        currentsize=0;
     
        System.out.println(hash_table_size);
     
        for(int i=0;i<old_hash_table.length;i++)
        {
            if(old_hash_table[i]!=null && old_hash_key[i]!=null )
            {
             //   System.out.println("inside resize" + old_hash_key[i]+ old_hash_table[i]);
            hash_map(old_hash_key[i],old_hash_table[i]);
            }
        }
    }
}

public class Linear_probing {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
     
        hash_code hk = new hash_code();
        Scanner sc = new Scanner(System.in);
        int c;
        do
        {
            System.out.print("Enter Key value :-->");
            String key = sc.next();
         
            System.out.println("Enter  value :-->");
            String value = sc.next();
         
            hk.hash_map(key, value);
         
         
            System.out.println("Do you want to enter more values press Y to yes else n to exit");
            c = sc.next().charAt(0);
        }while(c=='Y'||c=='y');
     
        do
        {
            System.out.println("Enter Key value to retrieve data :-->");
            String key = sc.next();
         
           String val =  hk.get_value(key);
         
            System.out.println("Value at mentioned key -->" + key + " is :-->" + val);
         
            System.out.println("Do you want to retrieve more values press Y to yes else n to exit");
            c = sc.next().charAt(0);
        }while(c=='Y'||c=='y');
        // TODO code application logic here
    }
 
}

OPEN HASHING --- HASH TABLE CHAINING USING LINKED LIST

/*OPEN HASHING --- HASH TABLE CHAINING USING linked LIST */

/*Write a Program to create your own Hash Map data structure and prevent collision using open hashing chaining,*/

Chaining allows sorting the key elements with the same hash value into linked list.

With open hashing ,the hash table is implemented as a data structure of array and that of fix size.
Where the empty hash table is first created ,each location in the array contains an empty list.
In order to add an item to the hash table , we will first create

1) Customize function to calculate hashcode.

2) Calculate hash value using hash function h(x) = key.hashcode()%HASH_TABLE_SIZE.

3)Location given by the hash

value of the Key will searched and the new item is inserted to the head of the singly linked list.

package hashingsc;



import java.util.Scanner;

/**
 *
 * @author shashank

 */

class Node
{
    protected Node link;
    protected String data;
    protected String key;
 
    public Node()
    {
        link = null;
        data = null;
        key = null;
             
    }
    public Node(String data,String key, Node link)
    {
        this.link = link;
        this.data = data;
        this.key = key;
    }
 
    public void setLink(Node n)
    {
        this.link = n;
    }
 
    public void setdata(String data)
    {
        this.data = data;
    }
 
    public void setKey(String key)
    {
        this.key = key;
    }
 
    public Node getlink()
    {
        return link;
    }
 
    public String getdata()
    {
        return data;
 
    }
 
    public String getKey()
    {
        return key;
 
    }

}


class hash_key
{
int hash_table_size = 10;
Node start;
Node end;
int size;
char key_value[];
Node hk[] = new Node[hash_table_size];
int len;
public hash_key()
{
    start = null;
    end = null;
    size = 0;

}

public boolean isempty()
{
    return start==null;
}

public int getSize()
{
    return size;
}

public Node insert_at_beg(String d,String  key ,int index)
{
    Node nptr = new Node(d,key,null);

    if(hk[index]==null)
    {
        hk[index] = nptr;
    }
    else
    {
        nptr.setLink(hk[index]);
        hk[index] = nptr;
    }
    return hk[index];
}

public int calculateHashKeycode(String hash)
{
    key_value  = hash.toCharArray();
 
    int hashcode = 0;
    for(int i=0;i<hash.length();i++)
    {
        hashcode = hashcode + key_value[i];
     
     
     // System.out.println("Ascii value for :" + key_value[i] + ": is :" + (int)key_value[i]);
    }
   // System.out.println("hashcode is" + hashcode);
    return hashcode;
 
}

public int hash_function(String key)
{
    int hash_code = calculateHashKeycode(key);
    int index = hash_code%hash_table_size;
    return index;
}

public void hash_map(String key, String value)
{
    int index= hash_function(key);
    hk[index] = insert_at_beg(value,key,index);
}

public String gethashvalue(String key)
{    
    int index = hash_function(key);
 
    if(hk[index]==null)
    {
        return "no key stored with given value";
    }
 
    Node current = hk[index];
 
 
    if(current.getlink()==null)
    {
        if(key.equals(current.getKey()))
        return current.getdata();
        else
            return "Key not found";
    }
 
    else
    {
        while(current!=null)
        {
           // System.out.print("inside this loop" + index);
            if(key.equals(current.getKey()))
                return current.getdata();
 
            else
            {
               current = current.getlink();
         
            }
         
        }
        return "Key not found";
     
    }
}
}
public class HashingSC {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
     
        Scanner sc = new Scanner(System.in);
     
        hash_key hk = new hash_key();
     
        System.out.println("Enter Key value pair");
     
        for(int i=0;i<3;i++)
        {
            System.out.print("Enter Key ---->");
            String key = sc.next();
            System.out.print("Enter associated Value ----->");
            String value = sc.next();
       hk.hash_map(key,value);
        }
        char c;
        do
        {
            System.out.println("Enter Key to retrieve data");
      System.out.println("values of a given key is ::->" + hk.gethashvalue(sc.next()));
         
           System.out.print("Do you want to retrieve more values press y to continue and n to exit ->");
            c = sc.next().charAt(0);
        }while(c =='y'||c=='Y');
     
     
        // TODO code application logic here
    }
 
}