Print nodes in a Binary Tree [ Level wise ]
There are more then one ways to achieve this. But, the theme is to do BFS. Here is one of them. It is self-explanatory.
#include<stdio.h> #include<stdlib.h> struct node{ int data; struct node* left; struct node* right; }; struct node* queuePtr[100]; int front,end; struct node* getNode () { struct node *t = (struct node*) malloc(sizeof(struct node)); t->left = t->right = NULL; return t; } void print_BST_levelwise () { while (front < end) { if (queuePtr[front] != NULL) { if (queuePtr[front]->left == NULL && queuePtr[front]->right == NULL) { front++; continue; } //if (queuePtr[front]->left != NULL) { queuePtr[end++] = queuePtr[front]->left; //} //if (queuePtr[front]->right != NULL) { queuePtr[end++] = queuePtr[front]->right; //} } front++; } //Done with BFS... Now print int i,j,c; for(i=0 ; i<end ; i++) { if (queuePtr[i] != NULL) { printf("%d, ", queuePtr[i]->data); } else { printf("null, "); } } printf("\n\nLevelwise printing\n"); c=-1; for(i=0 ; i<end ; ) { c++; printf("Level [%d]:\t\t", c+1); for(j=0 ; j<(1<<c) ; j++) { if (queuePtr[i] != NULL) { printf("%d, ", queuePtr[i]->data); } else { printf("null, "); } i++; } printf("\n"); } } int main () { struct node* n1 = getNode(); struct node* n2 = getNode(); struct node* n3 = getNode(); struct node* n4 = getNode(); struct node* n5 = getNode(); struct node* n6 = getNode(); n1->data = 1; n1->left = n2; n1->right = n3; n2->data = 2; n2->left = n4; n2->right = n5; n3->data = 3; n3->left = NULL; n3->right = n6; n4->data = 4; n5->data = 5; n6->data = 6; /* How does the Tree look ? 1 / \ 2 3 / \ \ 4 5 6 */ front=end=0; queuePtr[end++] = n1; print_BST_levelwise(); free(n1); free(n2); free(n3); free(n4); free(n5); free(n6); return 0; }
No comments:
Post a Comment