ging ging 0 Newbie Poster

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);
}