Tuesday 10 September 2013

Tuesday 10 September 2013

Delete a node from binary Tree



To delete a node from Binary tree if :
1.if the node to be deleted has no child.
2.if node has two children.
3.if the node has only right child.
4.if the node has only left child.
#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *left;
    struct node *right;
    
};

void insert(struct node **,int);
void postorder(struct node *);
void delete(struct node **,int,struct node **);

int main(){
    struct node *s;
    s=NULL;
    insert(&s,11);
    insert(&s,13);
    postorder(s);
    printf("\n");
    delete(&s,11,NULL);
    printf("\n");
    postorder(s);
    return 0;
}

void insert(struct node **s,int num){
    if((*s)==0){
        (*s)=(struct node *)malloc(sizeof(struct node));
        (*s)->left=0;
        (*s)->data=num;
        
        (*s)->right=0;
    }
  
    else if(num<((*s)->data)){
        insert(&((*s)->left),num);
    }
  
    else if(num>((*s)->data)){
        insert(&((*s)->right),num);
    }

      
}
 void postorder(struct node *s){
     
        
        if(s!=NULL){
            
            postorder(s->left);
            postorder(s->right);
            printf("%d ",s->data);
        }else
        return;
     }
void delete(struct node **s,int num,struct node **f){
    struct node *temp;
    if((*s)->data==num){
        if(((*s)->left==NULL) && ((*s)->right==NULL)){
        temp=&(*s);
        free(*s);
        (*s)=NULL;
        }
//only delete if right node present and left should be null
        else if(((*s)->left==NULL) && ((*s)->right!=NULL)){
            free(*s);
            (*s)=(*s)->right;
        }

else if(((*s)->left!=NULL) && ((*s)->right==NULL)){
            free(*s);
            (*s)=(*s)->left;
        }

    }    
        
    }
output
$demo
13 11 

13 


No comments:

Post a Comment