> 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<Node*> 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<Node *> 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<Node*> 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
_________________________________________________________________
Need to know the score, the latest news, or you need your Hotmail®-get your
"fix".
http://www.msnmobilefix.com/Default.aspx
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
