Heres an AVL TREE.... and my problem is.... help me include a function that delete nodes.......
# include<malloc.h>
#include<stdio.h>
# include<iostream.h>
#include<stdlib.h>
#include<conio.h>
# define F 0
# define T 1
struct NODE
{
int Info;
int Flag;
struct NODE *Left_Child;
struct NODE *Right_Child;
};
struct NODE *Binary_Tree (int , struct NODE *, int *);
void Output(struct NODE *, int );
struct NODE *Balance_Right_Heavy(struct NODE *, int *);
struct NODE *Balance_Left_Heavy(struct NODE *, int *);
/* Function to insert an element into tree */
struct NODE * Binary_Tree (int Info, struct NODE *Parent, int *H)
{
struct NODE *Node1;
struct NODE *Node2;
if(!Parent)
{
Parent = (struct NODE *) malloc(sizeof(struct NODE));
Parent->Info = Info;
Parent->Left_Child = NULL;
Parent->Right_Child = NULL;
Parent->Flag = 0;
*H = T;
return (Parent);
}
if(Info < Parent->Info)
{
Parent->Left_Child = Binary_Tree(Info, Parent->Left_Child, H);
if(*H)
/* Left branch has grown higher */
{
switch(Parent->Flag)
{
case 1: /* Right heavy */
Parent->Flag = 0;
*H = F;
break;
case 0: /* Balanced tree */
Parent->Flag = -1;
break;
case -1: /* Left heavy */
Node1 = Parent->Left_Child;
if(Node1->Flag == -1)
{
cout<< “\n Left to Left Rotation\n";
Parent->Left_Child= Node1->Right_Child;
Node1->Right_Child = Parent;
Parent->Flag = 0;
Parent = Node1;
}
else
{
cout <<”\n Left to right rotation\n";
Node2 = Node1->Right_Child;
Node1->Right_Child = Node2->Left_Child;
Node2->Left_Child = Node1;
Parent->Left_Child = Node2->Right_Child;
Node2->Right_Child = Parent;
if(Node2->Flag == -1)
Parent->Flag = 1;
else
Parent->Flag = 0;
if(Node2->Flag == 1)
Node1->Flag = -1;
else
Node1->Flag = 0;
Parent = Node2;
}
Parent->Flag = 0;
*H = F;
}}}
if(Info > Parent->Info)
{
Parent->Right_Child = Binary_Tree(Info, Parent->Right_Child, H);
if(*H)
/* Right branch has grown higher */
{
switch(Parent->Flag)
{
case -1: /* Left heavy */
Parent->Flag = 0;
*H = F; break;
case 0: /* Balanced tree */
Parent->Flag = 1; break;
case 1: /* Right heavy */
Node1 = Parent->Right_Child;
if(Node1->Flag == 1)
{
printf("\n Right to Right Rotation\n");
Parent->Right_Child= Node1->Left_Child;
Node1->Left_Child = Parent;
Parent->Flag = 0;
Parent = Node1;
}
else
{
cout<<”\n Right to Left Rotation\n";
Node2 = Node1->Left_Child;
Node1->Left_Child = Node2->Right_Child;
Node2->Right_Child = Node1;
Parent->Right_Child = Node2->Left_Child;
Node2->Left_Child = Parent;
if(Node2->Flag == 1)
Parent->Flag = -1;
else
Parent->Flag = 0;
if(Node2->Flag == -1)
Node1->Flag = 1;
else
Node1->Flag = 0;
Parent = Node2;
}
Parent->Flag = 0;
*H = F;
}}}
return(Parent);
}
/* Output function */
void Output(struct NODE *Tree,int Level)
{
int i;
if (Tree)
{
Output(Tree->Right_Child, Level+1);
cout <<”\n”;
for (i = 0; i < Level; i++)
printf(" ");
cout << Tree->Info;
Output(Tree->Left_Child, Level+1);
}}
/* Balancing Right Heavy */
struct NODE * Balance_Right_Heavy(struct NODE *Parent, int *H)
{
struct NODE *Node1, *Node2;
switch(Parent->Flag)
{
case -1:
Parent->Flag = 0;
break;
case 0:
Parent->Flag = 1;
*H= F;
break;
case 1: /* Rebalance */
Node1 = Parent->Right_Child;
if(Node1->Flag >= 0)
{
cout <<"\n Right to Right Rotation\n";
Parent->Right_Child= Node1->Left_Child;
Node1->Left_Child = Parent;
if(Node1->Flag == 0)
{
Parent->Flag = 1;
Node1->Flag = -1;
*H = F;
}
else
{
Parent->Flag = Node1->Flag = 0;
}
Parent = Node1;
}
else
{
cout << "\n Right to Left Rotation\n";
Node2 = Node1->Left_Child;
Node1->Left_Child = Node2->Right_Child;
Node2->Right_Child = Node1;
Parent->Right_Child = Node2->Left_Child;
Node2->Left_Child = Parent;
if(Node2->Flag == 1)
Parent->Flag = -1;
else
Parent->Flag = 0;
if(Node2->Flag == -1)
Node1->Flag = 1;
else
Node1->Flag = 0;
Parent = Node2;
Node2->Flag = 0;
}}
return(Parent);
}
/* Balancing Left Heavy */
struct NODE * Balance_Left_Heavy(struct NODE *Parent, int *H)
{
struct NODE *Node1, *Node2;
switch(Parent->Flag)
{
case 1:
Parent->Flag = 0;
break;
case 0:
Parent->Flag = -1;
*H= F;
break;
case -1: /* Rebalance */
Node1 = Parent->Left_Child;
if(Node1->Flag <= 0)
{
cout <<"\n Left to Left Rotation\n";
Parent->Left_Child= Node1->Right_Child;
Node1->Right_Child = Parent;
if(Node1->Flag == 0)
{
Parent->Flag = -1;
Node1->Flag = 1;
*H = F;
}
else
{
Parent->Flag = Node1->Flag = 0;
}
Parent = Node1;
}
else
{
cout <<"\n Left to Right Rotation\n";
Node2 = Node1->Right_Child;
Node1->Right_Child = Node2->Left_Child;
Node2->Left_Child = Node1;
Parent->Left_Child = Node2->Right_Child;
Node2->Right_Child = Parent;
if(Node2->Flag == -1)
Parent->Flag = 1;
else
Parent->Flag = 0;
if(Node2->Flag == 1)
Node1->Flag = -1;
else
Node1->Flag = 0;
Parent = Node2;
Node2->Flag = 0;
}}
return(Parent);
}
/* Replace the node at which key is found with last right key of a left child */
/* Function main */
void main()
{
int H;
int Info;
char choice;
struct NODE *Tree = (struct NODE *)malloc(sizeof(struct NODE));
Tree = NULL;
Cout<<"\n Input choice 'b' to break:";
choice = getchar();
while(choice != 'b')
{
cout << "\n Input information of the node: ";
cin >> Info;
Tree = Binary_Tree(Info, Tree, &H);
clrscr();
cout <<"\n Tree is:\n";
Output(Tree, 1);
fflush(stdin);
cout<<”\n Press any key to input info______";
cout <<"\n Input choice 'b' to break:";
choice = getchar();
}
fflush(stdin);
}