Tuesday, November 19, 2013

Breadth First Traversal and Size of Tree (Non Recursive version)

typedef struct que {
    int front;
    int rear;
    Node **array;
}Que;

 Que * CreateQue(void)
{
    Que * temp = (Que *) malloc (sizeof(Que));
    temp->front = -1;
    temp->rear = -1;
    temp->array = (Node **) malloc (SIZE * sizeof (Node *));
    return temp;
}

void  enQue (Que *que, Node *temp )
{
    // Generally for Que for a EnQUe op
    // only rear gets changed. (added at end)
    //
    // this is a array which we wnat to manage
    // as a circular array
    que->rear = (que->rear + 1) % SIZE;
    que->array[que->rear] = temp;

    if(que->front == -1)
        que->front = que->rear;
}
 Node * deQue (Que *que)
{
    Node *temp = que->array[que->front];

    if (que->front == que->rear) {
        que->front =-1;
        que->rear = -1;
    }
    else
      que->front = (que->front+1) % SIZE;
    return temp;
}

 int isEmpty (Que *que)
{
    return (que->rear == -1);
}

//Non Recursive Size using BFS Traversal
 int bfs_size (Node *root)
{
    Node *temp = NULL;
    int count =0 ;

    //if tree is null return
    if (!root)
        return 0;

    //Create a Queue and push root
    Que *Q = CreateQue();
    enQue(Q,root);

    //Loop while Queue is not empty
    while (!isEmpty(Q))
    {
        temp = deQue(Q);
        printf(" %d ",temp->data);
        count++;
        if(temp->left)
            enQue(Q,temp->left);
        if(temp->right)
            enQue(Q,temp->right);
    }
    return count;
}

int main ()
{
    Node *root = addNode(1);
    root->left = addNode(2);
    root->right = addNode(3);
    root->left->left  = addNode(5);
    printf("size of binary tree is %d\n",bfs_size(root));
    return 0;
}

1 comment:

  1. sbobet.com | Sbobet.com || Login - thauberbet.com
    sbobet.com is a sports betting sbobet ทางเข้า portal offering sports betting ミスティーノ and casino games. You can get betting vua nhà cái information on popular sports like football,

    ReplyDelete