An alternative algorithm that works without the explored() function could be as under. Just written a rough algorithm, there are a few more optimizations in loop possible,.. The basi idea used here is - Post order mean "Data-Left-Right" If pre-order algorithm be executed with the difference that instead of left we explore right. The final order obtained when reversed will give post order.
post_order(root) { string_reverse( func(root)); } func(root) { do { while(root != NULL) { print(root->data); push(root); root=root->right; } while( root->left=NULL || stack ! empty) root=pop() if(root->left !=NULL) { root=root->left } }while( stack ! empty); } On Aug 28, 8:39 am, "chandra kumar" <[EMAIL PROTECTED]> wrote: > 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---