Results 1 to 9 of 9
  1. #1
    yanikaA is offline Member
    Join Date
    Jan 2013
    Posts
    5
    Rep Power
    0

    Exclamation Generic Binary Search Tree HELP!!

    Hi all!! Happy New Year to everyone!

    Hi all !! Happy New Year!!

    I am currently working on a Generic Binary Search Tree. The insertion is done according to a variable - int seqNo and the get and set methods for seqNo are in a class called AnyClass (which is in a package named dataobjects).
    Now, when I am calling the getseqNo() method in the BST class, it seems that it cannot be found.
    I also have a class named Node that creates the nodes for the BST.
    These are my classes ;

    This is the AnyClass Class:

    Java Code:
    package dataobjects;  
      
    import java.util.Scanner;  
      
    public abstract class AnyClass  
    {  
        Scanner sc = new Scanner(System.in);  
          
        public int seqNo;  
        public String name;  
          
          
        public AnyClass()  
        {  
        }  
          
        public String getData()  
        {  
            return "Number " + seqNo;  
        }  
          
        public void edit()   
        {  
            System.out.println("Enter new number for the  ");  
            seqNo = sc.nextInt();  
        }  
          
        public String getKey()  
        {  
            return " "+seqNo;  
        }  
          
        public void setseqNo(int SeqNo)  
        {  
            seqNo = SeqNo;  
        }  
          
        public int getseqNo()  
        {  
            return seqNo;  
        }  
          
        public static int randInt (int min, int max)  
        {  
            int n = min + (int) (Math.random() * (double) (max-min+1));  
            System.out.println(n);  
            return n;  
        }  
    }
    The following is the Node Class

    Java Code:
    package LinearNode;  
      
    import dataobjects.*;  
      
    public class Node<E>  
    {  
        public E obj;  
        public Node <E> next;  
        public Node <E> left;  
        public Node <E> right;  
              
        public Node(E newObj)  
        {  
            obj = newObj;  
            next = null;  
        }  
          
        public void show()  
        {  
            System.out.println(obj);  
        }  
    }

    And finally the BST Class:

    Java Code:
    import LinearNode.*;  
    import dataobjects.*;  
      
    public class BST<E>  
    {  
           
        Node <E> root;  
          
      protected Node <E> insert (Node root,Node newNode)   
      {  
          if (root == null)  
             root = newNode;   
          else  
          {  
            if((newNode.obj.getSeqNo())<(root.obj.getSeqNo())) // if first is less than second  
                root.left = insert(root.left,newNode);  
            else  
                root.right = insert(root.right, newNode);      
          }    
          return root;   
      }   
          
      public void insertBST (E newObj)  
      {  
          Node temp = new Node (newObj);  
          root = insert (root,temp);  
      }  
          
      protected Node <E> search (Node root, int key)  
      {  
          if(root == null)  
             return null;  
          else  
          {  
              if(key == root.obj.getseqNo())  
                return root;  
              else  
              if (key<root.obj.getseqNo())  
                return search(root.left , key);  
              else  
                return search(root.right, key);  
          }  
      }  
        
      public AnyClass SearchBST(int key)  
      {  
          Node <E> temp = search(root,key);  
          if(temp== null)  
            return null;  
          else  
            return temp.obj;  
      }  
        
      protected void inorder(Node root)  
      {  
          if(root !=null)   //if not empty  
          {   
              inorder(root.left);  
              root.show();  
              inorder(root.right);   
          }   
      }  
          
      public void inorderBST()  
      {  
        inorder(root);  
      }  
    }
    Thanks in advance!

  2. #2
    Potato is offline Member
    Join Date
    Dec 2011
    Posts
    25
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    What is the point of the 'next' Node. And in this method:

    Java Code:
      protected Node <E> insert (Node root,Node newNode)  
      { 
          if (root == null) 
             root = newNode;  
          else 
          { 
            if((newNode.obj.getSeqNo())<(root.obj.getSeqNo())) // if first is less than second 
                root.left = insert(root.left,newNode); 
            else 
                root.right = insert(root.right, newNode);     
          }   
          return root;  
      }
    This does either:

    Java Code:
    root.left = root.left;
    
    // or
    
    root.right = root.right;
    not sure what that accomplishes...
    Last edited by Potato; 01-02-2013 at 08:24 PM.

  3. #3
    yanikaA is offline Member
    Join Date
    Jan 2013
    Posts
    5
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    oh no.. nothing.. i declared that because I was using the Node class for another project... that has nothing to do with this. Thanks!

  4. #4
    Potato is offline Member
    Join Date
    Dec 2011
    Posts
    25
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    If I understand you correctly, you want the insert method to insert the nodes based on the value of getSeqNo() right?

    So it looks like this (Node 1 is the root because it has the smallest seqNo):

    Node 1, seqNo=0
    Node 2, seqNo=5
    Node 3, seqNo=6
    Node 4, seqNo=8

    etc, they are in order of least to greatest

    And for Node 1:

    left = null
    right = Node 2

    And for Node 2:

    left = Node 1
    right = Node 3

    etc.

    Is that what you're trying to accomplish?

  5. #5
    yanikaA is offline Member
    Join Date
    Jan 2013
    Posts
    5
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    Yes exactly! thanks !

  6. #6
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: Generic Binary Search Tree HELP!!

    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  7. #7
    yanikaA is offline Member
    Join Date
    Jan 2013
    Posts
    5
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    ok ok...fine... now I know that I cross Posted!!!!

  8. #8
    Potato is offline Member
    Join Date
    Dec 2011
    Posts
    25
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    I mean, this would work if seqNo is unique (no 2 nodes have the same value for seqNo)

    Java Code:
    protected Node <E> insert (Node root,Node newNode) 
    {
        if (root == null)
           root = newNode; 
        else {
           boolean dir = newNode.obj.getSeqNo() < root.obj.getSeqNo(); // direction: if true move left, if false move right
           Node<E> prev = root;
           do {
               root = dir ? root.left : root.right;
               if (root == null) { // moved all the way left or right
                   if (dir) { // we moved all the way left
                       this.root = newNode; // newNode is the head of your list of Nodes
                       newNode.right = prev; // to the right of newNode is the previous head
                       prev.left = newNode; // to the left of the previous head is newNode. a bit redundant.
                   } else { // we moved all the way right
                       prev.right = newNode; // to the right of your previous tail is newNode
                       newNode.left = prev; // newNode is the new tail, to its left is the previous tail
                   }
               }
               prev = root; // keep a reference to the previous root
           } while (newNode.obj.getSeqNo() < root.obj.getSeqNo() == dir);
           // If we got to this point, we haven't reached the head or tail end of the Node list
           // 'root' will be on one side of 'newNode' and 'prev' will be on the other side of 'newNode'
           // if we were moving left, i.e. dir == true, then root should be on the left said and prev on the right side. if dir == false, vice versa.
           if (dir) {
               root.right = newNode;
               prev.left = newNode;
               newNode.left = root;
               newNode.right = prev;
           } else {
               root.left = newNode;
               prev.right = newNode;
               newNode.right = root;
               newNode.left = prev;
           }
        }
        return root;
    }
    I worked this out in my head and typed it here, not sure if it'll work or even compile. My explanation should be sound though, read the comments.

  9. #9
    yanikaA is offline Member
    Join Date
    Jan 2013
    Posts
    5
    Rep Power
    0

    Default Re: Generic Binary Search Tree HELP!!

    Thanks! that clears some problems I have in solving this problem. I went through the code and it seems good. I will try and implement it and do some minor changes if needed. Thanks again for your time. I really appreciate that :D

Similar Threads

  1. Binary search tree ?
    By santa in forum New To Java
    Replies: 5
    Last Post: 06-07-2011, 04:22 PM
  2. Replies: 6
    Last Post: 04-28-2010, 01:49 AM
  3. Replies: 0
    Last Post: 04-04-2010, 08:40 AM
  4. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 02:42 AM
  5. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 03:03 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •