binary search trees

[j_depp_99]

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 in advance.

 

[Paavo Helde]

(e-mail address removed) wrote in (e-mail address removed):

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:

[/QUOTE]

For such problems it is most instructive to step through the code in the 
debugger and see what's happening. As you did not state what results you 
got and what you expected I can only point out some suspicious lines in 
the code:
[QUOTE]
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.[/QUOTE]

Return value and num parameter not documented.
[QUOTE]
{
//int counter=0;
if (tree == NULL)
{
found = false;                     // item is not found.
return num=0;[/QUOTE]

This clears the num count and returns 0, possibly not what you wanted?
[QUOTE]
}
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;[/QUOTE]

This does not update num, correct?
   [QUOTE]
}
[/QUOTE]

No return value here!
[QUOTE]
}

Thanks in advance.

 

[j_depp_99]

(e-mail address removed) wrote in (e-mail address removed):

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:

[/QUOTE]

For such problems it is most instructive to step through the code in the
debugger and see what's happening. As you did not state what results you
got and what you expected I can only point out some suspicious lines in
the code:
[QUOTE]
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.[/QUOTE]

Return value and num parameter not documented.
[QUOTE]
{
  //int counter=0;
  if (tree == NULL)
  {
    found = false;                     // item is not found.
    return num=0;[/QUOTE]

This clears the num count and returns 0, possibly not what you wanted?
[QUOTE]
  }
  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;[/QUOTE]

This does not update num, correct?


[QUOTE]
  }[/QUOTE]

No return value here!


[QUOTE]
}

Thanks in advance.- Hide quoted text -

- Show quoted text -

Thanks. Let me correct that and get back to you.