C++

Forum

 
Binary Search Tree - searching func

Mar 24, 2012 at 11:54pm
shocklightning (24)
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)! ive 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.

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

bool Tree::search(string a, char b) {
  Customer target = Customer(a,b,100);
    Node* leafPtr = root;
    while(leafPtr!=0){
      if(leafPtr->customer == target){
	cout <<"returning true"<<endl;
	return true;
      }if(target > leafPtr->customer){
	  cout <<"checking >"<<endl;
	  leafPtr = leafPtr->right;
      }if(target < leafPtr->customer){
	  cout<<"checking <"<<endl;
	  leafPtr = leafPtr->left;
      }
      
    }
    return false;//end of while loop
}


heres the test code i was using:
1
2
3
4
5
6
7
8
9
10
 
int main(){
  Tree 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 gave me false for that one when i tried to check it. any help is much appreciated.
Last edited on Mar 25, 2012 at 4:27am
Mar 25, 2012 at 12:15am
liquidfuzz (78)
Pardon me, but binary tree. Is there suppose to be any recursive function..?

search(){
if(statment){ return something;} else {search();}
}
Mar 25, 2012 at 12:40am
shocklightning (24)
oh godness, youre right about the recursive part. i was so fixated on trying to get it to just work... but even without recursion, shouldnt this work? or is it because its not recursive that it isnt working? :\
Mar 25, 2012 at 12:42am
liquidfuzz (78)
What search algorithm are you planning to use?
Mar 25, 2012 at 12:52am
shocklightning (24)
binary search....assuming the root is not null, if the target is greater than the root, go right, if less than, go left etc and keep going until you find it or atleast reach the point where it should be.

just as a side note (i realize ive left this out) each customer has a first name/last name and ive overloaded the comparison operators to compare them alphabetically, last name first.
Last edited on Mar 25, 2012 at 12:52am
Mar 25, 2012 at 1:09am
shocklightning (24)
...or were you asking about the traversal method?
Mar 25, 2012 at 1:10am
liquidfuzz (78)
Ops, you run the recursion in a while loop. I messed that. Sorry!

You need to cout stuff the see what's going on.
Mar 25, 2012 at 1:21am
shocklightning (24)
oh good -phew- i was wondering how i was going to do that if i wasnt already doing it.

i am cout-ing each case. it only goes to the ' cout<<"checking <"<<endl;' one, never anything else. even if i change the target.

are my if statements wrong? i even tried using else if but it didnt help, output was still the same, giving me false for any case i entered.
Mar 25, 2012 at 2:47am
ne555 (10692)
Maybe the problem is in the insert method. Check if the tree is properly constructed.
Also, it wouldn't hurt to see what you are comparing
Mar 25, 2012 at 4:12am
shocklightning (24)
my insert method is like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 

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;
  }
  
}


i had cout statements for that to make sure it entered the loop, it seemed to output the correct code to me.....is it not doing it right?

im comparing the names of the customers. so "F", 'f' is greater than "A",'a', alphabetically, im 100% sure that they are being compared correctly.
Mar 25, 2012 at 3:41pm
ne555 (10692)
You are not linking the nodes. Your code is equivalent to 
1
2
3
4
5
6
7
8
9
10
11
12
 
bool Tree::insert(string a, char b, int c) {
  Node* leaf = new Node(Customer(a,b,c));
  if(root == NULL){
    root = leaf; //fine
    return true;
  }else{
    Node* leafPtr = root;
    leafPtr = NULL; //that's what your loop is doing
    leafPtr = leaf;
    return true;
  }
}
So as you can see, you are stopping too late.
Mar 26, 2012 at 4:42am
shocklightning (24)
ah, thanks a ton! fixed it.
Topic archived. No new replies allowed.