/* Assuming you have a stack setup with push() and pop() operations. Also assuming that all nodes are initially marked to 0. (This function will reset them back to zero when finished) */ void postorder(Node *n) { push(n);
while (stack.size > 0) { n = (Node*)pop(); if (n->marked || (n->left == NULL && n->right == NULL)) { n->marked = 0; printf("%d\n", n->value); } else { n->marked = 1; push(n); if (n->right) push(n->right); if (n->left) push(n->left); } } } is the above solution fine for postorder. plz let me knw if there is any mistake........ On 17 June 2010 10:37, Gene <gene.ress...@gmail.com> wrote: > On Jun 16, 3:01 pm, divya <sweetdivya....@gmail.com> wrote: > > plz give algos of inorder, preorder nd post order tree traversal..non > > recursive one..using stack.. > > nd the tree is not threaded > > > #include <stdio.h> > #include <stdlib.h> > > typedef struct node_s { > int val; > struct node_s *left, *right; > } NODE; > > NODE *new(int val) > { > NODE *tree = malloc(sizeof(NODE)); > tree->val = val; > tree->left = tree->right = NULL; > return tree; > } > > void search(NODE *tree) > { > if (tree) { > printf("preorder %d\n", tree->val); > search(tree->left); > printf("inorder %d\n", tree->val); > search(tree->right); > printf("postorder %d\n", tree->val); > } > } > > // Direct conversion of recursive code to iteration. > struct stack_elt_s { > int site; > NODE *tree; > } stack[100]; > int sp = 0; > > void search_iterative(NODE *tree) { > start: > if (tree) { > printf("preorder %d\n", tree->val); > // simulate the recursive call search(tree->left) > stack[sp].tree = tree; > stack[sp++].site = 0; > tree = tree->left; > goto start; > L0: > printf("inorder %d\n", tree->val); > // simulate the recursive call search(tree->right) > stack[sp].tree = tree; > stack[sp++].site = 1; > tree = tree->right; > goto start; > L1: > printf("postorder %d\n", tree->val); > } > // simulate return to last call site > if (sp) { > tree = stack[--sp].tree; > switch (stack[sp].site) { > case 0: goto L0; > case 1: goto L1; > } > } > } > > int main(void) > { > struct node_s *n0 = new(0); > struct node_s *n1 = new(1); > struct node_s *n2 = new(2); > struct node_s *n3 = new(3); > struct node_s *n4 = new(4); > n0->left = n1; > n0->right = n2; > n1->left = n3; > n2->left = n4; > > printf("recusive:\n"); > search(n0); > > printf("\nnow iterative:\n"); > search_iterative(n0); > > return 0; > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.