Tuesday, May 8, 2012

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