Finding number nodes in a tree and height of tree and find number of full nodes
fullnodes:
null those nodes are not full nodes
code:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct treenode
{
int data;
struct treenode *left;
struct treenode *right;
} *root=NULL;
//static tree building function
struct treenode * buildtree()
{
struct treenode *temp1,*temp2,*temp3,*temp4,*temp5;
root=(struct treenode *)malloc(sizeof(struct treenode));
temp1=(struct treenode *)malloc(sizeof(struct treenode));
temp2=(struct treenode *)malloc(sizeof(struct treenode));
temp3=(struct treenode *)malloc(sizeof(struct treenode));
temp4=(struct treenode *)malloc(sizeof(struct treenode));
root->data=4;
root->left=temp1;
temp1->data=5;
root->right=temp2;
temp2->data=6;
temp1->left=temp3;
temp3->data=7;
temp3->left=temp3->right=NULL;
temp1->right=temp4;
temp4->data=8;
temp4->left=NULL;
temp4->right=NULL;
temp2->left=temp2->right=NULL;
printf("\n tree buildedsuccessfull");
return root;
}
//no nodes
int noofnodes(struct treenode *root)
{
if(root==NULL) return 0;
return noofnodes(root->left)+noofnodes(root->right)+1;
}
//height of tree
int height(struct treenode *root)
{
if(root==NULL) return 0;
return max(height(root->left),height(root->right))+1;
}
//
int max(int i, int k)
{
if(i>k)
return i;
return k;
}
int fullnodes(struct treenode *root)
{
int count=0;
if(root==NULL ) return ;
else if(root->left!=NULL&&root->right!=NULL)
count=1;
return fullnodes(root->left)+fullnodes(root->right)+count;
}
int d=0;
int diameter(struct treenode *root,int l)
{
d=l;
int lh,rh;
if(root==NULL) return 0;
lh=diameter(root->left,d);
rh=diameter(root->right,d);
if(d<(lh+rh))
d=lh+rh;
return max(lh,rh)+1;
}
void main()
{
struct treenode *root;
int i=1;
while(i)
{
printf("\n enter 2 to build tree");
printf("\n enter 1 to find no of nodes of given tree");
printf("\n enter 3 to find height");
printf("\n enter 4 find full nodes of given tree");
printf("\n enter 5 find diameter");
scanf("%d",&i);
if(i==5)
{
diameter(root,d);
printf("\n %d is diameter",d);
}
if(i==4)
printf("\n full node is %d",fullnodes(root));
if(i==2)
root=buildtree();
if(i==3)
printf("\n height if tree is %d",height(root));
if(i==1)
printf("\n %d is no of nodes in given tree",noofnodes(root));
}
}
No comments:
Post a Comment