begin quoting Gabriel Sechan as of Fri, Jan 25, 2008 at 05:02:02PM -0600:
>
> Resend due to hotmail sucking. Maybe I'll try and get that email
> server running this weekend. Crossing my fingers
>
> > From: [EMAIL PROTECTED]
> >> begin quoting Gabriel Sechan as of Fri, Jan 25, 2008 at 02:39:05PM -0600:
> >> struct Node {
> >> int value;
> >> Node *leftChild;
> >> Node *rightChild;
> >> }
> >>
[chop]
> > Note that this assumes that the root of the tree is a Node, rather
> > than having a Tree structure and a TreeNode structure, which can be
> > rather useful.
> >
>
> Or that we're in a helper function called by the tree structure's walk
> function- which is how I've coded it in the past. This was a quickie
> example program :)
Heh.
A good one for discussion, anyway.
[chop]
> > Um, no need to keep checking for NULL, that's making the code more
> > complicated than necessary. You waste a little space, unless your
> > stack implementation is smart enough to ignore pushes of NULL.
> >
> > void walkTree( Node *head) {
> > Node *current;
> > stack pending;
> >
> > pending.push( head );
> > while( ! pending.isEmpty() ) {
> > if ( NULL == ( current = pending.pop() ) ) continue;
> > foo( current->value );
> > pending.push( current->leftChild );
> > pending.push( current->rightChild );
> > }
> > }
> >
> > Branches impair readability, they should be minimized.
>
> Disagree. The idea of everything in the stack needs to be processed
> is far easier to understand and maintain than that most items in the
> stack need to be processed, but sometimes you have something that
> doesn't.
I don't concur that it's "far easier". But then, what I consider easy
and what I consider not easy don't always line up with everyone else.
> In general, I believe in removing bad data points as early
> as possible. Although your version is a closer approximation of the
> recursive algorithm.
Yah, we could've written the recursive algorithm:
void walkTree( Node *head ) {
if ( head == NULL ) return;
foo ( head->value; )
if ( head->leftChild != NULL ) {
walkTree( head->leftChild );
}
if ( head->rightChild != NULL ) {
walkTree( head->rightChild );
}
}
But it isn't so pretty anymore. Thus, my assertion that branches ought
to be minimized ought to stand.
To address your "always process something" preference, and presuming
that a stack will hold NULLs and doesn't have a pushIfNotNull, adding
an else might help:
void walkTree( Node *head) {
Node *current;
stack pending;
pending.push( head );
while( ! pending.isEmpty() ) {
if ( NULL == ( current = pending.pop() ) )
continue;
} else {
foo( current->value );
}
pending.push( current->leftChild );
pending.push( current->rightChild );
}
}
Personally, I find that while this makes it clearer that "everything
on the tree is operated on", it's less clear overall.
> I could see writing a pushIfNotNull function and calling that though-
>
> void PushIfNotNull(stack *target, Node *value){
> if(value != NULL)
> target->push(value);
> }
>
> void walkTree(Node *head){
> stack pending;
> Node *current;
>
> pushIfNotNull(pending, head);
> while( !pending.isEmpty()){
> current = pending.pop();
> foo(current->value);
> pushIfNotNull(pending, current->leftChild);
> pushIfNotNull(pending, current->rightChild);
> }
> }
>
> Which actually makes it look a lot more like the recursive
> version.pushIfNotNull, of course, could be expanded to take a value to
> check instead of assuming NULL and work on a terminated tree. If you
Yup.
There's not a lot of difference between the two now. :)
> want to go really berserk and generic, you could make pushIf take a
> stack and a function to call, pushing the value only if the function
> evaluates to true. Or even better, make it take an iterator instead
> of a stack. Although thats really overkill, and would probably make
> your walkTree function harder to read, not easier.
Yup.
--
Nonrecursive programming without a stack
Is a pain in the, erm, um... lower back.
Stewart Stremler
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
