binary search tree find

[maverick786]

My program is required to build a binary search tree using integers inputted from a file. It also searches for items and counts the nodes accessed in each search. Also it needs to calculate the average number of comparisons per search. I am not sure where to insert the counts because it seems I am getting the wrong count. Here is my retrieve function:

int Retrieve(TreeNode* tree, 
     ItemType& item, bool& found, int& num)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item's,
//       found is true and item is set to a copy of someItem; 
//       otherwise found is false and item is unchanged.
{
  //int counter=0;
  if (tree == NULL)
  {
    found = false;                     // item is not found.
    return num=0;
  } 
  else if (item < tree->info)      
  {
     Retrieve(tree->left, item, found, num); // Search left subtree. 
     num=num+1;
  }
  else if (item > tree->info)
  {
     Retrieve(tree->right, item, found, num);// Search right subtree.
     num = num+1;
  }
  else
  {   
      item = tree->info;                 // item is found.
      found = true;
  
      
  }

Thanks

[Lerner]

First, I assume that num represents the number of nodes visited during the search process. If so, I'd assign num the value of zero inside the calling function and increment the value by one, outside of the if/else statements, each time the function is called. If num isn't assigned the value of zero before you do one of these lines:

num = num +1;

then num is just going to be junk and that may account for the erroneous value returned.

In addition, since num is passed by reference you don't need to return it which means you could give the function a return type of void.

The instructions do seem a bit ambiguous to me, however, because instead of calculating the average number of nodes visited and therefore compared with the desired search value, I suppose it could want the average number of a comparison operators, such as == or < or >, used during the search (which could range anywhere from 1 to 4 comparisons per node evaluated). To calculate the number of camparison operators used during the search, if that's what's required, I would pass a variable called operatorCount by reference to the function and increment it within each of the if and else if statements (else statements are the default and don't need to use any of the comparison operators). I'd increment operatorCount by 1 if tree == NULL, by 2 if item < tree->info, and by 3 if item > tree->info.

Last, but not least this line assigns the value of tree->info to item, not compare the values of the two to see if item equals tree->info as implied by the comment.

item = tree->info;                 // item is found.

However, since else is the default state, you can assume the two values are equal since you wouldn't get there if the node had no value or if one of the inequality comparisons were true. Therefore, you can leave this line out completely if you want.