//      minhhoaTREE_yoyolove.c
//
//      Copyright 2010 YoYoLove <traitimbanggia.199x@gmail.com>


#include <stdio.h>
#include <stdlib.h>

typedef struct pointer
{
    struct pointer *lptr, *rptr;
    int info;
} tree;

int S[100];
int j=0;
float s;

tree *add_node(tree *p, int giatrinut)
{
    tree *A=NULL,*B=NULL;
    if(p == NULL)
    {
        p=(tree*)malloc(sizeof(tree));
        p->info = giatrinut;
        p->lptr = NULL;
        p->rptr = NULL;
    }
    else
    {
        A = p;
        while(A != NULL)
        {
                if(giatrinut == A->info)
                {
                printf("\n Exit...");
                exit(0);
                }

                else if(giatrinut < A->info)
                {
                    B=A; A=A->lptr;
                }
                else
                {
                    B=A; A=A->rptr;
                }

        }
        A=(tree*)malloc(sizeof(tree));
        A->info = giatrinut;
        A->lptr = A->rptr = NULL;
        if(giatrinut < B->info)
        {
            B->lptr = A;
        }
        else
        {
            B->rptr = A;
        }
    }
    return p;
}

void duyetgiua(tree *p)
{
    if(p->lptr !=NULL)
    {
    duyetgiua(p->lptr);
    }
    printf(" %5d",p->info);
    if(p->rptr !=NULL)
    {
    duyetgiua(p->rptr);
    }
}

tree *timkiem(tree *p,int xxx)
{
    while(p!=NULL)
    {
        if(xxx== p->info)
        {
            return p; break;
        }
        else
        {
            if(xxx < p->info)
            {
                if(p->lptr == NULL) return NULL;
                else p=p->lptr;
            } else
            {
                if(p->rptr == NULL) return NULL;
                else p=p->rptr;
            }
        }
    }
    return p;
}

int tim_chan(tree *p)
{
    if(p->lptr !=NULL)
        {
            tim_chan(p->lptr);
        }
    if(p->info%2==0)
        {
            ++j; S[j]=p->info;
        }
    if(p->rptr !=NULL)
        {
            tim_chan(p->rptr);
        }
    return j;
}

void delete_node(tree *p,int xxx)
{
    tree *A, *B, *C, *D;
    A=p;
    A=timkiem(A,xxx);
    if(A == NULL)
    {
        printf("\n Gia tri vua nhap %d khong ton tai, khong the xoa! \n ket thuc...", xxx);
        exit(0);
    }
    else
    {
        // A->info = xxx
        //tim cha cua nut can xoa
        B=p;
        while(B!=NULL)
        {
            C=B;
            if(xxx < B->info) B=B->lptr;
            if(xxx > B->info) B=B->rptr;
            if(B->info == xxx) break;
        }
        B=C;
        //Cha nut can xoa: B->info)
        //Xoa
        //nut xoa la nut la:
        if(A->lptr==NULL && A->lptr==NULL)
        {
            if(A==B) //A la goc
                {
                    p=NULL;
                }

            if(A->info < B->info) //A la con trai cua B
                {
                    B->lptr=NULL;
                }

            if(A->info > B->info) //A la con phai cua B
                {
                    B->rptr=NULL;
                }
        }

        if(A->lptr==NULL && A->rptr != NULL) //nut xoa la nut nua la co con phai
            {
                if(A==B)
                {
                    B=B->rptr;
                    p=B;
                    A->rptr=NULL;
                }else
                    {
                        B->rptr=A->rptr;

                    }A->rptr = NULL;

            }
        if(A->rptr==NULL && A->lptr != NULL) //nut xoa la nut nua la co con trai
            {
                if(A==B)
                {
                    B=B->lptr;
                    p=B;
                    A->rptr=NULL;
                }else
                    {
                        B->lptr=A->lptr;
                        A->lptr= NULL;
                    }
            }

        if((A->rptr !=NULL) && (A->lptr != NULL)) //Truong hop A la cay con
        {
            C=A->rptr;
            D=C;//tim nut trai tan cung ben phai: C la con cua A
            while(C->lptr!=NULL) //tim cha cua C
            {
                D=C;
                C=C->lptr;
            }
            printf("\n A-left= %d", A->lptr->info);
            printf("\n C= %d", C->info);
            printf("\n D= %d", D->info);
            if(A==B) //neu A la goc
            {
                if(C==D)
                {
                    C->lptr=A->lptr;
                    C->rptr=NULL;
                    p=C;
                }else
                    {
                        C->lptr=A->lptr;
                        C->rptr=D;
                        p=C;
                    }

            }

            if(B->lptr == A) // A la cay con trai cua B
            {
                if(C==D) //truong hop  C la nut la: C=D
                {
                    C->lptr=A->lptr;
                    B->lptr=C;
                    A->lptr=A->rptr=NULL;
                }
                else
                    {
                        D->lptr=NULL;
                        B->lptr=C;
                        C->lptr=A->lptr;
                        C->rptr=A->rptr;
                        A->lptr=A->rptr=NULL;

                    }

            }

            if(B->rptr== A) // A la cay con phai cua B
            {
                if(C==D) //truong hop  C la nut la: C=D
                {
                    C->lptr=A->lptr;
                    C->rptr=NULL;
                    B->rptr=C;
                    A->lptr=A->rptr=NULL;
                }
                else
                    {
                        D->lptr=NULL;
                        B->rptr=C;
                        C->lptr=A->lptr;
                        C->rptr=A->rptr;
                        A->lptr=A->rptr=NULL;
                    }
            }
        }

        printf("\n Da xoa: %d", A->info);
        free(A);

        if(p!=NULL)
        {
        printf("\n Cay sau khi xoa duyet theo thu tu giua: \n");
        duyetgiua(p);
        }else
                {
                    printf("\n Cay rong...");
                    exit(0);
                }
    }
}

int dem_nut_la(tree *p)
{
    if(p->lptr !=NULL) dem_nut_la(p->lptr);

    if(p->rptr==p->lptr) j++;

    if(p->rptr !=NULL) dem_nut_la(p->rptr);

    return j;
}

float tbc(tree *p)
{
    if(p->lptr !=NULL) tbc(p->lptr);

    if(p->info > 0)
    {
        s=s+p->info; j++;
    }
    if(p->rptr !=NULL) tbc(p->rptr);

    return s;
}

int main()
{
    tree *root=NULL, *T=NULL;
    int n,i,sonut;

    printf("\n So nut ( > 0): ");
    scanf("%d",&sonut);

    for(i=1;i<=sonut;i++)
    {
        printf("\n Nut thu %d= ", i);
        scanf("%d",&n);
        root = add_node(root,n);
    }

    T=root;
    //duyet
    printf("\n \n Cay da nhap: \n");
    duyetgiua(root);

    //tim kiem
    root=T;
    printf("\n\n Nhap vao gia tri tim kiem n= ");
    scanf("%d",&n);
    root = timkiem(root,n);
    if(root!=NULL) printf("\n Ton tai %d", root->info);
    else printf("\n Khong ton tai %d",n);

    //them nut
    printf("\n\n Nhap gia tri muon them: ");
    scanf("%d",&n);
    root=T;
    root = timkiem(root,n);
    if(root!=NULL)
    {
        printf("\n Gia tri vua nhap da ton tai (%d) khong the them", root->info);
        exit(0);
    }
    else
    {
        root=T;
        root=add_node(root,n);
        printf("\n Cay moi: \n");
        duyetgiua(root);
    }

    printf("\n\n");
    root=T;
    j=tim_chan(root);
    if(j!=0) printf("\n Phan tu chan dau tien duyet theo thu tu giua: %d \n",S[1]);
    else printf("\n Khong co so chan nao trong cay...");

    root=T;
    j=0;
    j=dem_nut_la(root);
    printf("\n\n");
    printf("\n So nut la: %d",j);

    printf("\n\n");
    root=T;
    j=0;
    s=tbc(root);
    if(j!=0)
    {
        printf("\n TBC= %g",s/j);
    }
    else printf("\n Khong co so duong nao trong cay...");

    root=T;
    printf("\n\n");
    printf("\n Nhap gia tri muon xoa: ");
    scanf("%d",&n);
    delete_node(root,n);
return(0);
}