On Jun 16, 3:01 pm, divya <[email protected]> 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 [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?hl=en.
