By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,244 Members | 1,972 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,244 IT Pros & Developers. It's quick & easy.

binary search trees

P: n/a
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:
Expand|Select|Wrap|Line Numbers
  1.  
  2. int Retrieve(TreeNode* tree,
  3. ItemType& item, bool& found, int& num)
  4. // Recursively searches tree for item.
  5. // Post: If there is an element someItem whose key matches item's,
  6. //       found is true and item is set to a copy of someItem;
  7. //       otherwise found is false and item is unchanged.
  8. {
  9. //int counter=0;
  10. if (tree == NULL)
  11. {
  12. found = false;                     // item is not found.
  13. return num=0;
  14. }
  15. else if (item < tree->info)
  16. {
  17. Retrieve(tree->left, item, found, num); // Search left subtree.
  18. num=num+1;
  19. }
  20. else if (item tree->info)
  21. {
  22. Retrieve(tree->right, item, found, num);// Search right subtree.
  23. num = num+1;
  24. }
  25. else
  26. {
  27. item = tree->info;                 // item is found.
  28. found = true;
  29.  
  30.  
  31. }
  32.  
  33.  
  34. }
  35.  
Thanks in advance.
Mar 5 '08 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.