Like Tree1Likes
  • 1 Post By GReaper

Binary Search Tree-search method help?

This is a discussion on Binary Search Tree-search method help? within the C++ Programming forums, part of the General Programming Boards category; Ive been trying to implement a simple search method for my BST but its always returning false, and when i ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    4

    Binary Search Tree-search method help?

    Ive been trying to implement a simple search method for my BST but its always returning false, and when i use cout statements to see where its going, it only ever goes in one case(the < one)-i've tried many variations, but maybe ive been staring at it for too long. hoping a new pair of eyes might shed some light. thanks.

    its searching for the customer based off of first and last name, ive overloaded the comparison operators (and checked that they work) to work for the customer objects.

    Code:
    //a is the customer object in nodes
    bool BSTree::search(string x, char y) {
      Customer target = Customer(x,y,100);
        Node* leafPtr = root;
        while(leafPtr!=0){
          if(leafPtr->a == target){
        cout <<"returning true"<<endl;
        return true;
          }if(target > leafPtr->a){
          cout <<"checking >"<<endl;
          leafPtr = leafPtr->right;
          }if(target < leafPtr->a){
          cout<<"checking <"<<endl;
          leafPtr = leafPtr->left;
          }
          
        }
        return false;//end of while loop
    }


    heres the test code i was using:


    Code:
    int main(){
      BSTree bst; 
      bst.insert("H",'h',100);
      bst.insert("B",'b',100);
      bst.insert("F",'f',100);
      bst.insert("I",'i',100);
    
      cout <<"Result"<< bst.search("F",'f')<<endl;
      return 0;
    }



    it keeps giving me false when i tried to check it.

    any help is much appreciated.

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    Have you overloaded correctly the > and < operators?
    Devoted my life to programming...

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    4
    Yep. Very certain that overloading those operators is the only correct thing ive done so far, sadly. Ive tested them once again and they work fine.

    however, after doing some tests after insertion, it seems as though something might be going wrong.

    ive tried to print the root object, works fine, then i move a pointer from the root to its left (where the "B", 'b' object should be located) and its telling me 'segmentation fault' - im running this in linux. so its not there even though ive allocated new memory for it... heres that insertion code:

    Code:
    bool Tree::insert(string a, char b, int c) {
      
      Node* leaf = new Node(Customer(a,b,c));
      if(root == NULL){
        root = leaf;
        cout << "insertion complete for "<<root->a<<endl;
        return true;
      }else{
        Node* leafPtr = root;
        while(leafPtr!=NULL){
          if((leaf->customer) > (leafPtr->customer)){
        leafPtr = leafPtr->right;
          }else{
        leafPtr = leafPtr->left;
          }
        }
        leafPtr = leaf;
        cout << "insertion complete for "<<leaf->customer<<endl;
        
        return true;
      }
      
    }

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    4
    just a side note that ive changed 'BSTree' to 'tree' and 'a' to 'customer' when trying to mix variables around during testing just now. the code is still the same though.

  5. #5
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    I spotted your problem. You see, by doing "leafPtr = leaf;" you're not actually changing anything in the binary tree, because you only alter the LOCAL pointer.
    shocklightning likes this.
    Devoted my life to programming...

  6. #6
    Registered User
    Join Date
    Mar 2012
    Posts
    4
    Thanks a ton! Fixed it, seems to be working.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree Delete Method
    By pobri19 in forum C# Programming
    Replies: 2
    Last Post: 09-26-2008, 09:43 AM
  2. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  5. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21