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;
>> }
>>
>> Lets say you want to visit every node and call foo() on the value.
>> Recursive solution
>>
>> void walkTree(Node *cur){
>> if(cur == NULL)
>> return;
>> foo(cur->value);
>> walkTree(cur->leftChild);
>> walkTree(cur->rightChild);
>> }
>
> 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 :)
>> An iterative solution
>>
>> void walkTree(Node *head){
>> if(head == NULL)
>> return;
>> stack toCheck;
>> toCheck.push(head);
>> while(toCheck.size()>0){
>> Node* cur =toCheck.pop();
>> foo(cur->value);
>> if(cur->leftChild != NULL)
>> toCheck.push(cur->leftChild);
>> if(cur->rightChild != NULL)
>>
>> toCheck.push(cur->rightChild);
>>
>> }
>> }
>
> 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. In general, I
believe in removing bad data points as early as possible. Although your
version is a closer approximation of the recursive algorithm.
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 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.
Gabe
_________________________________________________________________
Climb to the top of the charts! Play the word scramble challenge with star
power.
http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_jan--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
