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; }
Tuesday, November 19, 2013
Breadth First Traversal and Size of Tree (Non Recursive version)
Labels:
Binary Tree,
Data Structure
Subscribe to:
Post Comments (Atom)
sbobet.com | Sbobet.com || Login - thauberbet.com
ReplyDeletesbobet.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,