Question

Use C programming to Implement the breadth-first tree traversal. The tasks are:

a) Build the tree.

b) Perform breadth first traversal on the tree that you have built at step

a).

Note: "Please comment the program"

Answer 1

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

//Tree Structure

struct Tree {

struct Tree* left, *right;

int data;

};

//Queue Structure

struct QNode {

struct QNode* next;

struct Tree* BData;

};

//Queue front and rear pointers

struct Queue {

struct QNode* front, *rear;

};

//Creating a new queue Node

struct QNode* newQNode(struct Tree* data)

{

struct QNode* temp = malloc(sizeof(struct QNode));

temp->BData = data;

temp->next = NULL;

return temp;

}

//Creating a new Tree Node

struct Tree* CreateNode(int data)

{

struct Tree* temp = malloc(sizeof(struct Tree));

temp->data = data;

temp->left = temp->right = NULL;

return temp;

}

//Method to enqueue

void enQueue(struct Queue* q, struct Tree* data)

{

struct QNode* temp = newQNode(data);

if (q->front == NULL && q->rear == NULL)

{

q->front = q->rear = temp;

return;

}

q->rear->next = temp;

q->rear = temp;

}

//Method to pop or dequeue

struct Tree* pop(struct Queue* q)

{

if (q->front == NULL)

return NULL;

struct QNode* temp = q->front;

struct Tree* bdata = temp->BData;

q->front = q->front->next;

if (q->front == NULL)

q->rear = NULL;

return bdata;

}

int IsEmpty(struct Queue* q)

{

return (q->front == NULL && q->rear == NULL);

}

//breadthFirst method

void breadthFirst(struct Tree *root)

{

// Base Case

if (root == NULL)

return;

struct Queue* q = malloc(sizeof(struct Queue));

q->front = q->rear = NULL;

enQueue(q, root);

//Check if Queue is NOT Empty

while (!IsEmpty(q))

{

struct Tree* temp = pop(q);

printf("%d ", temp->data);

/* Enqueue left child */

if (temp->left != NULL)

enQueue(q,temp->left);

/* Enqueue right child */

if (temp->right != NULL)

enQueue(q,temp->right);

}

}

int main()

{

//Create Tree with 1 as root

struct Tree *root = CreateNode(1);

//2 as left child with 1 as root

root->left = CreateNode(2);

//3 as right child with 1 as root

root->right = CreateNode(3);

//4 as left of left child with 2 as parent

root->left->left = CreateNode(4);

//4 as right of right child with 3 as parent

root->left->right = CreateNode(5);

printf("\nBreadth First: ");

//Call BFS with root

breadthFirst(root);

return 0;

}

=====================================

SEE OUTPUT

PLEASE COMMENT if there is any concern.

=========================================