Would you like to make this site your homepage? It's fast and easy...
Yes, Please make this my home page!
FOR LOVE BIRDS ONLY CURRENTLY NOT AVALIABLE
SORRY FRIENDSS
Project for Hina and Seema
#include
#include
#include
#include
#include
#include
typedef struct TreeNode{
int info;
TreeNode *left;
TreeNode *right;
};
///////////////////////////////////////////////////////
/////////////////FUNCTIONS/////////////////////////////
///////////////////////////////////////////////////////
void avl (void);
void menu (void);
void menu2 (int);
void insert (TreeNode *,TreeNode *);
void listmem(TreeNode *);
void level (TreeNode*, int );
void path (TreeNode*, int );
void countleaf(TreeNode*);
void count_add(TreeNode *);
void delet ();
void search(TreeNode*,int);
void balance (TreeNode *);
void b(TreeNode *);
void graph (TreeNode *);
TreeNode* replacer(void);
TreeNode* leftrot(TreeNode *tree);
TreeNode* rightrot(TreeNode *tree);
TreeNode* dobleft(TreeNode *tree);
TreeNode* dobright(TreeNode *tree);
//////////////////////////////////////////////////////////////
//////////////GLOBAL VARIABLES////////////////////////////////
//////////////////////////////////////////////////////////////
int count=0,add=0,lev=0,leaf[20],Left[10],Right[10];
TreeNode *first,*parent=NULL,*child=NULL;
//////////////////////////////////////////////////////////////
//////////////MAIN STARTS/////////////////////////////////////
//////////////////////////////////////////////////////////////
void main (void)
{
int a,b;
textbackground(0);
textcolor(LIGHTGREEN);
int members=0;
for(int x=0;x<1000;x++)
{
clrscr();
printf("\t ADDITION OF ELEMENT");
printf("\n ====================");
printf("\n PRESS '1' to enter the element at the start.");
printf("\n DELETE AN ELEMENT");
printf("\n ====================");
printf("\n PRESS '2' to delete the element of the link TreeNode");
printf("\n DIAMETER OF THE TREE");
printf("\n ====================");
printf("\n PRESS '3' to covert into avl");
printf("\n PRESS '4' for graphical representation (upto 3 level)");
printf("\n EXIT ");
printf("\n ==========");
printf("\n PRESS '5' to exit");
printf("\n ENTER YOUR CHOICE:");
scanf("%d",&a);
clrscr();
switch(a)
{
case 1:
printf("\n
Enter the element:");
scanf("%d",&b);
TreeNode *node;
node=(TreeNode*)malloc(sizeof(TreeNode));
node->info=b;
node->left=NULL;
node->right=NULL;
if(members==0)
{
first=node;
members++;
}
else
insert(first,node);
break;
case 2:
printf("Which element you want to delete?");
scanf("%d",&a);
search(first,a);
if(child==NULL)
printf("The node you have entered does not exits.");
else
delet();
child=NULL;
parent=NULL;
getch();
break;
case 3:
avl();
break;
case 4:
graph(first);
break;
case 5:
exit(1);
} // end of case.
} //end of for.
getch();
}
void insert (TreeNode *root,TreeNode *a) /// INSERTION
{
if (a->info < root->info)
{
if(root->left==NULL)
root->left=a;
else
insert(root->left,a);
}
if (a->info > root->info)
{
if(root->right==NULL)
root->right=a;
else
insert(root->right,a);
}
}
void listmem (TreeNode *first) /// IN ORDER
{
TreeNode *temp;
temp=first;
if(temp!=NULL)
{
listmem(temp->left);
printf("%d\n",temp->info);
listmem(temp->right);
}
}
void countleaf (TreeNode *temp) // COUNTS LEAF NODES
{
if(temp->right==NULL&&temp->left==NULL)
{
leaf[count]=temp->info;
count++;
}
if(temp!=NULL)
{
fflush(stdin);
countleaf(temp->left);
countleaf(temp->right);
}
}
void count_add(TreeNode * first) // COUNTS AND ADDS NODES
{
if(first!=NULL)
{ count ++;
add+=first->info;
count_add(first->left);
count_add(first->right);
}
}
void search (TreeNode* first,int a) //SEARCHES A NODE
{
TreeNode* temp;
temp=first;
if(temp!=NULL)
{
if(temp->right->info==a)
{ parent=temp;
child=temp->right;
printf("\n
The element %d is traced.....",temp->right->info);
delay(300);
}
if(temp->left->info==a)
{ parent=temp;
child=temp->left;
printf("\n
The element %d is traced.....",temp->left->info);
delay(300);
}
else
{ search(temp->left,a);
search(temp->right,a);
}
}
}
void delet () // DELETE THE SEARCHED NODE
{
if(child->left==NULL && child->right==NULL)
{
if(parent->right==child)
parent->right=NULL;
if(parent->left==child)
parent->left=NULL;
TreeNode*temp=child;
free(temp);
}
//////////////////////////////////////////////////////////////////////////////
if(child->left!=NULL && child->right==NULL)
{
if(parent->right==child)
parent->right=child->left;
if(parent->left==child)
parent->left=child->left;
TreeNode*temp=child;
free(temp);
}
if(child->left==NULL && child->right!=NULL)
{
if(parent->right==child)
parent->right=child->right;
if(parent->left==child)
parent->left=child->right;
TreeNode*temp=child;
free(temp);
}
///////////////////////////////////////////////////////////////////////////
if(child->left!=NULL && child->right!=NULL)
{
TreeNode*temp;
temp=replacer();
child->info=temp->info;
if(parent->left==temp)
parent->left=temp->right;
if(parent->right==temp)
parent->right=NULL;
free(temp);
}
}
TreeNode* replacer() //REPLACE THE DELETE TWO CHILD NODE
{
TreeNode*temp=child->right;
parent=child;
while(temp->left!=NULL)
{ parent=temp;
temp=temp->left;
}
return temp;
}
void level (TreeNode*root, int num)
{
if(root!=NULL)
{
if (num < root->info)
{
lev++;
level(root->left,num);
}
if (num > root->info)
{
lev++;
level(root->right,num);
}
}
}
void path (TreeNode*root, int num)
{
if(root!=NULL)
{
if (num < root->info)
{
lev++;
printf("\n%d",root->info);
path(root->left,num);
}
if (num > root->info)
{
lev++;
printf("\n%d",root->info);
path(root->right,num);
}
}
}
void balance (TreeNode *first)
{
if(first!=NULL)
{countleaf(first);
int max=0,maxLeft=0,maxRight=0,maxval=0,bal=0;
// printf("\nThere are %d leaf nodes ",count);
for(int f=0;finfo)
{ Left[max]=leaf[f];
max++ ;
}
if(leaf[f] > first->info)
{ Right[maxval]=leaf[f];
maxval++;
}
}
for(f=0;finfo,bal);
count=0;
getch();
balance (first->left);
balance (first->right);
}
}
TreeNode* rightrot(TreeNode *tree)
{
TreeNode *temp;
temp=tree->left;
tree->left=temp->right;
temp->right=tree;
return temp;
}//end of left rotation function
TreeNode* leftrot(TreeNode *tree)
{
TreeNode *temp;
temp=tree->right;
tree->right=temp->left;
temp->left=tree;
return temp;
}//end of right rotation function
TreeNode* dobright(TreeNode *tree)
{
TreeNode *temp;
temp=tree->left;
tree->left=temp->right;
temp->right=tree;
return temp;
}//end of left rotation function
TreeNode* dobleft(TreeNode *tree)
{
TreeNode *temp;
temp=tree->right;
tree->right=temp->left;
temp->left=tree;
return temp;
}//end of right rotation function
void graph (TreeNode *first)
{
int u=0,sa;
char uz[6];
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,"c:\ c3\bgi");
while(u!=5)
{
setfillstyle(1,9); //BACKGROUND
bar(0,0,1000,1000); //BACKGROUND
settextstyle(11,0,1);
setfillstyle(1,6);
//========================================
if(first!=NULL)
{
bar(275,15,325,30); // 0 LEVEL
itoa(first->info,uz,10);
outtextxy(285,20,uz);
}
//=======================================
//============== 1 LEVEL ==============
//=======================================
if(first->left!=NULL)
{line(300,30,175,100);
bar(150,100,200,115);
itoa(first->left->info,uz,10);
outtextxy(160,105,uz);
///////////////////////////////////////
///////// LEVEL 2//////////////////////
///////////////////////////////////////
if(first->left->left!=NULL)
{
line(175,115,75,185);
bar(50,185,100,200);
itoa(first->left->left->info,uz,10);
outtextxy(60,190,uz);
///////////////////////////////////////
///////// LEVEL 3//////////////////////
///////////////////////////////////////
if(first->left->left->left!=NULL)
{line(75,200,35,275);
bar(10,275,60,290);
itoa(first->left->left->left->info,uz,10);
outtextxy(20,280,uz);
}
if(first->left->left->right!=NULL)
{line(75,200,100,275); // LINE FROM 2 TO 3.
bar(75,275,125,290); // 3 LEVEL
itoa(first->left->left->right->info,uz,10);
outtextxy(85,280,uz);
}
}
///////////////////////////////////////
///////// LEVEL 2//////////////////////
///////////////////////////////////////
if(first->left->right!=NULL)
{
line(175,115,225,185); // LINE FROM 1 TO 2.
bar(200,185,250,200); // 2 LEVEL
itoa(first->left->right->info,uz,10);
outtextxy(210,190,uz);
///////////////////////////////////////
///////// LEVEL 3//////////////////////
///////////////////////////////////////
if(first->left->right->left!=NULL)
{line(225,200,175,275);
bar(150,275,200,290);
itoa(first->left->right->left->info,uz,10);
outtextxy(160,280,uz);
}
if(first->left->right->right!=NULL)
{line(225,200,250,275);
bar(225,275,275,290);
itoa(first->left->right->right->info,uz,10);
outtextxy(235,280,uz);
}
}
}
if(first->right!=NULL)
{line(300,30,445,100); // LINE FROM 0 TO 1.
bar(420,100,470,115); // 1 LEVEL
itoa(first->right->info,uz,10);
outtextxy(430,105,uz);
if(first->right->left!=NULL)
{
line(445,115,390,185); // LINE FROM 1 TO 2.
bar(365,185,415,200); // 2 LEVEL
itoa(first->right->left->info,uz,10);
outtextxy(375,190,uz);
if(first->right->left->left!=NULL)
{line(390,200,345,275); // LINE FROM 2 TO 3.
bar(320,275,370,290); // 3 LEVEL
itoa(first->right->left->left->info,uz,10);
outtextxy(330,280,uz);
}
if(first->right->left->right!=NULL)
{line(390,200,420,275); // LINE FROM 2 TO 3.
bar(395,275,445,290); // 3 LEVEL
itoa(first->right->left->right->info,uz,10);
outtextxy(405,280,uz);
}
}
if(first->right->right!=NULL)
{
line(445,115,515,185); // LINE FROM 1 TO 2.
bar(490,185,540,200); // 2 LEVEL
itoa(first->right->right->info,uz,10);
outtextxy(500,190,uz);
if(first->right->right->left!=NULL)
{line(515,200,495,275); // LINE FROM 2 TO 3.
bar(470,275,520,290); // 3 LEVEL
itoa(first->right->right->left->info,uz,10);
outtextxy(480,280,uz);
}
if(first->right->right->right!=NULL)
{line(515,200,570,275); // LINE FROM 2 TO 3.
bar(545,275,595,290); // 3 LEVEL
itoa(first->right->right->right->info,uz,10);
outtextxy(555,280,uz);
}
}
}//=======================================
menu();
scanf("%d",&u);
if(u!=5)
{
if(u==1||u==2)
menu2(1);
if(u==1||u==2)
menu2(2);
scanf("%d",&sa);
switch(u)
{
case 1:
if(first->info==sa)
first=rightrot(first);
else
{
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.");
if(parent->left==child)
parent->left=rightrot(child);
else
printf("Can't rotate.");
}
parent=NULL;
child=NULL;
getch();
break;
case 2:
if(first->info==sa)
first=leftrot(first);
else
{
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.");
if(parent->right==child)
parent->right=leftrot(child);
else
printf("Can't rotate.");
}
parent=NULL;
child=NULL;
getch();
break;
case 3:
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.");
if(parent->right==child)
parent->right=dobright(child);
else
printf("Can't rotate.");
getch();
parent=NULL;
child=NULL;
break;
case 4:
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.") ;
if(parent->left==child)
parent->left=dobleft(child);
else
printf("Can't rotate.");
getch();
parent=NULL;
child=NULL;
break;
}//end of switch
}//end of if
}//end of for
closegraph();
}
void menu ()
{
int a=50,b=570,c=305,d=450,HIGH=1,BACK=2;
for(int i=c ; i<=d; i++)
{
delay(1);
bar(a,i,b,i);
setfillstyle(1,BLUE);
bar(a+7,i+11,b+10,i+11);
setfillstyle(1,WHITE);
bar(a,i,b,i);
}
for(i=c+5 ; i<=d-8 ; i++)
{
delay(1);
setcolor(BLACK);
line(a+6,c+6,a+514,c+5);
putpixel(a+6,i,HIGH);
putpixel(a+514,i,HIGH);
}
line(a+6,d-8,a+514,d-8);
setcolor(BACK);
settextstyle(2,0,6);
outtextxy(75,315,"1-TO ROTATE RIGHT. ");
outtextxy(75,335,"2-TO ROTATE LEFT. ");
outtextxy(295,315,"3-TO ROTATE DOUBLE RIGHR. ");
outtextxy(295,335,"4-TO ROTATE DOUBLE RIGHR.");
outtextxy(200,355,"5-TO RETURN TO MAIN MENU. ");
setfillstyle(1,8);
bar(200,385,410,415);
setfillstyle(1,6);
bar(190,375,400,405);
setcolor(14);
settextstyle(2,0,6);
outtextxy(200,380,"YOUR OPTION : ");
setfillstyle(1,0);
bar(330,380,380,400);
gotoxy(43,25);
}
void menu2 (int r)
{
int a=50,b=570,c=305,d=450,HIGH=1,BACK=2;
for(int i=c ; i<=d; i++)
{
delay(1);
bar(a,i,b,i);
setfillstyle(1,BLUE);
bar(a+7,i+11,b+10,i+11);
setfillstyle(1,WHITE);
bar(a,i,b,i);
}
for(i=c+5 ; i<=d-8 ; i++)
{
delay(1);
setcolor(BLACK);
line(a+6,c+6,a+514,c+5);
putpixel(a+6,i,HIGH);
putpixel(a+514,i,HIGH);
}
line(a+6,d-8,a+514,d-8);
setcolor(BACK);
settextstyle(2,0,6);
if (r==2)
outtextxy(75,330," ENTER THE NUMBER IN CASE OF DOUBLE R/L/ ROTATION. ");
else
outtextxy(75,330,"ENTER THE PARENT NODE IN CASE OF R/L ROTATION. ");
setfillstyle(1,8);
bar(200,385,410,415);
setfillstyle(1,6);
bar(190,375,400,405);
setcolor(14);
settextstyle(2,0,6);
outtextxy(200,380,"YOUR OPTION : ");
setfillstyle(1,0);
bar(330,380,380,400);
gotoxy(43,25);
}
void avl (void)
{
int b;
for(int sa=0;sa<1000; sa++)
{
clrscr();
count_add(first);
printf("\t There are %d nodes in the tree.
",count);
printf("\t *****************************
");
count=0;
balance(first);
printf("\n
PRESS '1' to rotate right.");
printf("\n
PRESS '2' to rotate left.");
printf("\n
PRESS '3' to rotate double right.");
printf("\n
PRESS '4' to rotate double left.");
printf("\n
PRESS '5' to return to main menu.");
printf("\n
ENTER YOUR OPTION:");
scanf("%d",&b);
if(b!=5)
{
printf("\n
Which node do you wanna rotate? ");
scanf("%d",&sa);
}
switch(b)
{
case 1:
if(first->info==sa)
first=rightrot(first);
else
{
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.");
if(parent->left==child)
parent->left=rightrot(child);
else
printf("Can't rotate.");
}
parent=NULL;
child=NULL;
getch();
break;
case 2:
if(first->info==sa)
first=leftrot(first);
else
{
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.");
if(parent->right==child)
parent->right=leftrot(child);
else
printf("Can't rotate.");
}
parent=NULL;
child=NULL;
getch();
break;
case 3:
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.");
if(parent->right==child)
parent->right=dobright(child);
else
printf("Can't rotate.");
getch();
parent=NULL;
child=NULL;
break;
case 4:
search (first,sa);
if(parent==NULL||child==NULL)
printf("Node does not exists.") ;
if(parent->left==child)
parent->left=dobleft(child);
else
printf("Can't rotate.");
getch();
parent=NULL;
child=NULL;
break;
case 5:
sa=1000;
}//end of switch
} //end of for
}
void b (TreeNode *first)
{ static int flag=0;
if(first!=NULL)
{countleaf(first);
int max=0,maxLeft=0,maxRight=0,maxval=0,bal=0;
for(int f=0;finfo)
{ Left[max]=leaf[f];
max++ ;
}
if(leaf[f] > first->info)
{ Right[maxval]=leaf[f];
maxval++;
}
}
for(f=0;f1)
flag=1;
count=0;
getch();
b(first->left);
b(first->right);
}
}
