Geekers Point: Tree traversal

Showing posts with label Tree traversal. Show all posts

Tuesday, 10 September 2013

Delete a node from the binary search tree

Code for Program to insert and delete a node from the binary search tree in C Programming

#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

   struct btreenode leftchild ;

  struct btreenode

{
   int data ;

   struct btreenode rightchild ;

} ;

void insert ( struct btreenode , int ) ;

void delete ( struct btreenode , int ) ;

void search ( struct btreenode , int, struct btreenode ,

   struct btreenode **, int * ) ;

void inorder ( struct btreenode * ) ;

void main( )

{

   struct btreenode bt ;

   int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;

   bt = NULL ; / empty tree /



   while ( i <= 8 )

   {

   insert ( &bt, a[i] ) ;

   i++ ;

   }



   printf ( "Binary tree before deletion:\n" ) ;

   inorder ( bt ) ;

   delete ( &bt, 10 ) ;

   printf ( "\nBinary tree after deletion:\n" ) ;

   inorder ( bt ) ;

   delete ( &bt, 14 ) ;

   printf ( "\nBinary tree after deletion:\n" ) ;

   inorder ( bt ) ;

   delete ( &bt, 8 ) ;

   printf ( "\nBinary tree after deletion:\n" ) ;

   inorder ( bt ) ;

   delete ( &bt, 13 ) ;

   printf ( "\nBinary tree after deletion:\n" ) ;

   inorder ( bt ) ;

}

/ inserts a new node in a binary search tree */

void insert ( struct btreenode **sr, int num )

{

   if ( sr == NULL )

   {

   sr = malloc ( sizeof ( struct btreenode ) ) ;

   ( sr ) -> leftchild = NULL ;

   ( sr ) -> data = num ;

   ( sr ) -> rightchild = NULL ;

   }

   else/ search the node to which new node will be attached /

   {

   / if new data is less, traverse to left /

if ( num < ( sr ) -> data )

   insert ( &( ( sr ) -> leftchild ), num ) ;

   else/ else traverse to right /

   insert ( &( ( sr ) -> rightchild ), num ) ;

   }

}

/* deletes a node from the binary search tree */

void delete ( struct btreenode **root, int num )

{

   int found ;

   struct btreenode parent, x, xsucc ;

   / if tree is empty /

if ( root == NULL )

   {

   printf ( "\nTree is empty" ) ;

   return ;

   }

   parent = x = NULL ;

   /* call to search function to find the node to be deleted /

   search ( root, num, &parent, &x, &found ) ;

   / if the node to deleted is not found /

if ( found == FALSE )

   {

   printf ( "\nData to be deleted, not found" ) ;

   return ;

   }

   / if the node to be deleted has two children /

if ( x -> leftchild != NULL && x -> rightchild != NULL )

   {

   parent = x ;

   xsucc = x -> rightchild ;

   while ( xsucc -> leftchild != NULL )

   {

   parent = xsucc ;

   xsucc = xsucc -> leftchild ;

   }

   x -> data = xsucc -> data ;

   x = xsucc ;

   }

   / if the node to be deleted has no child /

if ( x -> leftchild == NULL && x -> rightchild == NULL )

   {

   if ( parent -> rightchild == x )

   parent -> rightchild = NULL ;

   else

   parent -> leftchild = NULL ;

   free ( x ) ;

   return ;

   }

   / if the node to be deleted has only rightchild /

if ( x -> leftchild == NULL && x -> rightchild != NULL )

   {

   if ( parent -> leftchild == x )

   parent -> leftchild = x -> rightchild ;

   else

   parent -> rightchild = x -> rightchild ;

   free ( x ) ;

   return ;

   }

   / if the node to be deleted has only left child /

if ( x -> leftchild != NULL && x -> rightchild == NULL )

   {

   if ( parent -> leftchild == x )

   parent -> leftchild = x -> leftchild ;

   else

   parent -> rightchild = x -> leftchild ;

   free ( x ) ;

   return ;

   }

}

/returns the address of the node to be deleted, address of its parent and

   whether the node is found or not */

void search ( struct btreenode root, int num, struct btreenode par, struct

   btreenode **x, int found )

{

   struct btreenode q ;

   q = root ;

   found = FALSE ;

   par = NULL ;

   while ( q != NULL )

   {

   / if the node to be deleted is found /

if ( q -> data == num )

   {

   found = TRUE ;

   x = q ;

   return ;

   }

   par = q ;

   if ( q -> data > num )

   q = q -> leftchild ;

   else

   q = q -> rightchild ;

   }

}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion /

void inorder ( struct btreenode sr )

{

   if ( sr != NULL )

   {

   inorder ( sr -> leftchild ) ;

   /* print the data of the node whose leftchild is NULL or the path has

   already been traversed */

   printf ( "%d\t", sr -> data ) ;

   inorder ( sr -> rightchild ) ;

   }

}

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

preorder:  10 5 12

postorder:  12 10 5

Sunday, 8 September 2013

Reverse a LinkedList

Simple Program to Reverse a LinkedList

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

struct node{
   struct node *link;
   int data;
   };

   void insert(struct node **,int);
   void display(struct node *);
   int count(struct node *);

   void delete(struct node **,int);
   void append(struct node **,int);
   void reverse(struct node **);
   int main(){
   struct node *s;
   s=NULL;


   insert(&s,10);
   insert(&s,20);
   insert(&s,40);
   insert(&s,50);

   reverse(&s);

   display(s);

   return 0;
   }

   void insert(struct node **s,int num){
   struct node *temp;
   temp=(struct node*)malloc(sizeof(struct node));
   temp->data=num;
   temp->link=*s;
   *s=temp;
   }
   void display(struct node *s){

   while(s!=NULL){
   printf("%d \n",s->data);
   s=s->link;
   }
   printf("\n");
   }

int count(struct node *s){
   int i;
   i=0;
   while(s!=NULL){

   s=s->link;
   i++;
   }
   printf("%d",i);
   }

void delete(struct node **s,int num){
   struct node *temp,*old;
   temp=(struct node *)malloc(sizeof(struct node));
   temp->data=num;
   temp->link=*s;
   *s=temp;

   free(temp);

   }

void append(struct node **s,int num){
   struct node *temp;
   temp=(struct node *)malloc(sizeof(struct node));
   temp->data=num;
   temp->link=NULL;
   *s=temp;
}

void reverse(struct node **s) {

struct node *a = NULL;
struct node *b = NULL;
struct node *c = NULL;
a = *s, b = NULL;

while(a != NULL) {
  c = b, b = a, a = a->link;
  b->link = c;
}

*s = b;
}
output:

Executing the program....
Before Reverse