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 [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
-~----------~----~----~----~------~----~------~--~---
