Your task is to implement the following function in bst.c : void bstLevelOrder( struct node *t);
Question:
Your task is to implement the following function in bst.c
:
void bstLevelOrder(struct node *t);
This function should print the level-order traversal of the given BST on a single line separated by spaces (i.e., the same format as the other traverse-and-print functions). The following diagram aims to give an idea of how level-order traversal scans the nodes in a tree:
You must implement this algorithm by making use of the Queue ADT provided. Note that the Queue ADT stores pointers (void *
is a generic pointer type). This is because you should store node pointers in the queue rather than integers - if the queue stored integers then after dequeuing an integer, there would be no easy way to add its children to the queue.
// Prints the level-order traversal of the given BST
void bstLevelOrder(struct node *t) {
}
Queue.c
// Implementation of the Queue ADT using a linked list
// !!! DO NOT MODIFY THIS FILE !!!
#include
#include
#include
#include "Queue.h"
typedef struct node *Node;
struct node {
Item item;
Node next;
};
struct queue {
Node head;
Node tail;
int size;
};
static Node newNode(Item it);
/**
* Creates a new empty queue
*/
Queue QueueNew(void) {
Queue q = malloc(sizeof(*q));
if (q == NULL) {
fprintf(stderr, "couldn't allocate Queue\n");
exit(EXIT_FAILURE);
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
/**
* Frees all resources associated with the given queue
*/
void QueueFree(Queue q) {
Node curr = q->head;
while (curr != NULL) {
Node temp = curr;
curr = curr->next;
free(temp);
}
free(q);
}
/**
* Adds an item to the end of the queue
*/
void QueueEnqueue(Queue q, Item it) {
Node n = newNode(it);
if (q->size == 0) {
q->head = n;
} else {
q->tail->next = n;
}
q->tail = n;
q->size++;
}
static Node newNode(Item it) {
Node n = malloc(sizeof(*n));
if (n == NULL) {
fprintf(stderr, "couldn't allocate Node\n");
exit(EXIT_FAILURE);
}
n->item = it;
n->next = NULL;
return n;
}
/**
* Removes an item from the front of the queue and returns it
* Assumes that the queue is not empty
*/
Item QueueDequeue(Queue q) {
assert(q->size > 0);
Node newHead = q->head->next;
Item it = q->head->item;
free(q->head);
q->head = newHead;
if (newHead == NULL) {
q->tail = NULL;
}
q->size--;
return it;
}
/**
* Gets the item at the front of the queue without removing it
* Assumes that the queue is not empty
*/
Item QueueFront(Queue q) {
assert(q->size > 0);
return q->head->item;
}
/**
* Gets the size of the given queue
*/
int QueueSize(Queue q) {
return q->size;
}
/**
* Returns true if the queue is empty, and false otherwise
*/
bool QueueIsEmpty(Queue q) {
return q->size == 0;
}
/**
* Prints the queue to the given file with items space-separated
*/
void QueueDump(Queue q, FILE *fp) {
for (Node curr = q->head; curr != NULL; curr = curr->next) {
fprintf(fp, "%p ", curr->item);
}
fprintf(fp, "\n");
}
Management Science The Art of Modeling with Spreadsheets
ISBN: 978-1118582695
4th edition
Authors: Stephen G. Powell, Kenneth R. Baker