Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: Binary Search Tree

  1. #1
    Member
    Join Date
    Mar 2009
    Posts
    48
    Thanks
    3
    Thanked 2 Times in 2 Posts

    Default Binary Search Tree

    Hello, I have to do Binary Search Tree. I found on internet a lot of versions, but i need it just simple. First time, I need help with method insert.
    My code:
    public class BinarySearchTree {
        private Node root;
        private Node parent;
        private Node node;
     
     
        public boolean isEmpty()
        {
            return root==null ;
        }
     
        public void insert(int number)
        {
              if(root==null)
               {
                   Node newNode = new Node();
                   newNode.setData(number);
                   root=newNode;
               }  
        }
     
        public void remove(int)
        {
     
        }
     
        public boolean contains(int)
        {
            return;
        }
     
     
    }

    public class Node {
        private Node left;      //left children
        private Node right;     //right children
        private Node parent;
        private int data;
     
     
        public void setLeft(Node left)
        {
            this.left=left;
        }
        public Node getLeft()   
        {
            return left;
        }
     
        public void setRight(Node right)
        {
            this.right=right;
        }
     
        public Node getRight()
        {
            return right;
        }
     
        public void setParent(Node parent)
        {
            this.parent=parent;
        }
     
        public Node getParent()
        {
            return parent;
        }
     
        public void setData(int data)
        {
            this.data=data;
        }
     
        public int getData()
        {
            return data;
        }
    }
    Last edited by Koren3; November 7th, 2009 at 09:17 AM.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Binary Search Tree

    The simplified textbook way of doing insert into a binary tree is to use recursion. Create a function that accepts a Node and (in your case) an int as parameters. Check if the node is null, if it is return a new node, if it is not, check the value against the current node data, if it is greater than perform insert on the right node and if it is less than perform insert on the left node. You initiate the insert by passing the root node as the parameter.
    semi pseudo-code
    private Node insert(Node node, int data)
    {
        //insert code to check if node is null, if it is return a new node
        ......
        //recursively go down the tree
        if ( node.getData() > data )
        {
             node.setRight(insert( node.getRight(), data));//do insert on the right node
        }
        else
        {
             //...do the same as above for the the left node
        }
        return node;
    }
    public void insertData(int data)
    {
       root =  insert(root, data);
    }

    Other functions, such as removal and traversal involve a similar type of code to move down the tree until you hit the node you want.

  3. #3
    Member
    Join Date
    Mar 2009
    Posts
    48
    Thanks
    3
    Thanked 2 Times in 2 Posts

    Default Re: Binary Search Tree

    Thank you but Donīt it do another way? Because I got UML diagram with methods and method insert look like insert (int).
    UML diagram on picture: Imageshack - treeu

  4. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Binary Search Tree

    Quote Originally Posted by Koren3 View Post
    Thank you but Donīt it do another way? Because I got UML diagram with methods and method insert look like insert (int).
    UML diagram on picture: Imageshack - treeu
    That's essentially what the insertData function is in the code above. Just rename the two functions to conform to the UML

  5. The Following User Says Thank You to copeg For This Useful Post:

    Koren3 (November 8th, 2009)

  6. #5
    Member
    Join Date
    Mar 2009
    Posts
    48
    Thanks
    3
    Thanked 2 Times in 2 Posts

    Default Re: Binary Search Tree

    Ohh yes. Thank you.
    I wrote this code:
    public boolean isEmpty()
        {
            return root==null ;
        }
     
       private Node insertData(Node node, int data)
    {
        //insert code to check if node is null, if it is return a new node
        if (node==null)
        {
            return node;
        }
        //recursively go down the tree
        if ( node.getData() > data )
        {
             node.setRight(insertData( node.getRight(), data));//do insert on the right node
        }
        else
        {
             node.setLeft(insertData(node.getLeft(), data));//do insert on the left node
        }
        return node;
    }
    public void insert(int data)
    {
       root =  insertData(root, data);
    }
    public class Main {
     
     
        public static void main(String[] args) {
            BinarySearchTree b1 = new BinarySearchTree();
     
            System.out.println(b1.isEmpty());
            b1.insert(10);
            b1.insert(5);
            b1.insert(3);
            b1.insert(12);
            b1.insert(14);
            System.out.println(b1.isEmpty());
     
        }
     
    }
    But it write:
    true
    true
    Where is the problem?
    Last edited by Koren3; November 8th, 2009 at 03:47 AM.

  7. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Binary Search Tree

    In you're insert method you need to check for a null root node. Then, if it is null, create a new node.

  8. #7
    Member
    Join Date
    Mar 2009
    Posts
    48
    Thanks
    3
    Thanked 2 Times in 2 Posts

    Default Re: Binary Search Tree

    I changed it but nothing...
    Did you mean this?
    public class BinarySearchTree {
        private Node root;
        private Node parent;
        private Node node;
     
     
        public boolean isEmpty()
        {
            return root==null ;
        }
     
       private Node insertData(Node node, int data)
    {
        //insert code to check if node is null, if it is return a new node
        if (node==null)
        {
            return node;
        }
        //recursively go down the tree
        if ( node.getData() > data )
        {
             node.setRight(insertData( node.getRight(), data));//do insert on the right node
        }
        else
        {
             node.setLeft(insertData(node.getLeft(), data));//do insert on the left node
        }
        return node;
    }
    public void insert(int data)
    {
        if (root==null)
        {
        root =  insertData(root, data);
        }
    }

  9. #8
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Binary Search Tree

    no, like this:

    public void insert(int data)
    {
        if (root == null)
        {
              root = new Node(); // err, i'm not sure i know what you're node constructor looks like, but put it here
         }
         insertData(root, data);
    }

  10. #9
    Member
    Join Date
    Mar 2009
    Posts
    48
    Thanks
    3
    Thanked 2 Times in 2 Posts

    Default Re: Binary Search Tree

    I changed it:
    public class BinarySearchTree {
        private Node root;
        private Node parent;
        private Node node;
     
     
        public boolean isEmpty()
        {
            return root==null ;
        }
     
       private Node insertData(Node node, int data)
    {
        //insert code to check if node is null, if it is return a new node
        if (node==null)
        {
            return node = new Node();
        }
        //recursively go down the tree
        if ( node.getData() > data )
        {
             node.setRight(insertData(node.getRight(), data));//do insert on the right node
        }
        else
        {
             node.setLeft(insertData(node.getLeft(), data));//do insert on the left node
        }
        return node;
    }
    public void insert(int data)
    {
        if (root==null)
        {
            root = new Node();
            insertData(root, data);
        }
        insertData(root, data);
    }
    Class Node:
    public class Node {
        private Node left;      //left children
        private Node right;     //right children
        private Node parent;
        private int data;
     
     
        public void setLeft(Node left)
        {
            this.left=left;
        }
        public Node getLeft()
        {
            return left;
        }
     
        public void setRight(Node right)
        {
            this.right=right;
        }
     
        public Node getRight()
        {
            return right;
        }
     
        public void setParent(Node parent)
        {
            this.parent=parent;
        }
     
        public Node getParent()
        {
            return parent;
        }
     
        public void setData(int data)
        {
            this.data=data;
        }
     
        public int getData()
        {
            return data;
        }
    }

    But something is wrong. picture Ddebuger: Imageshack - debuga
    Last edited by Koren3; November 11th, 2009 at 04:13 AM.

  11. #10
    Member
    Join Date
    Mar 2009
    Posts
    48
    Thanks
    3
    Thanked 2 Times in 2 Posts

    Default Re: Binary Search Tree

    Ok I solved it. Now i am trying do method remove.

Similar Threads

  1. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 12:23 AM
  2. recursive search of all local disks
    By ttsdinesh in forum Java Theory & Questions
    Replies: 4
    Last Post: September 27th, 2009, 08:23 AM
  3. How to highlight search keyword in text?
    By Mohd in forum JavaServer Pages: JSP & JSTL
    Replies: 4
    Last Post: February 1st, 2009, 06:35 AM
  4. Implementation of search function for Patricia Trie
    By javaguy in forum What's Wrong With My Code?
    Replies: 0
    Last Post: July 21st, 2008, 01:54 PM