RSS

Treaps

08 Mar
Treaps are binary search trees in which each node has both a key and a priority.
Here’s the implementation in C:

#include<stdio.h>

#include<iostream.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct btreenode
{
int data;
int priority;
struct btreenode *leftchild;
struct btreenode *rightchild;
};
struct btreenode *bt;
void insert(struct btreenode**,int,int);
void inorder(struct btreenode*);
void show(struct btreenode*);
void insertfunc();
void deletefunc();
void searchfunc();
void search(struct btreenode*,int);
void del(struct btreenode**,int);
void main()
{
int choice;
bt=NULL; //empty tree
char ch;
do
{
printf(“What operation do you wish to perform on the tree\n”);
printf(“1. Insertion\n”);
printf(“2. Deletion\n”);
printf(“3. Searching\n”);
printf(“4. Show elements\n”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
insertfunc();
break;
case 2:
deletefunc();
break;
case 3:
searchfunc();
break;
case 4:
printf(“Elements are:\n”);
show(bt);
break;
}
cout<<“\nDo you want to continue (y or n)\n”;
cin>>ch;
}while(ch==’y’||ch==’Y’);
}
void inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr->leftchild);
inorder(sr->rightchild);
}
else
return;
}
void insertfunc()
{
int req,i=1,num,num2;
printf(“Enter the no. of items to be inserted\n”);
scanf(“%d”,&req);
while(i++<=req)
{
printf(“Enter the data\n”);
scanf(“%d”,&num);
printf(“Enter the priority\n”);
scanf(“%d”,&num2);


insert(&bt,num,num2);
}
}
void deletefunc()
{
int num;
printf(“Enter the element to be deleted\n”);
scanf(“%d”,&num);
del(&bt,num);
}
void searchfunc()
{
int num;
printf(“Enter the element to be searched\n”);
scanf(“%d”,&num);
search(bt,num);
}
void insert(struct btreenode **sr,int num,int num2)
{
if(*sr==NULL)
{
*sr=(btreenode*)malloc(sizeof(struct btreenode));
(*sr)->leftchild=NULL;
(*sr)->data=num;
(*sr)->priority=num2;
(*sr)->rightchild=NULL;
}
else
{
if(num<(*sr)->data)
insert(&((*sr)->leftchild),num,num2);
else
insert(&((*sr)->rightchild),num,num2);
}
return;
}
void search(struct  btreenode *sr,int num)
{
if(sr!=NULL)
{
search(sr->leftchild,num);
if(sr->data==num)
{
cout<<“Element found”<<endl;
return;
}
search(sr->rightchild,num);
}
else
{
return;
}
}
void del(struct btreenode **sr,int num)
{
if(*sr!=NULL)
{
del(&((*sr)->leftchild),num);
if((*sr)->data==num)
{
if((*sr)->leftchild!=NULL)
{
(*sr)=(*sr)->leftchild;
free((*sr)->leftchild);
return;
}
else
if((*sr)->rightchild!=NULL)
{
(*sr)=(*sr)->rightchild;
free(&((*sr)->rightchild));
return;
}
else
{
free(&((*sr)));
}
}
del(&((*sr)->rightchild),num);
}
}
void show(struct btreenode *sr)
{
if(sr!=NULL)
{
show(sr->leftchild);
printf(“\t%d”,sr->data);
printf(“\t%d\n”,sr->priority);
show(sr->rightchild);
}
else
return;

}

Advertisements
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

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

 
%d bloggers like this: