Write an algorithm and program that accepts a Binary Tree as Input and Checks if the input Binary tree is Complete Binary Tree or a Full Binary Tree – IGNOU BCA Assignment 2017 – 18

By | December 23, 2017

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-033
Course Title : Data and File Structures Lab
Assignment Number : BCA(3)/L-033/Assignment/17-18
Maximum Marks : 50
Weightage : 25%

Write an algorithm and program that accepts a Binary Tree as Input and Checks if the input Binary tree is Complete Binary Tree or a Full Binary Tree and prints appropriate message – IGNOU BCA Assignment 2017 – 18

 

CODE:

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

/* Tree node structure */
struct Node
{
int key;
struct Node *left, *right;
};

/* This function counts the number of nodes in a binary tree */
int countNodes(struct Node* root)
{
if (root == NULL)
return (0);
return (1 + countNodes(root->left) + countNodes(root->right));
}

/* This function checks if the binary tree is complete or not */
int isComplete (struct Node* root, int index,int number_nodes)
{
// An empty tree is complete
if (root == NULL)
return (1);

// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return (0);

// Recur for left and right subtrees
return (isComplete(root->left, 2*index + 1, number_nodes) &&
isComplete(root->right, 2*index + 2, number_nodes));
}
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
struct Node *newNode(char k)
{
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}

/* This function tests if a binary tree is a full binary tree. */
int isFullTree (struct Node* root)
{
// If empty tree
if (root == NULL)
return (1);

// If leaf node
if (root->left == NULL && root->right == NULL)
return (1);

// If both left and right are not NULL, and left & right subtrees
// are full
if ((root->left) && (root->right))
return (isFullTree(root->left) && isFullTree(root->right));

// We reach here when none of the above if conditions work
return (0);
}

// Driver Program
void main()
{
struct Node* root = NULL;
unsigned int node_count;
unsigned int index;

clrscr();
root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);

root->left->right = newNode(40);
root->left->left = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);

root->left->left->left = newNode(80);
root->left->left->right = newNode(90);
root->left->right->left = newNode(80);
root->left->right->right = newNode(90);
root->right->left->left = newNode(80);
root->right->left->right = newNode(90);
root->right->right->left = newNode(80);
root->right->right->right = newNode(90);

node_count = countNodes(root);
index = 0;

if (isComplete(root, index, node_count))
printf(“\nThe Binary Tree is complete\n”);
else
printf(“\nThe Binary Tree is not complete\n”);

if (isFullTree(root))
printf(“\nThe Binary Tree is full\n”);
else
printf(“\nThe Binary Tree is not full\n”);

getch();

[codesyntax lang=”C”]

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

/* Tree node structure */
struct Node
{
int key;
struct Node *left, *right;
};

/* This function counts the number of nodes in a binary tree */
int countNodes(struct Node* root)
{
if (root == NULL)
return (0);
return (1 + countNodes(root->left) + countNodes(root->right));
}

/* This function checks if the binary tree is complete or not */
int isComplete (struct Node* root, int index,int number_nodes)
{
// An empty tree is complete
if (root == NULL)
return (1);

// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return (0);

// Recur for left and right subtrees
return (isComplete(root->left, 2*index + 1, number_nodes) &&
isComplete(root->right, 2*index + 2, number_nodes));
}
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
struct Node *newNode(char k)
{
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}

/* This function tests if a binary tree is a full binary tree. */
int isFullTree (struct Node* root)
{
// If empty tree
if (root == NULL)
return (1);

// If leaf node
if (root->left == NULL && root->right == NULL)
return (1);

// If both left and right are not NULL, and left & right subtrees
// are full
if ((root->left) && (root->right))
return (isFullTree(root->left) && isFullTree(root->right));

// We reach here when none of the above if conditions work
return (0);
}

// Driver Program
void main()
{
struct Node* root = NULL;
unsigned int node_count;
unsigned int index;

clrscr();
root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);

root->left->right = newNode(40);
root->left->left = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);

root->left->left->left = newNode(80);
root->left->left->right = newNode(90);
root->left->right->left = newNode(80);
root->left->right->right = newNode(90);
root->right->left->left = newNode(80);
root->right->left->right = newNode(90);
root->right->right->left = newNode(80);
root->right->right->right = newNode(90);

node_count = countNodes(root);
index = 0;

if (isComplete(root, index, node_count))
printf(“\nThe Binary Tree is complete\n”);
else
printf(“\nThe Binary Tree is not complete\n”);

if (isFullTree(root))
printf(“\nThe Binary Tree is full\n”);
else
printf(“\nThe Binary Tree is not full\n”);

getch();

[/codesyntax]

 

SCREENSHOTS:

C_program_Check_Full_Complete_BST

C_program_Check_Full_Complete_BST_Out