-implement a function that will determine whertherthe tree is a 0-2 tree. -imple
ID: 3570848 • Letter: #
Question
-implement a function that will determine whertherthe tree is a 0-2 tree.
-implement a function that will find the maximum value in a tree.
this is wat i have so far.Its builds the tree and displays it.
#include <iostream>
#include <fstream>
using namespace std;
struct tree
{
int data;
tree *lChild;
tree *rChild;
};
class BST
{
private:
tree *head;
int count;
public:
//methods
BST();
int size();
void insert(int data);
void insert(tree *&temp, int data);
void display();
void display(tree *root);
};
ifstream infile;
ofstream outfile;
BST::BST()
{
head = NULL;
count = 0;
}
int BST::size()
{
return count;
}
void BST::insert(tree *&temp, int data)
{
if (temp == NULL)
{
tree *newone = new tree;
newone->data = data;
newone->lChild = NULL;
newone->rChild = NULL;
temp = newone;
return;
}
else
{
if (temp->data <= data)
{
insert(temp->rChild, data);
}
else
{
insert(temp->lChild, data);
}
}
}
void BST::insert(int data)
{
if (head == NULL)
{
tree *newone = new tree;
newone->data = data;
newone->lChild = NULL;
newone->rChild = NULL;
head = newone;
count++;
return;
}
else
{
insert(head, data);
count++;
return;
}
}
void BST::display(tree *root)
{
if (root == NULL)
{
return;
}
else
{
display(root->lChild);
outfile<< root->data << " ";
display(root->rChild);
}
}
void BST::display()
{
if (count == 0)
{
outfile<< "Tree is Empty" << endl;
}
else
{
outfile<< "Total 25 elements from an input file from small to large order in binary search" << endl;
display(head);
outfile << endl;
}
}
int main()
{
BST tree;
infile.open("data.txt");
outfile.open("results.txt");
int data;
while (infile >> data)
{
tree.insert(data);
}
tree.display();
infile.close();
outfile.close();
system("PAUSE");
return 0;
}
this is wat i have so far.Its builds the tree and displays it.The information in the infile is 25 random numbers.Need the c++ code for the functions above.Thanks
Explanation / Answer
Answer for Question 1 is:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_Q_SIZE 500
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* frunction prototypes for functions needed for Queue data
structure. A queue is needed for level order tarversal */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);
bool isQueueEmpty(int *front, int *rear);
/* Given a binary tree, return true if the tree is complete
else false */
bool isCompleteBT(struct node* root)
{
// Base Case: An empty tree is complete Binary Tree
if (root == NULL)
return true;
// Create an empty queue
int rear, front;
struct node **queue = createQueue(&front, &rear);
// Create a flag variable which will be set true
// when a non full node is seen
bool flag = false;
// Do level order traversal using queue.
enQueue(queue, &rear, root);
while(!isQueueEmpty(&front, &rear))
{
struct node *temp_node = deQueue(queue, &front);
/* Ceck if left child is present*/
if(temp_node->left)
{
// If we have seen a non full node, and we see a node
// with non-empty left child, then the given tree is not
// a complete Binary Tree
if (flag == true)
return false;
enQueue(queue, &rear, temp_node->left); // Enqueue Left Child
}
else // If this a non-full node, set the flag as true
flag = true;
/* Ceck if right child is present*/
if(temp_node->right)
{
// If we have seen a non full node, and we see a node
// with non-empty left child, then the given tree is not
// a complete Binary Tree
if(flag == true)
return false;
enQueue(queue, &rear, temp_node->right); // Enqueue Right Child
}
else // If this a non-full node, set the flag as true
flag = true;
}
// If we reach here, then the tree is complete Bianry Tree
return true;
}
/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
struct node **queue =
(struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);
*front = *rear = 0;
return queue;
}
void enQueue(struct node **queue, int *rear, struct node *new_node)
{
queue[*rear] = new_node;
(*rear)++;
}
struct node *deQueue(struct node **queue, int *front)
{
(*front)++;
return queue[*front - 1];
}
bool isQueueEmpty(int *front, int *rear)
{
return (*rear == *front);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above functions*/
int main()
{
/* Let us construct the following Binary Tree which
is not a complete Binary Tree
1
/
2 3
/
4 5 6
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->right = newNode(6);
if ( isCompleteBT(root) == true )
printf ("Complete Binary Tree");
else
printf ("NOT Complete Binary Tree");
return 0;
}
Answer for Question 2 is:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.