Follow us on Twitter!
Few are those who can see with their own eyes and hear with their own hearts. - Albert Einstein
Wednesday, April 23, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 16
Guests Online: 13
Members Online: 3

Registered Members: 82876
Newest Member: bhl1986
Latest Articles
View Thread

HellBound Hackers | Computer General | Programming

Author

binary search tree in java

the_unwanted
Member

Your avatar

Posts: 11
Location:
Joined: 03.12.10
Rank:
Newbie
Posted on 12-03-12 17:22
Code

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package datastructures;
import java.io.*;

/**
 *
 * @author unwanted
 */

public class bitree {
    static class tnode
   {
     int data;
    tnode left;
    tnode right;
    tnode(int i)
    {
        data=i;
    }
   
}   
  tnode root;
   
    bitree()
    {
        root=null;
     
    }
    boolean isEmpty()
    {
        if(root==null)
            return true;
        else
            return false;
    }
 void  insert(tnode temp,int obj)
    {
       
     
          if(obj<temp.data)
            {   
               if(temp.left!=null)
                insert(temp.left,obj);
               else
                temp.left=new tnode(obj);
            }
            else if(obj>temp.data)
            { 
               if(temp.right!=null)
                   insert(temp.right,obj);
               else
                   temp.right=new tnode(obj);
            }
            else
                System.out.println("element already exits");
         
    }
    void create(int obj)
    {
        if(isEmpty())
        {
            root=new tnode(obj);
           
        }
        else
        {   
           
            insert(root,obj);
        }
    }
    int deletemin(tnode p)
    {
        int c;
        if(p.left==null)
        {
            c=p.data;
            p=p.right;
            return c;
        }
        else
           c=deletemin(p.left);
        return c;
    }
  int del(tnode temp,int i)
    {
      int dummy=-1;
        if(temp==null)
            dummy=-1;
        else if(i<temp.data)
        {
        del(temp.left,i);
        }
        else if(i>temp.data)
        {
        del(temp.right,i);
        }
        else  if(temp.left==null)
        {
            dummy=temp.data;
            temp=temp.right;
            System.out.print(dummy);
         }           
        else if(temp.right==null)
            {
            dummy=temp.data;
            temp=temp.left;
            }
        else if((temp.left==null)&&(temp.right==null))
        {
            dummy=temp.data;
            temp=null;
        }
        else
            dummy=deletemin(temp.right);
        return dummy;
    }
  int delete(int i)
    {
        if(isEmpty())
            return -1;
        else
        {
          int ans=del(root,i);
          return ans;
        }
    }
     
     
   void in(tnode temp1)
   {
       if(temp1!=null)
       {
     
       in(temp1.left);
       System.out.println(temp1.data);
       in(temp1.right);
       }
   }
   void inorder()
   {
       if(isEmpty()) 
           System.out.println("no elements found");
       else
       {     
           
           in(root);
       }
   }
   public static void main(String args[]) throws IOException
   {
       bitree b=new bitree();
       Integer ch,i;
       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       out: while(true)
        {
            System.out.println("1.insert \n2.delete \n 3.display \n4.exit");
            ch=Integer.parseInt(br.readLine());
            switch(ch)
            {
                case 1: try
                {
                    System.out.println("enter element to be inserted");
                    Integer j=Integer.parseInt(br.readLine());
                    b.create(j);
                }
                    catch(NumberFormatException e1)
                    {
                        System.out.println("enter integers only");
                    }
                    break;
                case 2: try
                {
                    System.out.println("enter element to  delete");
                    int j=Integer.parseInt(br.readLine());
                    int rm=b.delete(j);
                   
                    if(rm==-1)
                    {
                        //System.out.println(rm);
                        throw new NullPointerException();
                    }
                    else
                    System.out.println("deleted element is"+rm);
                }
                    catch(NullPointerException e)
                    {
                        System.out.println("element not found exce");
                    }
                    catch(NumberFormatException e3)
                    {
                        System.out.println("enter integers only");
                    }
                   
                    break;
                    case 3: b.inorder();
                    break;
                case 4: break out;
                default : System.out.println("enter correct choice");
            }
        }
 
   }
   
   
}





insertion and display works fine but deletion operation not working properly :( dont know whats wrong in it.. help me with deletion operation
thank u :D
im not gud at english :|
Author

RE: binary search tree in java

Arabian
Banned



Posts: 332
Location: inside you.
Joined: 22.09.10
Rank:
Apprentice
Posted on 12-03-12 19:53
Your lack of booleans makes me want to kill myself. throwing -1 is useless when you could just use false. Also, your node constructor sucks and you don't catch duplicate errors. Also, throw yourself off a bridge if you think your syntax is good. I'm not even going to get into why your delete doesn't work. I'll let you figure out why making p = p.right without checking if p.right is not null and returning its value is not going to work.

Also, why the hell are you importing java.io.* ?

Here is a proper recursive BST:

Code
package binarySearchTree;

public class BinarySearchTree {
   protected TreeNode root;
   int size;
   
   public BinarySearchTree () {
      root = null;
   }
   
   public void insert (int x) throws Exception {
      root = insert(x, root);
      size++;
   }
   protected TreeNode insert(int x, TreeNode y) throws Exception {
      if (y == null || isEmpty() == true) {
         y = new TreeNode(x);
      }
      else if (x < y.data)
         y.left = insert(x, y.left);
      else if (x > y.data)
         y.right = insert(x, y.right);
      else
         throw new Exception();
      return y;
   }
   
   public void remove (int x) {
      root = remove (x , root);
      size--;
   }
   protected TreeNode remove (int x, TreeNode y) {
      if (y == null || isEmpty() == true) {
         throw new NullPointerException();
      }
      else if (x < y.data)
         y.left = remove(x, y.left);
      else if (x > y.data)
         y.right = remove(x, y.right);
      else if (y.left != null && y.right != null) {
         y.data = findMin(y.right).data;
         y.right = removeMin(y.right);
      }
      else
         y = y.left != null ? y.left : y.right;
      return y;
   }
   
   public void removeMin() {
      root = removeMin( root );
      size--;
   }
   protected TreeNode removeMin(TreeNode x) {
      if(x == null || isEmpty() == true) {
         throw new NullPointerException();
      }
      else if (x.left != null) {
         x.left = removeMin(x.left);
         return x;
      }
      else
         return x.right;
   }
   
   public void removeMax() {
      root = removeMax( root );
      size--;
   }
   protected TreeNode removeMax(TreeNode x) {
      if(x == null || isEmpty() == true) {
         throw new NullPointerException();
      }
      else if (x.right != null) {
         x.right = removeMax(x.right);
         return x;
      }
      else
         return x.left;
   }
   
   public int findMin() {
      return elementAt(findMin(root));
   }
   protected TreeNode findMin(TreeNode x) {
      if (x != null || isEmpty() == false) {
         while( x.left != null)
            x = x.left;
      }
      return x;
   }
   
   public int findMax() {
      return elementAt(findMax(root));
   }
   protected TreeNode findMax(TreeNode x) {
      if (x != null || isEmpty() == false) {
         while( x.right != null)
            x = x.right;
      }
      return x;
   }
   
   public int findElement(int x) {
      return elementAt(findElement(x, root));
   }
   private TreeNode findElement(int x, TreeNode y) {
      while(y != null && isEmpty() == false) {
         if( x < y.data)
            y = y.left;
         else if ( x > y.data) {
            y = y.right;
         }
         else
            return y;
      }
      return null;
   }
   
   public boolean isEmpty() {
      if(root == null)
         return true;
      else
         return false;
   }
   
   public void makeEmpty() {
      root = null;
   }
   
   private int elementAt(TreeNode x) {
      if (x == null)
         return -1;
      else
         return x.data; // return x == null ? null : x.data;
   }

   public int sizeOf() {
      return size;
   }
   
   public void inOrder() {
      inOrder(root);
   }
   private void inOrder(TreeNode x) {
      if(x != null) {
         inOrder(x.left);
         System.out.println(x.data);
         inOrder(x.right);
      }
   }
   
   public static void main( String [ ] args ) throws Exception {

        BinarySearchTree t = new BinarySearchTree( );
        final int NUMS = 4000;
        final int GAP  =   37;

        System.out.println("Building tree ::");

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        for( int i = 1; i < NUMS; i += 2 )
            t.remove( i );

        System.out.println("Maximum: " + t.findMax() + "\tMinimum: " + t.findMin());
        System.out.println("Now printing inOrdered tree: ");
        t.inOrder();
        System.out.println("Size: " + t.sizeOf());
       
       
        System.out.println("Removing maximum: " + t.findMax());
        t.removeMax();
        System.out.println("New Maximum: " + t.findMax());
       
        t.makeEmpty();
        System.out.println("Called makeEmpty(). New size: " + t.sizeOf());
   
    }
}


class TreeNode {
   
   public TreeNode left;
   public TreeNode right;
   public int data;
   
   TreeNode(int data) {
      this.data = data;
   }
   TreeNode(TreeNode node) {
      left = node.left;
      right = node.right;
      data = node.data;
   }
}




P.S.: PM me if you wanna learn more about searches and tree types. I'm not a bad guy, I just hate everything about your coding style. :)

EDIT: Updated test cases so you know it works.


G'bye y'all! I was an asshole, So korg banned me.

Edited by Arabian on 13-03-12 07:52
Author

RE: thanks for ur reply

the_unwanted
Member

Your avatar

Posts: 11
Location:
Joined: 03.12.10
Rank:
Newbie
Posted on 13-03-12 12:03
Code

import java.io.*;


public class bitree {
     class tnode
   {
     int data;
    tnode left;
    tnode right;
    tnode(int i)
    {
        data=i;
        left=null;
        right=null;
    }
   
}   
  tnode root;
    int dummy;
    tnode parent;
   
    bitree()
    {
        root=null;
        dummy=-1;
     
    }
    boolean isEmpty()
    {
        if(root==null)
            return true;
        else
            return false;
    }
 void  insert(tnode temp,int obj)
    {
         
               
           if(obj<temp.data)
            {   
               if(temp.left!=null)
                insert(temp.left,obj);
               else
                   // insert(temp.left,obj);
                temp.left=new tnode(obj);
            }
            else if(obj>temp.data)
            { 
              if(temp.right!=null)
                   insert(temp.right,obj);
               else
                   // insert(temp.right,obj);
                   temp.right=new tnode(obj);
            }
            else
                System.out.println("element already exits");
         
    }
    void create(int obj)
    {
        if(isEmpty())
        {
            root=new tnode(obj);
           
        }
        else
        {   
           
            insert(root,obj);
        }
    }
    int deletemin(tnode temp1,tnode parent)
    {
        int c;
        if(temp1.left==null)
        {   //System.out.println("left\n"+temp1.data);
            c=temp1.data;
            if(temp1.right==null)
            {
                if(parent.data<temp1.data)
                    parent.right=null;
                else
                parent.left=null;
                temp1=null;
            }
            else
            {
            parent.left=temp1.right;
            temp1=null;
            }
            return c;
        }
        else
           c=deletemin(temp1.left,temp1);
        return c;
    }
  int del(tnode temp,int i,tnode parent)
    {
 
        if(temp==null)
        {
            System.out.println("element no found");
            dummy=-1;
        }
        else if(i<temp.data)
        {
        del(temp.left,i,temp);
        }
        else if(i>temp.data)
        {
        del(temp.right,i,temp);
        }
         else if((temp.left==null)&&(temp.right==null))
        {
        dummy=temp.data;
            if(i<parent.data)
            parent.left=null;
            else
            parent.right=null;
        temp=null;
        }
        else  if(temp.left==null)
        {
            dummy=temp.data;
            if(i<parent.data)
            parent.left=temp.right;
            else
            parent.right=temp.right;
            temp=temp.right;
         }           
        else if(temp.right==null)
         {
            dummy=temp.data;
            if(i<parent.data)
            parent.left=temp.left;
            else
            parent.right=temp.left;
            temp=temp.left;
           
        }
       
        else
        { 
            temp.data=deletemin(temp.right,temp);
           
            dummy=i;
        }
        return dummy;
    }
  int delete(int i)
    {
        if(isEmpty())
            return -1;
        else
        {
            //tnode alias;
          int ans=del(root,i,root);
          return ans;
        }
    }
     
     
   void in(tnode temp1)
   {
       if(temp1!=null)
       {
     
       in(temp1.left);
       System.out.println(temp1.data);
       in(temp1.right);
       }
   }
   void pre(tnode temp1)
   {
       if(temp1!=null)
       {
        System.out.println(temp1.data);
        in(temp1.left);
        in(temp1.right);
       }
   }
   void post(tnode temp1)
   {
       if(temp1!=null)
       {
     
       in(temp1.left);
       in(temp1.right);
       System.out.println(temp1.data);
       }
   }
   void inorder()
   {
       if(isEmpty()) 
           System.out.println("no elements found");
       else
       {     
           in(root);
       }
   }
   void postorder()
   {
       
       if(isEmpty()) 
           System.out.println("no elements found");
       else
       {     
           
           post(root);
       }
   }
   void preorder()
   {
       if(isEmpty()) 
           System.out.println("no elements found");
       else
       {     
           pre(root);
       }
   }
   public static void main(String args[]) throws IOException
   {
       bitree b=new bitree();
       Integer ch,i;
       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       out: while(true)
        {
            System.out.println("1.insert \n2.delete \n 3.preorder \n 4.inorder \n 5.postorder \n6.exit");
            ch=Integer.parseInt(br.readLine());
            switch(ch)
            {
                case 1: try
                {
                    System.out.println("enter element to be inserted");
                    Integer j=Integer.parseInt(br.readLine());
                    if(j<0)
                        throw new NumberFormatException();
                    b.create(j);
                }
                    catch(NumberFormatException e1)
                    {
                        System.out.println("enter integers (positive) only");
                    }
                    break;
                case 2: try
                {
                    System.out.println("enter element to be element");
                    int j=Integer.parseInt(br.readLine());
                    int rm=b.delete(j);
                   
                    if(rm==-1)
                    {
                        //System.out.println(rm);
                        throw new NullPointerException();
                    }
                    else
                    System.out.println("deleted element is"+rm);
                    }
                    catch(NullPointerException e)
                    {
                        System.out.println("element not found");
                    }   
                    break;
                    case 3: b.preorder();
                    break;
                    case 4: b.inorder();
                    break;
                    case 5: b.postorder();
                    break;
                    case 6: break out;
                    default : System.out.println("enter correct choice");
            }
        }
 
   }
   
   
}




i modified code now insertion,deletion and inorder working properly
i m inserting only positive values so -1 indicate element not found
i know its not a gud way to program
the thing is preorder and postorder not working properly .. plz check once
i think problem is at insertion of node..
plz tell wer i went wrong
im not gud at english
:(
Author

RE: binary search tree in java

Arabian
Banned



Posts: 332
Location: inside you.
Joined: 22.09.10
Rank:
Apprentice
Posted on 13-03-12 18:57
the_unwanted wrote:

i modified code now insertion,deletion and inorder working properly
i m inserting only positive values so -1 indicate element not found
i know its not a gud way to program
the thing is preorder and postorder not working properly .. plz check once
i think problem is at insertion of node..
plz tell wer i went wrong
im not gud at english
Sad


Why are you calling in() in your post and preorder methods? You make no sense.


G'bye y'all! I was an asshole, So korg banned me.

Edited by Arabian on 13-03-12 20:16