Re: How to sum the determination of a pointer(s)
ajj@rextrax.com wrote:
Jim, you have some good points
Declare them like this:
int oneChildCount(0);
Done.
> Why have you declared leftChildCount and rightChildCount when they
do
not appear to be used within the function?
These variables have been deleted, they were used in a former version
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.
I am now incrementing oneChildCount as follows
oneChildCount++;
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.
I am using the statement
return oneChildCount;
The function does not modify a tnode so why isn't the argument declared
as tnode<T> const* instead of tnode<T>* ?
Defined parameter. May not be modified.
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.
I have successfuly implemented a solution in this fashion (the one with
a reference) however, I am unable to find a solution with the
requirements listed below.
Write a function
template <typename T>
int countOneChild(tnode<T> *t);
that counts the number of interior nodes in a binary tree having one
child.
If you look at the previous code you will see that these nodes can be
identified as well as the tree traversal through the output. The
problem is the sum algorithm. Why am I able to correctly identify a
one child node, increment a variable, only to have that variable
reinitialized to zero? What am I failing to understand about pointers?
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++.
Good to know :)
Good point!
Eradicated
There are no compilation errors
Any more help would be wonderful!!!
Sincerely,
Aaron Johnston
Aaron,
I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like
static int oneChildCount(0);
should solve the problem. This means that whenever we execute the
statement ++oneChildCount; it is the static variable that is being
updated preserving its value across recursive invocations. The final
statement in the function should then be return oneChildCount;
What's worrying me though is what happens when we call the function
again with a different node. Since this would effectively be a new
execution environment it should reset oneChildCount but I'm not sure.
Any expert opinion please?
P.S. I would modify the function slightly to eliminate the 2 simplest
cases first: a null node; and a node with no children. I would do this
before attempting a recursive call like this:
if (t == 0)
{ // empty tree
return 0;
}
if ((t->left == 0) && (t->right ==0))
{ // single node with no children
return 0;
}
Also, if we want to be "cute" we can take advantage of the
short-circuit nature of boolean operators in C++ (assuming they haven't
been overloaded for this class) and collapse the two tests into 1 as
follows:
if ((t == 0) || ((t->left == 0) && (t->right == 0)))
return 0;
Note how we can get way with this here because short-circuit rules
guarantee left-to-right evaluation order. In other languages where
short-circuit evaluation is not done this would likely generate a core
dump since the second half of the expression might be referencing
through a null pointer if t is actually 0.
Of course this violates the one-entry : one-exit rule of structured
programing and your teacher might not find that acceptable. He / she
might not accept relying on short-circuit evaluation order either since
it may cause confusion in other circumstances (remember that in general
C++ does not guarantee that an arbitrary expression will be evaluated
in a specific order). Don't do this if you're in any doubt about what
your teacher will accept!
Hope this helps.
Cheers
Jim.