SringSring

Tuesday, 28 October 2014

Binary Search Tree implementation

package com.srini.DS.search;

import java.util.Scanner;

public class BinarySearchTree {
public static void main(String[] args)
   {                
       Scanner scan = new Scanner(System.in);
       /* Creating object of BST */
       BST bst = new BST();
       System.out.println("Binary Search Tree Test\n");        
       char ch;
       /*  Perform tree operations  */
       do  
       {
           System.out.println("\nBinary Search Tree Operations\n");
           System.out.println("1. insert ");
           System.out.println("2. delete");
           System.out.println("3. search");
           System.out.println("4. count nodes");
           System.out.println("5. check empty");

           int choice = scan.nextInt();          
           switch (choice)
           {
           case 1 :
               System.out.println("Enter integer element to insert");
               bst.insert( scan.nextInt() );                    
               break;                        
           case 2 :
               System.out.println("Enter integer element to delete");
               bst.delete( scan.nextInt() );                    
               break;                        
           case 3 :
               System.out.println("Enter integer element to search");
               System.out.println("Search result : "+ bst.search( scan.nextInt() ));
               break;                                        
         
           case 4 :
               System.out.println("Nodes = "+ bst.countNodes());
               break;    
           case 5 :
               System.out.println("Empty status = "+ bst.isEmpty());
               break;          
           default :
               System.out.println("Wrong Entry \n ");
               break;  
           }
           /*  Display tree  */
           System.out.print("\nPost order : ");
           bst.postorder();
           System.out.print("\nPre order : ");
           bst.preorder();
           System.out.print("\nIn order : ");
           bst.inorder();

           System.out.println("\nDo you want to continue (Type y or n) \n");
           ch = scan.next().charAt(0);                      
       } while (ch == 'Y'|| ch == 'y');              
   }
}



----------------------------------------------------------

package com.srini.DS.search;

public class BST {
private BSTNode root;
 
     /* Constructor */
     public BST()
     {
         root = null;
     }
     /* Function to check if tree is empty */
     public boolean isEmpty()
     {
         return root == null;
     }
     /* Functions to insert data */
     public void insert(int data)
     {
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private BSTNode insert(BSTNode node, int data)
     {
         if (node == null)
             node = new BSTNode(data);
         else
         {
             if (data <= node.getData())
                 node.left = insert(node.left, data);
             else
                 node.right = insert(node.right, data);
         }
         return node;
     }
     /* Functions to delete data */
     public void delete(int k)
     {
         if (isEmpty())
             System.out.println("Tree Empty");
         else if (search(k) == false)
             System.out.println("Sorry "+ k +" is not present");
         else
         {
             root = delete(root, k);
             System.out.println(k+ " deleted from the tree");
         }
     }
     private BSTNode delete(BSTNode root, int k)
     {
         BSTNode p, p2, n;
         if (root.getData() == k)
         {
             BSTNode lt, rt;
             lt = root.getLeft();
             rt = root.getRight();
             if (lt == null && rt == null)
                 return null;
             else if (lt == null)
             {
                 p = rt;
                 return p;
             }
             else if (rt == null)
             {
                 p = lt;
                 return p;
             }
             else
             {
                 p2 = rt;
                 p = rt;
                 while (p.getLeft() != null)
                     p = p.getLeft();
                 p.setLeft(lt);
                 return p2;
             }
         }
         if (k < root.getData())
         {
             n = delete(root.getLeft(), k);
             root.setLeft(n);
         }
         else
         {
             n = delete(root.getRight(), k);
             root.setRight(n);             
         }
         return root;
     }
     /* Functions to count number of nodes */
     public int countNodes()
     {
         return countNodes(root);
     }
     /* Function to count number of nodes recursively */
     private int countNodes(BSTNode r)
     {
         if (r == null)
             return 0;
         else
         {
             int l = 1;
             l += countNodes(r.getLeft());
             l += countNodes(r.getRight());
             return l;
         }
     }
     /* Functions to search for an element */
     public boolean search(int val)
     {
         return search(root, val);
     }
     /* Function to search for an element recursively */
     private boolean search(BSTNode r, int val)
     {
         boolean found = false;
         while ((r != null) && !found)
         {
             int rval = r.getData();
             if (val < rval)
                 r = r.getLeft();
             else if (val > rval)
                 r = r.getRight();
             else
             {
                 found = true;
                 break;
             }
             found = search(r, val);
         }
         return found;
     }
     /* Function for inorder traversal */
     public void inorder()
     {
         inorder(root);
     }
     private void inorder(BSTNode r)
     {
         if (r != null)
         {
             inorder(r.getLeft());
             System.out.print(r.getData() +" ");
             inorder(r.getRight());
         }
     }
     /* Function for preorder traversal */
     public void preorder()
     {
         preorder(root);
     }
     private void preorder(BSTNode r)
     {
         if (r != null)
         {
             System.out.print(r.getData() +" ");
             preorder(r.getLeft());             
             preorder(r.getRight());
         }
     }
     /* Function for postorder traversal */
     public void postorder()
     {
         postorder(root);
     }
     private void postorder(BSTNode r)
     {
         if (r != null)
         {
             postorder(r.getLeft());             
             postorder(r.getRight());
             System.out.print(r.getData() +" ");
         }
     }     
}

----------------------------------------------------
package com.srini.DS.search;

public class BSTNode {
BSTNode left, right;
     int data;
 
     /* Constructor */
     public BSTNode()
     {
         left = null;
         right = null;
         data = 0;
     }
     /* Constructor */
     public BSTNode(int n)
     {
         left = null;
         right = null;
         data = n;
     }
     /* Function to set left node */
     public void setLeft(BSTNode n)
     {
         left = n;
     }
     /* Function to set right node */ 
     public void setRight(BSTNode n)
     {
         right = n;
     }
     /* Function to get left node */
     public BSTNode getLeft()
     {
         return left;
     }
     /* Function to get right node */
     public BSTNode getRight()
     {
         return right;
     }
     /* Function to set data to node */
     public void setData(int d)
     {
         data = d;
     }
     /* Function to get data from node */
     public int getData()
     {
         return data;
     }
}

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)