Re: How to sum the determination of a pointer(s)
ajj@rextrax.com wrote:
Hello All,
Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.
I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???
Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.
template <typename T>
int countOneChild(tnode<T> *t)
{
int oneChildCount, leftChildCount, rightChildCount;
if (t != NULL) // If it were NULL there would be no one child
nodes!
{
countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;
}
}
Calling Function is
cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;
I would appreciate any help, Thanx in advance,
A.J. Johnston
I'm not surprised since you haven't initialised any of the local
variables. The compiler will allocate storage for them but the value
can be anything and you want them all to be specifically 0, at least
initially. Declare them like this:
int oneChildCount(0);
int leftChildCount(0);
int rightChildCount(0);
This will guarantee that the counts have sensible values on function
entry.
Why have you declared leftChildCount and rightChildCount when they do
not appear to be used within the function?
oneChildCount does not appear to be incremented anywhere. Presumably,
you want to count the number of tree nodes having just one child? As
far as I can see oneChildCount will either have a nonsense value or 1
for each recursive invocation of countOneChild whereas it should be
zero initially and then increment for each tnode having only one child.
The function would then return 0 (there are no one child nodes) or some
positive number equal to the number of one child nodes in the tree.
There is also no return statement at the end of the function. What
happens if t happens to be zero? What value is returned? There is no
gurantee that the function will return anything sensible.
The function does not modify a tnode so why isn't the argument declared
as tnode<T> const* instead of tnode<T>* ?
I wouldn't use a plain int here since: a) you don't know its size and
it might overflow for large trees; and b) it's not really what you
want. What you want is a count type - yes it's a number but it's closer
to the problem domain. I would do something like:
typedef std::size_t TreeNodeCount;
and then declare the function to be of type TreeNodeCount. You could do
this like this:
template <typename T>
TreeNodeCount countOneChild (TreeNode<T> const& treeNode);
since countOneChild will never modify a tree node and, presumably, will
not alter the internal state of the class. Note that I have used a
reference rather than a pointer here. You would need to modify the code
to take account of that or just use the pointer.
Why are you using the NULL macro? There is no need to since the
standard guarantees that binary 0 is compatible with any pointer. NULL
is a hangover from C and this is C++.
I haven't gone through the other code but hopefully this will help.
Best regards
Jim Bannon.