Scribd
Upload
63 views2 pages

Binary Search Tree Operations in C

This document defines C structures and functions for creating and manipulating a binary search tree (BST). It defines a vertex structure containing an integer data field and left and right child pointer fields. Functions are defined for creating a new vertex, inserting a new vertex into the tree, searching for a value in the tree, and deleting a value from the tree. These functions perform the standard BST operations by recursively traversing the tree and updating pointers as needed when inserting or deleting nodes.

Uploaded by

Vitor Hama
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
63 views2 pages

Binary Search Tree Operations in C

This document defines C structures and functions for creating and manipulating a binary search tree (BST). It defines a vertex structure containing an integer data field and left and right child pointer fields. Functions are defined for creating a new vertex, inserting a new vertex into the tree, searching for a value in the tree, and deleting a value from the tree. These functions perform the standard BST operations by recursively traversing the tree and updating pointers as needed when inserting or deleting nodes.

Uploaded by

Vitor Hama
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

struct v e r t e x {

int data ;
struct v e r t e x l , r ;
} r o o t ;
struct v e r t e x new ( )
{
return ( ( struct v e r t e x ) m a l l o c ( s i z e o f ( struct v e r t e x ) ) ) ;
}
struct v e r t e x c r e a t e ( )
{
struct v e r t e x p ;
p=new ( ) ;
p>data =0;
p>r=NULL;
return ( p ) ;
}
int member ( int x )
{
struct v e r t e x p ;
p=r o o t ;
do{
i f ( x<p>data )
p=p>l ;
e l s e p=p>r ;
} while ( p!=NULL && x!=p>data ) ;
return ( p!=NULL ) ;
}
void i n s e r t ( int x )
{
struct v e r t e x p , f ;
p=r o o t ;
do{
f=p ;
i f ( x<p>data )
p=p>l ;
e l s e p=p>r ;
} while ( p!=NULL ) ;
p=new ( ) ;
p>data=x ;
p>l=p>r=NULL;
i f ( x<f >data )
1

f >l=p ;
e l s e f >r=p ;

void d e l e t e ( int x )
{
struct v e r t e x f , p , q ;
p=r o o t ;
do{
f=p ;
i f ( x<p>data )
p=p>l ;
e l s e p=p>r ;
} while ( x!=p>data ) ;
i f ( p>l==NULL | | p>r==NULL) {
i f ( p>r=NULL)
q=p>l ;
e l s e q=p>r ;
i f ( f >l==p )
f >l=q ;
e l s e f >r=q ;
}
else {
q=p>r ;
f=q ;
while ( q>l !=NULL) {
f=q ;
q=q>l ;
}
p>data=q>data ;
i f ( q==f )
p>r=q>r ;
e l s e f >l=q>r ;
}
}
4.3: 2

You might also like