Geekers Point: Tree

Showing posts with label Tree. Show all posts

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

Monday, 9 September 2013

Binary Tree Traversal Program In c (InOrder)

C PROGRAM FOR TREE (PREORDER TRAVERSAL)

The binary tree is a fundamental data structure used in computer science. The binary tree is a useful data structure for rapidly storing sorted data and rapidly retrieving stored data.

A binary tree is composed of parent nodes, or leaves, each of which stores data and also links to up to two other child nodes (leaves) which can be visualized spatially as below the first node with one placed to the left and with one placed to the right. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

The typical graphical representation of a binary tree is essentially that of an upside down tree. It begins with a root node, which contains the original key value. The root node has two child nodes; each child node might have its own child nodes. Ideally, the tree would be structured so that it is a perfectly balanced tree, with each node having the same number of child nodes to its left and to its right.

#include <stdio.h>
#include <stdlib.h>

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

};

void insert(struct node **,int);
void preorder(struct node *);
void postorder(struct node *);
int main(){
   struct node *s;
   s=NULL;
   insert(&s,10);
   insert(&s,5);
   insert(&s,12);
   preorder(s);
   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 preorder(struct node *s){

     if(s!=NULL){
   printf("%d ",s->data);
   preorder(s->left);
   preorder(s->right);
   }else
   return;
   }

void postorder(struct node *s){

if(s!=NULL){

postorder(s->left);

postorder(s->right);

printf("%d ",s->data);

}else

return;

}

OUTPUT
Executing the program....
$demo