HI,
I think the following solution will solve the problem. It's not as
elegant as the previous one but a straight forward try.
post_order( root )
{
while( root != NULL )
{
if( root->left != NULL )
{
push( LeftStack, root ) ;
root = root->left ;
}
else if( root->right != NULL )
{
push( RightStack, root ) ;
root = root->right ;
}
else
{
print( root ) ;
while( stackNotEmpty( RightStack ) )
print( pop( RightStack ) ;
while( stackNotEmpty( LeftStack ) )
{
root = pop( LeftStack ) ;
if( root->right != NULL )
break ;
print( root ) ;
}
if( root->right != NULL ) // break ;
{
push( RightStack, root ) ;
root = root->right ;
}
else
root = NULL ;
}
}
}
Correct me if I am wrong.
Thanks and Regards,
K.V.Chandra Kumar.
On 09/09/2007, chandra kumar <[EMAIL PROTECTED]> wrote:
>
> Hi,
> But in your second while( ) loop when the check 'root->left = NULL'
> executes 'root' is already NULL, because only then the first loop
> terminates. So you need to insert the following statement inbetween the
> loops
>
> root = pop( )
>
> Also your solution assumes that the value at the nodes are of 'single
> character'. Say, if the values are of multiple character strings, then
> instead of 'string_reverse( )' the function 'reverse_words_in_string( )'.
>
> Other than this the solution should be perfect. Correct me if I'm
> wrong.
>
> Thanks and Regards,
> K.V.Chandra Kumar.
>
> On 07/09/2007, anshu <[EMAIL PROTECTED]> wrote:
> >
> >
> > 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
-~----------~----~----~----~------~----~------~--~---
