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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.