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