BACHELOR OF COMPUTER APPLICATIONS
Course Code : BCSL-033
Course Title : Data and File Structures Lab
Assignment Number : BCA(III)/L-033/Assignment/2015
Maximum Marks : 50
Weightage : 25%
Write an Algorithm and a Program that accepts a Binary Tree as input and checks whether it is a Height Balanced Tree.
#include <stdio.h>
#include <stdlib.h>
struct tnode
{
int data;
struct tnode *lchild, *rchild;
};
/* returns maximum of two integers */
int maxi(int a,int b)
{
int c;
c = (a >= b)? a :b;
return c;
}
int isBalanced(struct tnode *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if(root == NULL)
return 1;
/* Get the height of left and right sub trees */
lh = height(root->lchild);
rh = height(root->rchild);
if( abs(lh-rh) <= 1 &&
isBalanced(root->lchild) &&
isBalanced(root->rchild))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
/* The function Compute the “height” of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct tnode* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + maxi(height(node->lchild), height(node->rchild));
}
struct tnode *insert(struct tnode *p,int val)
{
struct tnode *temp1,*temp2;
if(p == NULL)
{
p = (struct tnode *) malloc(sizeof(struct tnode));
/* insert the new node as root node*/
if(p == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
p->data = val;
p->lchild=p->rchild=NULL;
}
else
{
temp1 = p;
/* traverse the tree to get a pointer to that node
whose child will be the newly created node*/
while(temp1 != NULL)
{
temp2 = temp1;
if( temp1 ->data > val)
temp1 = temp1->lchild;
else
temp1 = temp1->rchild;
}
if( temp2->data > val)
{
temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->lchild;
if(temp2 == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
else
{
temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->rchild;
if(temp2 == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}
/* a function to binary tree in preorder */
void preorder(struct tnode *p)
{
if(p != NULL)
{
printf(“%d\t”,p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
if(p != NULL)
{
inorder(p->lchild);
printf(“%d\t”,p->data);
inorder(p->rchild);
}
}
/* a function to binary tree in postorder */
void postorder(struct tnode *p)
{
if(p != NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf(“%d\t”,p->data);
}
}
void main()
{
struct tnode *root = NULL;
int n,x;
clrscr();
printf(“\nEnter the number of nodes\n”);
scanf(“%d”,&n);
while(n!=0)
{
printf(“Enter the data value\n”);
scanf(“%d”,&x);
root = insert(root,x);
n–;
}
if(isBalanced(root))
printf(“\n***THIS TREE IS A BALANCED TREE***\n”);
else
printf(“\n**THIS TREE IS NOT A BALANCED TREE**\n”);
printf(“\n\nPREORDER OF TREE : \n”);
preorder(root);
printf(“\n\nINORDER OF TREE : \n”);
inorder(root);
printf(“\n\nPOSTORDER OF TREE : \n”);
postorder(root);
getch();
}
CODE:
[codesyntax lang=”php”]
#include <stdio.h> #include <stdlib.h> struct tnode { int data; struct tnode *lchild, *rchild; }; /* returns maximum of two integers */ int maxi(int a,int b) { int c; c = (a >= b)? a :b; return c; } int isBalanced(struct tnode *root) { int lh; /* for height of left subtree */ int rh; /* for height of right subtree */ /* If tree is empty then return true */ if(root == NULL) return 1; /* Get the height of left and right sub trees */ lh = height(root->lchild); rh = height(root->rchild); if( abs(lh-rh) <= 1 && isBalanced(root->lchild) && isBalanced(root->rchild)) return 1; /* If we reach here then tree is not height-balanced */ return 0; } /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(struct tnode* node) { /* base case tree is empty */ if(node == NULL) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + maxi(height(node->lchild), height(node->rchild)); } struct tnode *insert(struct tnode *p,int val) { struct tnode *temp1,*temp2; if(p == NULL) { p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/ if(p == NULL) { printf("Cannot allocate\n"); exit(0); } p->data = val; p->lchild=p->rchild=NULL; } else { temp1 = p; /* traverse the tree to get a pointer to that node whose child will be the newly created node*/ while(temp1 != NULL) { temp2 = temp1; if( temp1 ->data > val) temp1 = temp1->lchild; else temp1 = temp1->rchild; } if( temp2->data > val) { temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode)); /*inserts the newly created node as left child*/ temp2 = temp2->lchild; if(temp2 == NULL) { printf("Cannot allocate\n"); exit(0); } temp2->data = val; temp2->lchild=temp2->rchild = NULL; } else { temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode)); /*inserts the newly created node as left child*/ temp2 = temp2->rchild; if(temp2 == NULL) { printf("Cannot allocate\n"); exit(0); } temp2->data = val; temp2->lchild=temp2->rchild = NULL; } } return(p); } /* a function to binary tree in preorder */ void preorder(struct tnode *p) { if(p != NULL) { printf("%d\t",p->data); preorder(p->lchild); preorder(p->rchild); } } /* a function to binary tree in inorder */ void inorder(struct tnode *p) { if(p != NULL) { inorder(p->lchild); printf("%d\t",p->data); inorder(p->rchild); } } /* a function to binary tree in postorder */ void postorder(struct tnode *p) { if(p != NULL) { postorder(p->lchild); postorder(p->rchild); printf("%d\t",p->data); } } void main() { struct tnode *root = NULL; int n,x; clrscr(); printf("\nEnter the number of nodes\n"); scanf("%d",&n); while(n!=0) { printf("Enter the data value\n"); scanf("%d",&x); root = insert(root,x); n--; } if(isBalanced(root)) printf("\n***THIS TREE IS A BALANCED TREE***\n"); else printf("\n**THIS TREE IS NOT A BALANCED TREE**\n"); printf("\n\nPREORDER OF TREE : \n"); preorder(root); printf("\n\nINORDER OF TREE : \n"); inorder(root); printf("\n\nPOSTORDER OF TREE : \n"); postorder(root); getch(); }
[/codesyntax]
SCREENSHOTS: