can any one please tell me how to submit problems in the new acm
site?????
i am not able to figure it out !!!
On Sep 10, 8:50 pm, "chandra kumar" <[EMAIL PROTECTED]>
wrote:
> 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;
>
> ...
>
> read more >>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
