C++

Forum

 
little recursion question

dschwart (8)
I am a beginner. I have given myself a little recursion exercise. I have a binary search tree. I want to write a function that tells me if a particular value is in the tree.

So far, my function tells me if the value is present. But it fails if the value is not present.

1
2
3
4
5
6
7
8
9
 
bool Search_Tree(node * ptr_to_tree, int number) {
   if (ptr_to_tree->i == number)
      return true;

   if (ptr_to_tree->i <= number)
      Search_Tree(ptr_to_tree -> ptr_to_left, number);
   else
      Search_Tree(ptr_to_tree -> ptr_to_left, number);
}


I just can't see where to put 
 
 
return false;

Can someone point that out to me?
tcs (519)
If your pointer is NULL --> FALSE
dschwart (8)
OK, my code now looks like this
1
2
3
4
5
6
7
8
9
10
11
 
bool Search_Tree(node * ptr_to_tree, int number) {
   if (ptr_to_tree == 0)
      return false;
   if (ptr_to_tree->i == number)
      return true;

   if (number <= ptr_to_tree->i)
      Search_Tree(ptr_to_tree -> ptr_to_left, number);
   else if (number > ptr_to_tree->i)
      Search_Tree(ptr_to_tree -> ptr_to_right, number);
}

And behaves as expected.
But at compile time, I get a warning (not all control paths return a value). How can I resolve that warning?
Chervil (7320)
If the function calls itself recursively, the value returned should be used in some way. I've not analysed this code in detail, and my code may be incorrect, but it seems that it might look something like this:

1
2
3
4
5
6
7
8
9
10
11
 
bool Search_Tree(node * ptr_to_tree, int number) {
   if (ptr_to_tree == 0)
      return false;
   if (ptr_to_tree->i == number)
      return true;

   if (number <= ptr_to_tree->i)
      return Search_Tree(ptr_to_tree -> ptr_to_left, number);
   else  // note "else if" changed to "else"
      return Search_Tree(ptr_to_tree -> ptr_to_right, number);
}
dschwart (8)
OK, that was a good suggestion and the warning is now gone.
Can we look at another procedure that is confusing me?

Show_Tree just displays the values in all nodes in the tree. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void Show_Tree(node * ptr_to_tree) {
  /*
   if (ptr_to_tree == 0) {
      printf("The tree is empty.\n\n");
      return;
   }
   */
   
   if (ptr_to_tree == 0)
      return;
   
   Show_Tree(ptr_to_tree -> ptr_to_left);
   printf("%d\n", ptr_to_tree -> i);
   Show_Tree(ptr_to_tree -> ptr_to_right);   
}

The following code is necessary:
1
2
 
if (ptr_to_tree == 0)
   return;

But then I thought it would be nice to display a message if the tree is empty. So, I replaced that code with:
1
2
3
4
 
if (ptr_to_tree == 0) {
   printf("The tree is empty.\n\n");
   return;
}

But if the tree is not empty, the results are different and not good. (Displays "The tree is empty." before each value. ugh.) If the tree is empty, the message displays just fine.
Assuming that it is possible to display a 'tree is empty' message if the tree is empty, and then stop all processing in the procedure, how would I do that?
Last edited on
Topic archived. No new replies allowed.