Hi,
You are right. Thank you for the correction. Actually the error is
because of the ignorance of the fact that not only the info about the left
and right child are important but also the order in which the elements in
the stack are pushed.
So instead of having two stacks, this can be implemented by storing some
extra info regarding the child when a node is pushed in the stack.
I tried my algo and the code goes here...
/* program to print the post order traversal of given binary tree without
using recursion */
# include <stdio.h>
# include <errno.h>
# include <stdlib.h>
# define MAX_DEPTH 128
# define LEFT 0
# define RIGHT 1
typedef struct _Node
{
int data ;
struct _Node *left, *right ;
} Node ;
typedef struct _stackElement
{
Node *value ;
char childPending ; /* LEFT implies both LEFT and RIGHT are pending */
} StackElement ;
static StackElement stack[ MAX_DEPTH ] ;
static top = -1 ;
void buildBinaryTree( char *msg, int data, Node ** root ) ;
void printPostOrder( Node *root ) ;
void push( Node *value, char childPending ) ;
StackElement *pop( void ) ;
int stackNotEmpty( void ) ;
int main( void )
{
Node *root ;
buildBinaryTree( "Enter the value of root: ", 0, &root ) ;
printPostOrder( root ) ;
return 0 ;
}
void buildBinaryTree( char *msg, int data, Node **root )
{
printf( msg, data ) ;
scanf( "%d", &data ) ;
if( data == 0 )
{
*root = NULL ;
return ;
}
if( ( *root = ( Node * )malloc( sizeof( Node ) ) ) == NULL )
{
perror( "malloc( )" ) ;
exit( errno ) ;
}
( *root )->data = data ;
buildBinaryTree( "Left of %4d is: ", data, &( ( *root )->left ) ) ;
buildBinaryTree( "Right of %4d is: ", data, &( ( *root )->right ) ) ;
}
void printPostOrder( Node *root )
{
StackElement *tmp ;
while( root )
{
if( root->left != NULL )
{
push( root, LEFT ) ;
root = root->left ;
}
else if( root->right != NULL )
{
push( root, RIGHT ) ;
root = root->right ;
}
else
{
printf( "%d ", root->data ) ;
root = NULL ;
while( stackNotEmpty( ) )
{
tmp = pop( ) ;
if( ( tmp->childPending == LEFT ) && ( tmp->value->right ) )
{
push( tmp->value, RIGHT ) ;
root = tmp->value->right ;
break ;
}
printf( "%d ", tmp->value->data ) ;
}
}
}
putchar( '\n' ) ;
}
void push( Node *value, char childPending )
{
if( top >= MAX_DEPTH-1 )
{
fprintf( stderr, "push : Stack Overflow.\n" ) ;
exit( -1 ) ;
}
++top ;
stack[top].value = value ;
stack[top].childPending = childPending ;
}
StackElement *pop( void )
{
if( top < 0 )
{
fprintf( stderr, "pop : Stack Underflow.\n" ) ;
exit( -1 ) ;
}
return stack + top-- ;
}
int stackNotEmpty( void )
{
return top >= 0 ;
}
Correct me if I'm wrong.
Thanks and Regards,
K.V.Chandra Kumar.
On 09/09/2007, Phani Kumar Ch. V. <[EMAIL PROTECTED]> wrote:
>
> Hi Chandra,
>
> First of all Post-order is not the one which prints root first and then
> its children.
> Post order means first processing of left and right subtree's and then the
> data in the node. For eg:
>
> 1
> 2 3
> 4 5 6 7
>
> Post order is: 4 5 2 6 7 3 1
> Pre order is: 1 2 4 5 3 6 7
>
> So, think if your solution works for the post order.
>
> Regards
> Phani
> On 9/9/07, chandra kumar <[EMAIL PROTECTED]> wrote:
> >
> > 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
> > > >
> > > >
> > > >
> >
> >
> >
> >
>
>
> --
> 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
-~----------~----~----~----~------~----~------~--~---
