Pages

Showing posts with label height of binary tree. Show all posts
Showing posts with label height of binary tree. Show all posts

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));
}
}