Need help with these functions for the program below(please show output) -A func
ID: 3570263 • Letter: N
Question
Need help with these functions for the program below(please show output)
-A function that will find the maximum value in the tree
--A function that prints the bst from the maximum element to the minimum element
-a function that will determine if a binary tree is a full binary tree
#include <iostream>
#include <fstream>
using namespace std;
struct node{
int value;
node *left;
node *right;
};
class BST{
private:
node *head;
int count;
public:
BST();
int size();
void insert(int value);
void insert(node *&temp, int value);
void display();
void display(node *root);
void makecopy(BST &newcopy);
void makecopy(BST &newcopy, node *temp);
bool isEqual(BST newtree);
bool isEqual(node *temp1, node *temp2);
void createReversed(BST &reversed, node *temp);
void createReversed(BST &reversed);
};
BST::BST(){
head = NULL;
count = 0;
}
int BST::size(){
return count;
}
void BST::insert(node *&temp, int value){
if(temp == NULL){
node *newone = new node;
newone->value = value;
newone->left = NULL;
newone->right = NULL;
temp = newone;
return;
}
else{
if(temp->value <= value){
insert(temp->right, value);
}
else{
insert(temp->left, value);
}
}
}
void BST::insert(int value){
if(head == NULL){
node *newone = new node;
newone->value = value;
newone->left = NULL;
newone->right = NULL;
head = newone;
count++;
return;
}
else{
insert(head, value);
count++;
return;
}
}
void BST::display(node *root){
if(root == NULL){
return;
}
else{
display(root->left);
cout << root->value << " ";
display(root->right);
}
}
void BST::display(){
if(count == 0){
cout << "Tree is Empty" << endl;
}
else{
cout << "Inorder Traversal of the tree" << endl;
display(head);
cout << endl;
}
}
void BST::createReversed(BST &reversed, node *temp){
if(temp == NULL){
return;
}
else{
createReversed(reversed, temp->right);
createReversed(reversed, temp->left);
reversed.insert(temp->value);
}
}
void BST::createReversed(BST &reversed){
if(count == 0){
return;
}
else{
createReversed(reversed, head);
}
}
void BST::makecopy(BST &newcopy, node *temp){
if(temp == NULL){
return;
}
else{
newcopy.insert(temp->value);
makecopy(newcopy, temp->left);
makecopy(newcopy, temp->right);
}
}
void BST::makecopy(BST &newcopy){
if(count == 0){
return;
}
else{
makecopy(newcopy, head);
}
}
bool BST::isEqual(node *temp1, node *temp2){
if(temp1 == NULL){
if(temp2 == NULL){
return true;
}
else{
return false;
}
}
else{
if(temp2 == NULL){
return false;
}
else{
if(temp1->value != temp2->value){
return false;
}
else{
return (isEqual(temp1->left, temp2->left) && isEqual(temp1->right, temp2->right));
}
}
}
}
bool BST::isEqual(BST newtree){
if(count == 0 && newtree.size() == 0){
return true;
}
else{
isEqual(head, newtree.head);
}
}
int main(){
BST tree;
ifstream fp;
fp.open("data.txt");
int value;
while(fp >> value){
tree.insert(value);
}
cout << "Original Tree is: " << endl;
tree.display();
BST reversedTree;
tree.createReversed(reversedTree);
BST copytree;
tree.makecopy(copytree);
cout << "Copy Tree is: " << endl;
copytree.display();
if(tree.isEqual(copytree)){
cout << "Two Trees are equal" << endl;
}
else{
cout << "Two Trees are not same" << endl;
}
return 0;
}
Explanation / Answer
Answer 1:
#include<stdio.h>
#include<stdlib.h>
/* 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;
};
/* Compute the "maxDepth" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
/* 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);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Hight of tree is %d", maxDepth(root));
getchar();
return 0;
}
Answer 2:
struct node
{
int data;
struct node *left;
struct node *right;
};
/* The functions prints all the keys which in the given range [k1..k2].
The function assumes than k1 < k2 */
void Print(struct node *root, int k1, int k2)
{
/* base case */
if ( NULL == root )
return;
/* Since the desired o/p is sorted, recurse for left subtree first
If root->data is greater than k1, then only we can get o/p keys
in left subtree */
if ( k1 < root->data )
Print(root->left, k1, k2);
/* if root's data lies in range, then prints root's data */
if ( k1 <= root->data && k2 >= root->data )
printf("%d ", root->data );
/* If root->data is smaller than k2, then only we can get o/p keys
in right subtree */
if ( k2 > root->data )
Print(root->right, k1, k2);
}
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = new struct node;
int k1 = 10, k2 = 25;
/* Constructing tree given in the above figure */
root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
Print(root, k1, k2);
getchar();
return 0;
}
Answer for 3:
#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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.