Name your source code as .cpp (replace the text with with your last name and fir

Question

Name your source code as .cpp (replace the text with with your last name and first name, in that order) and upload to blackboard. The goal of this assignment is to implement a new search function that returns a pointer to the correct node if the search term matches the data in the node, otherwise returns NULL. Also implement a print function that will go through the nodes of the tree and print them out in ascending order. You can use either a Recursive approach or a non-recursive approach. Test your code with the following actions as inputs (program these in main) create new binary tree insert "John" insert "Mary" insert "Tim" insert "Jose" insert "Alice" print out all items in the tree use your new search function to search for "Jose", if returned node is not NULL print out "Found".

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>

#define SIZE 50


struct node
{
int data;
struct node *right,*left;
};


struct Queue
{
int front, rear;
int size;
struct node* *array;
};
  
struct node* newNode(int data)
{
struct node* temp = (struct node*) malloc(sizeof( struct node ));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
  
struct Queue* createQueue(int size)
{
struct Queue* queue = (struct Queue*) malloc(sizeof( struct Queue ));

queue->front = queue->rear = -1;
queue->size = size;

queue->array = (struct node**) malloc(queue->size * sizeof( struct node* ));

int i;
for (i = 0; i < size; ++i)
queue->array[i] = NULL;

return queue;
}

// Standard Queue Functions
int isEmpty(struct Queue* queue)
{
return queue->front == -1;
}

int isFull(struct Queue* queue)
{ return queue->rear == queue->size - 1; }

int hasOnlyOneItem(struct Queue* queue)
{ return queue->front == queue->rear; }

void Enqueue(struct node *root, struct Queue* queue)
{
if (isFull(queue))
return;

queue->array[++queue->rear] = root;

if (isEmpty(queue))
++queue->front;
}

struct node* Dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return NULL;

struct node* temp = queue->array[queue->front];

if (hasOnlyOneItem(queue))
queue->front = queue->rear = -1;
else
++queue->front;

return temp;
}

struct node* getFront(struct Queue* queue)
{ return queue->array[queue->front]; }

// A utility function to check if a tree node has both left and right children
int hasBothChild(struct node* temp)
{
return temp && temp->left && temp->right;
}

// Function to insert a new node in complete binary tree
void insert(struct node **root, int data, struct Queue* queue)
{
// Create a new node for given data
struct node *temp = newNode(data);

// If the tree is empty, initialize the root with new node.
if (!*root)
*root = temp;

else
{
struct node* front = getFront(queue);
  
if (!front->left)
front->left = temp;
  
else if (!front->right)
front->right = temp;
  
if (hasBothChild(front))
Dequeue(queue);
}
Enqueue(temp, queue);
}
  
void levelOrder(struct node* root)
{
struct Queue* queue = createQueue(SIZE);

Enqueue(root, queue);

while (!isEmpty(queue))
{
struct node* temp = Dequeue(queue);

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

if (temp->left)
Enqueue(temp->left, queue);

if (temp->right)
Enqueue(temp->right, queue);
}
}

int main()
{
struct node* root = NULL;
struct Queue* queue = createQueue(SIZE);
int i;

for(i = 1; i <= 12; ++i)
insert(&root, i, queue);

levelOrder(root);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.