Pages

Monday 27 August 2012

Finding number nodes in a tree and height of tree and find number of full nodes

fullnodes:

nodes which have both left and right childrens if a node contains left or right is null or both are
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: