#include < stdio.h >
#include < conio.h >
struct tree
{
int data ;
struct tree *left_child ;
struct tree *right_child ;
};
struct tree * insert ( struct tree * );
struct tree * search ( struct tree * , int );
void display_preorder( struct tree * );
void display_postorder( struct tree * );
void display_inorder( struct tree * );
void deletion_element ( struct tree ** , int );
struct tree * findmax ( struct tree *current );
void main()
{
int choice , value;
struct tree *root = NULL , *search_element = NULL ;
while ( 1 )
{
//system("cls");
printf ( " \n\n \t Binary Tree " );
printf ( " \n\n 1. Insert \n 2. Display \n 3. Search \n 4. Delete \n 0. Exit " );
printf ( " \n\n Enter your choice : " );
scanf ( "%d" , &choice );
switch ( choice )
{
case 1 :
root = insert ( root );
printf ( " \n Node Inserted !" );
break;
case 2 :
printf ( " \n\n Tree Traverse preorder : " );
display_preorder( root );
printf ( " \n\n Tree Traverse inorder : " );
display_inorder( root );
printf ( " \n\n Tree Traverse postorder : " );
display_postorder( root );
break ;
case 3 :
printf ( " \n\n Enter value : " );
scanf ( "%d" , &value );
search_element = search ( root ,value );
if ( search_element != NULL )
{
printf ( " \n\n %d value is found ! " , search_element->data );
}
else
{
printf ( " \n\n value not found ! ");
}
break;
case 4 :
printf ( " \n\n Enter value : " );
scanf ( "%d" , &value );
deletion_element ( &root , value );
break;
case 0 :
printf ( " \n\n Thank you ! " );
getch();
exit ();
default :
printf ( " \n\n Invalid choice ! " );
}
getch();
}
}
void display_preorder( struct tree *root )
{
if ( root != NULL )
{
printf ( " %d " , root->data );
display_preorder( root->left_child ) ;
display_preorder( root->right_child ) ;
}
}
void display_postorder( struct tree *root )
{
if ( root != NULL )
{
display_postorder( root->left_child ) ;
display_postorder( root->right_child ) ;
printf ( " %d " , root->data );
}
}
void display_inorder( struct tree *root )
{
if ( root != NULL )
{
display_inorder( root->left_child ) ;
printf ( " %d " , root->data );
display_inorder( root->right_child ) ;
}
}
struct tree *insert ( struct tree *root )
{
int value ;
int c ;
struct tree *current , *previous , *new_node ;
current = previous = root ;
printf ( " \n\n Enter value : " );
scanf ( "%d" , &value );
new_node = ( struct tree * ) malloc ( sizeof ( struct tree ) );
new_node->data = value ;
new_node->left_child = NULL ;
new_node->right_child = NULL ;
if ( root == NULL )
{
root = new_node ;
}
else
{
while ( current != NULL )
{
previous = current ;
if ( current->data < value )
current = current->right_child ;
else
current = current->left_child ;
}
if ( previous->data < value )
previous->right_child = new_node ;
else
previous->left_child = new_node ;
}
return root ;
}
struct tree * search ( struct tree *root , int value)
{
while ( root != NULL )
{
if ( root->data == value )
return root ;
else if ( root->data > value )
root = root->left_child ;
else
root = root->right_child ;
}
return root ;
}
void deletion_element ( struct tree **root , int value )
{
struct tree *current = *root ;
struct tree *parent = *root ;
struct tree *temp = NULL ;
int value1 , c ;
while ( current != NULL && current->data != value )
{
parent = current ;
if ( current->data > value )
current = current->left_child ;
else
current = current->right_child ;
}
if ( current == NULL )
{
printf ( " \n\n Node does not Exits ! " );
}
else
{
// select case ...
if ( current->left_child == NULL && current->right_child == NULL ) // leaf node
c = 1 ;
else if ( current->left_child == NULL || current->right_child == NULL ) // A node have 1 child
c = 2;
else // A node have 2 child
c = 3 ;
switch ( c )
{
case 1 :
if ( current == parent )
{
*root = NULL ;
}
else
{
if ( parent->left_child == current )
parent->left_child = NULL ;
else
parent->right_child = NULL ;
}
free ( current );
break ;
case 2 :
if ( current == *root )
{
if ( (*root)->left_child == NULL )
(*root) = (*root)->right_child;
else
(*root) = (*root)->left_child;
}
else
{
if ( parent->left_child == current )
{
if ( current->left_child == NULL )
parent->left_child = current->right_child ;
else
parent->left_child = current->left_child ;
}
else
{
if ( current->left_child == NULL )
parent->right_child = current->right_child ;
else
parent->right_child = current->left_child ;
}
}
free ( current );
break ;
case 3 :
temp = findmax ( current->left_child );
value1 = temp->data ;
deletion_element ( &(*root) , value1 );
current->data = value1 ;
break;
}
}
}
struct tree * findmax ( struct tree *current )
{
if ( current != NULL )
while ( current->right_child != NULL )
current = current->right_child ;
return current;
}
***********************************************************************************************************************
------------------------------------------------------------------------
code
------------------------------------------------------------------------
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 1
Enter value : 10
Node Inserted !
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 1
Enter value : 20
Node Inserted !
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 1
Enter value : 30
Node Inserted !
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice :
1
Enter value : 40
Node Inserted !
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 2
Tree Traverse preorder : 10 20 30 40
Tree Traverse inorder : 10 20 30 40
Tree Traverse postorder : 40 30 20 10
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 3
Enter value : 20
20 value is found !
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 4
Enter value : 20
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 2
Tree Traverse preorder : 10 30 40
Tree Traverse inorder : 10 30 40
Tree Traverse postorder : 40 30 10
Binary Tree
1. Insert
2. Display
3. Search
4. Delete
0. Exit
Enter your choice : 0
Thank you !
Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.
0 comments:
Post a Comment