Hi,
Need more details about explored( Node * ) function,
Consider the "NULL" input
if your explored( NULL ) returns "true" then I guess that every thing
works fine, and also most of your checks could be eliminated ( code will
become simpler )
if your explored( NULL ) returns "false", then the same case as in my
previous mail will result in wrong answer.
* if((s->left == null && s->right==null)
||(explored(s->left)&&explored(s->right)) *
* ---as s->left == null && explored( s->right ) ( and vice versa
are not there )*
Correct me if I'm wrong.
Thanks and Regards,
K.V.Chandra Kumar.
On 28/08/07, MD <[EMAIL PROTECTED]> wrote:
>
>
> I think first s=pop() in while is not the right approach. This is an
> alternate approach where explored() checks if the node is visited or
> not... hence discarding that path.. and I think the following handles
> the null conditions as well.. (ex given by chandra)
>
> void postOrderTraversal(Tree *root)
> {
> node * previous = null;
> node * s = root;
> push(s);
>
> while( stack is not empty)
> {
> if(s->left && !explored(s->left)) //explored check if the node was
> previously visited
> {push(s->left);
> s=s->left}
> else
> {if(s->right && !explored(s->right))
> {push(s->right);
> s=s->right;}
> }
>
> if((s->left == null && s->right==null) ||(explored(s-
> >left)&&explored(s->right)) //last level-child or both childern are
> explored
> { s = pop(); //
> print(s->data);
> s= pop(); //POP Again....point s to next element.
> }
> }//end of while
>
> }
>
> On Aug 24, 6:17 am, "Phani Kumar Ch. V." <[EMAIL PROTECTED]> wrote:
> > Hi all,
> >
> > Please let me know if this pseudo code gives correct solution for
> iterative
> > post-order traversal of a binary tree.
> > ----------------------------------------------------
> > void postOrderTraversal(Tree *root)
> > {
> > node * previous = null;
> > node * s = null;
> > push(root);
> > while( stack is not empty )
> > {
> > s = pop();
> >
> > if(s->right == null and s->left == null)
> > {
> > previous = s;
> > process node s;
> > }
> > else
> > {
> > if( s->right == previous or s->left == previous )
> > {
> > previous = s;
> > process node s;
> > }
> > else
> > {
> > push( s );
> > if(s->right) { push(s->right); }
> > if(s->left) { push(s->left); }
> > }
> > }}
> >
> > -----------------------
> > Regards
> > Phani
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
