Anyone can help with writing recursive functionthat determines the level in the
Hello everyone :)
I want to learn how can I do this :
write a recursive function member level() for class template BST that determines the level in the BST at which a specified item is located .The root of the BST is at level 0 , its children are at level 1 , and so on
and this is the code for //-- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
BST<DataType>::BinNodePointer locptr = myRoot;
bool found = false;
for (;;)
{
if (found || locptr == 0) break;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found;
}
[922 byte] By [
Rooro] at [2007-11-11 9:57:35]
# 1 Re: Anyone can help with writing recursive functionthat determines the level in the
By the way ... your search procedure is not recursive. If you want recursive, you'll need to be calling search() with both the item you are trying to find and the pointer to the node of interest. Your base case is
if( found ) return true.
You can use your basic search procedure (modified to take a node pointer with the item) to be called within a
int findLevel( item, nodePointer )
procedure.
Now you just need to add a counter - create a data member which starts at 0, which you increment it each time you call search. When the search returns "found", you can then print the value of the variable.
if( found ) return 1, else return (1 + findLevel( item, childNodePointer) )
nspils at 2007-11-11 20:59:43 >
# 2 Re: Anyone can help with writing recursive functionthat determines the level in the
i'n not getting it well :(
template <typename DataType>
int BST<DataType>::search(const DataType & item) const
{
locptr = myRoot;
int count=0;
if (locptr == 0) return(count);
int countL=0, countR=0;
search(item < locptr->data )
countL++;
search( locptr->data < item)
countR++;
if (countL>countR)
return(countL);
else
return(countR);
}
<<< many things missings , i do not know how can I do it ...
----
int Level( item, nodePointer )
{
int count=0;
if (nodePointer = item )
return 1;
else
{
int count++;
(1 + Level( item, childNodePointer) )
}
return(count);
}
realy i'm confusing with it :(
Rooro at 2007-11-11 21:00:48 >
# 3 Re: Anyone can help with writing recursive functionthat determines the level in the
Yup, it looks like you're confused.
I think I may have led you astray ... it might be more direct to have the search procedure increment ONE global int counter variable which is initialized at 0 - each time the search procedure is called it will increment the value of that variable.
I don't know why you have a "countR" and "countL" - and then compare the two and report back only one ... I don't get the logic of that.
In addition, I would alter the parameters of the search procedure to take a node pointer as an argument as well as the value being searched for. This is the way you can implement a RECURSIVE function which is part of your inquiry.
nspils at 2007-11-11 21:01:49 >
