Program to implement threaded binary tree

 /* Program to implement threaded binary tree */

 #include "alloc.h"



 enum boolean

{

false = 0 ,

true = 1 ,

} ;



struct thtree

{

enum boolean left ;

struct thtree *leftchild ;

int data ;

struct thtree *rightchild ;

enum boolen right ;

} ;



 main( )

 {

struct thtree *th_head ;

th_head = NULL ;/* empty tree */

insert ( &th_head, 11 ) ;

insert ( &th_head, 9 ) ;

insert ( &th_head, 13 ) ;

insert ( &th_head, 8 ) ;

insert ( &th_head, 10 ) ;

insert ( &th_head, 12 ) ;

insert ( &th_head, 14 ) ;

insert ( &th_head, 15 ) ;

insert ( &th_head, 7 ) ;



clrscr( ) ;

printf ( "Threaded binary tree before deletion: " ) ;

inorder ( th_head ) ;



delete ( &th_head, 10 ) ;

printf ( "\nThreaded binary tree after deletion: " ) ;

inorder ( th_head ) ;



delete ( &th_head, 14 ) ;

printf ( "\nThreaded binary tree after deletion: " ) ;

inorder ( th_head ) ;



delete ( &th_head, 8 ) ;

printf ( "\nThreaded binary tree after deletion: " ) ;

inorder ( th_head ) ;



delete ( &th_head, 13 ) ;

printf ( "\nThreaded binary tree after deletion: " ) ;

inorder ( th_head ) ;

 }



 /* inserts a node in a threaded binary tree */

 insert ( struct thtree **s, int num )

 {

struct thtree *head = *s , *p, *z ;



/* allocating a new node */

z = malloc ( sizeof ( struct thtree ) ) ;

z -> left = true ; /* indicates a thread */

z -> data = num ; /* assign new data */

z -> right = true ; /* indicates a thread */



/* if tree is empty */

if ( *s == NULL )

{

head = malloc ( sizeof ( struct thtree ) ) ;

/* the entire tree is treated as a left subtree of the head node */

head -> left = false ;

head -> leftchild = z ;  /* z becomes leftchild of the head node */

head -> data = -9999 ;  /* no data */

head -> rightchild = head ;  /* right link will always be pointing to itself */

head -> right = false ;

*s = head ;

z -> leftchild = head ;  /* left thread to head */

z -> rightchild = head ;  /* right thread to head */

}

else /* if tree is non-empty */

{

p = head -> leftchild ;



/* traverse till the thread is found attached to the head */

while ( p != head )

{

if ( p -> data > num )

{

if ( p -> left != true )  /* checking for a thread */

p = p -> leftchild ;

else

{

z -> leftchild = p -> leftchild ;

p -> leftchild = z ;

p -> left = false ;  /* indicates a link */

z -> right = true ;

z -> rightchild = p ;

return ;

}

}

else

{

if ( p -> data  right != true )

p = p -> rightchild ;

else

{

z -> rightchild = p -> rightchild ;

p -> rightchild = z ;

p -> right = false ;  /* indicates a link */

z -> left = true ;

z -> leftchild = p ;

return ;

}

}

}

  }

}

 }



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

 delete ( struct thtree **root, int num )

 {

int found ;

struct thtree *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 -> left == false && x -> right == false )

  {

parent = x ;

xsucc = x -> rightchild ;

while ( xsucc -> left == false )

{

parent = xsucc ;

xsucc = xsucc -> leftchild ;

}

x -> data = xsucc -> data ;

x = xsucc ;

}



/* if the node to be deleted has no child */

if ( x -> left == true && x -> right == true )

{

if ( parent -> rightchild == x )

{

parent -> right = true ;

parent -> rightchild = x -> rightchild ;

}

else

{

parent -> left = true ;

parent -> leftchild = x -> leftchild ;

  }

free ( x ) ;

return ;

}



/* if the node to be deleted has only rightchild */

if ( x -> left == true && x -> right == false )

{

if ( parent -> leftchild == x )

{

parent -> leftchild = x -> rightchild ;

x -> rightchild -> leftchild = x -> leftchild ;

}

else

{

parent -> rightchild = x -> rightchild ;

x -> rightchild -> leftchild = parent ;

  }

free ( x ) ;

return ;

}



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

if ( x -> left == false && x -> right == true )

{

if ( parent -> leftchild == x )

{

parent -> leftchild = x -> leftchild ;

x -> leftchild -> rightchild = parent ;

}

else

{

parent -> rightchild = x -> leftchild ;

x -> leftchild -> rightchild = x -> rightchild ;

}

free ( x ) ;

return ;

}

 }



 /* returns the address of the node to be deleted, address of its parent and whether the node is found or not */

search ( struct thtree **root, int num, struct thtree **par, struct thtree **x, int *found )

{

struct thtree *q ;

q = ( *root ) -> leftchild ;

*found = false ;

*par = NULL ;

while ( q != root )

{

/* if the node to be deleted is found */

if ( q -> data == num )

{

*found = true ;

*x = q ;

return ;

}

if ( q -> data > num )

{

*par = q ;

q = q -> leftchild ;

}

else

{

*par = q ;

q = q -> rightchild ;

}

}

 }



 /* traverses the threaded binary tree in inorder */

 inorder ( struct thtree *root )

 {

struct thtree *p ;

p = root -> leftchild ;

while ( p != root )

{

while ( p -> left == false )

  p = p -> leftchild ;

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

while ( p -> right == true )

{

p = p -> rightchild ;

if ( p == root )

break ;

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

}

p = p -> rightchild ;

  }

 }  

Advertisements

One thought on “Program to implement threaded binary tree

  1. I got this website from my pal who told me on the topic of this web
    page and at the moment this time I am visiting this web page and reading very informative articles or reviews here.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s