c - Iterative Inorder Traversal -
here function iterative inorder traversal. when execute i'm getting segmentation fault. i'm using stack traversal. in given program have recursive function inorder traversal check if create() function working.
i'm pushing node stack , moving left of node , after i'm popping node stack , printing , going right doing root=root->rlink.
#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *llink; struct node *rlink; }node; typedef struct stack { node *a[10]; int top; }stack; void push(stack *s,node *root) { if(s->top==9) printf("full"); else { s->top++; s->a[s->top]=root; } } node *pop(stack *s) { if(s->top==-1) printf("empty"); return s->a[s->top--]; } void inorder(node *root) { stack s; s.top=-1; int flag=1; while(flag) { if(s.top!=9) { push(&s,root); root=root->llink; } else{ if(s.top!=-1) { root=pop(&s); printf("%d",root->data); root=root->rlink; } else flag=0; } } } void inor(node *root) { if(root!=null) { inor(root->llink); printf("%d",root->data); inor(root->rlink); } } node *create(node *root,int key) { if(root==null) { root=(node *)malloc(sizeof(node)); root->data=key; root->rlink=root->llink=null; } else { if(key>root->data) { root->rlink=create(root->rlink,key); } else if(key<root->data) { root->llink=create(root->llink,key); } } return root; } int main() { node *h=null; h=create(h,5); h=create(h,1); h=create(h,3); h=create(h,8); h=create(h,12); h=create(h,51); inorder(h); //inor(h); }
as diagnosed in main comment, problem code didn't stop traversing leftwards when there no further node in direction. fix simple:
#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *llink; struct node *rlink; } node; typedef struct stack { node *a[10]; int top; } stack; static void push(stack *s, node *root) { if (s->top == 9) printf("full\n"); else { s->top++; s->a[s->top] = root; } } static node *pop(stack *s) { if (s->top == -1) printf("empty\n"); return s->a[s->top--]; } static void inorder(node *root) { stack s; s.top = -1; int flag = 1; while (flag) { //printf("i: %p\n", (void *)root); if (s.top != 9 && root != 0) { push(&s, root); root = root->llink; } else { if (s.top != -1) { root = pop(&s); printf(" %d", root->data); root = root->rlink; } else flag = 0; } } } static void inor(node *root) { if (root != null) { inor(root->llink); printf(" %d", root->data); inor(root->rlink); } } static node *create(node *root, int key) { if (root == null) { root = (node *)malloc(sizeof(node)); root->data = key; root->rlink = root->llink = null; } else { if (key > root->data) { root->rlink = create(root->rlink, key); } else if (key < root->data) { root->llink = create(root->llink, key); } } return root; } int main(void) { int nodes[] = { 37, 2, 19, 9, 7, 41 }; enum { num_nodes = sizeof(nodes) / sizeof(nodes[0]) }; node *h = null; h = create(h, 5); h = create(h, 1); h = create(h, 3); h = create(h, 8); h = create(h, 12); h = create(h, 51); printf("recursive:\n"); inor(h); putchar('\n'); printf("iterative:\n"); inorder(h); putchar('\n'); (int = 0; < num_nodes; i++) { h = create(h, nodes[i]); printf("iterative:\n"); inorder(h); putchar('\n'); } } i use static on functions because default compiler options require functions declared or defined before use, , static functions can defined without being pre-declared:
gcc -o3 -g -std=c11 -wall -wextra -werror -wmissing-prototypes -wstrict-prototypes -wold-style-definition it37.c -o it37 you can decide whether matters (but note no file other 1 needs access functions, 'information hiding' suggests functions should static).
sample output:
recursive: 1 3 5 8 12 51 iterative: 1 3 5 8 12 51 iterative: 1 3 5 8 12 37 51 iterative: 1 2 3 5 8 12 37 51 iterative: 1 2 3 5 8 12 19 37 51 iterative: 1 2 3 5 8 9 12 19 37 51 iterative: 1 2 3 5 7 8 9 12 19 37 51 iterative: 1 2 3 5 7 8 9 12 19 37 41 51
Comments
Post a Comment