#include <stdio.h>

#include <stdlib.h>



typedef struct pointer

{

    int info;

    struct pointer *LPTR;

    struct pointer *RPTR;

}pointer;



int dem;



void inorder(pointer*);

pointer *search(pointer*,int);

pointer *ins_node(pointer**,int);

int del_node(pointer**,int);

void creat_tree(pointer**,int);

void del_tree(pointer**);

pointer *first_even(pointer*);

float avg_total(pointer*);

int num_leaves(pointer*);



int main()

{

    pointer *T;

    int info,num;

    pointer *m;

    float s;



    printf("Tao cay nhi phan tim kiem gom 10 nut!\n");

    creat_tree(&T,10);

    inorder(T);

    printf("\n\n\n");



    printf("Tim mot nut co khoa cho truoc!\n");

    printf("Thong tin cua nut can tim la:");

    scanf("%d",&info);

    m=search(T,info);

    printf("\n\n\n");



    printf("Xoa nut!\n");

    if(del_node(&T,info)) printf("Nut da duoc xoa!\n");

    else printf("Chua xoa duoc nut!\n");

    inorder(T);

    printf("\n\n\n");



    printf("Xac dinh nut chan dau tien duyet theo thu tu giua!\n");

    m=first_even(T);

    if(m==NULL) printf("Khong co phan tu chan nao!\n");

    else

    {

        printf("Phan tu chan dau tien la:%d\n",m->info);

    }

    printf("\n\n\n");



    printf("Tinh trung binh cong cua cac phan tu duong!\n");

    dem=0;

    s=avg_total(T);

    if(s==0) printf("Khong co phan tu duong nao!\n");

    else printf("Ket qua:%g\n",s/dem);

    printf("\n\n\n");



    printf("Dem so nut la!\n");

    num=num_leaves(T);

    printf("Ket qua:%d\n",num);

    printf("\n\n\n");



    printf("Xoa cay!\n");

    del_tree(&T);

    if(T==NULL) printf("Cay da duoc xoa!\n");

    else printf("Cay chua duoc xoa!\n");



    return 1;

}



void inorder(pointer *p)

{

    if(p->LPTR != NULL) inorder(p->LPTR);

    printf("%3d",p->info);

    if(p->RPTR != NULL) inorder(p->RPTR);

}



pointer *search(pointer *p,int info)

{

    while(p!=NULL)

    {

        if(p->info == info) return p;

        else if(p->info < info) p=p->RPTR;

        else p=p->LPTR;

    }

    return p;

}



pointer *ins_node(pointer **p,int info)

{

    pointer *m,*q;

    q=NULL;

    m=*p;

    while(m!=NULL)

    {

        if(m->info == info) return m;

        else if(m->info < info)

        {

            q=m;

            m=m->RPTR;

        }

        else

        {

            q=m;

            m=m->LPTR;

        }

    }

    m=(pointer*)malloc(sizeof(pointer));

    m->info = info;

    m->LPTR = m->RPTR = NULL;

    if(*p==NULL) *p=m;

    else if(q->info < info) q->RPTR = m;

    else q->LPTR = m;

    return m;

}



void creat_tree(pointer **p,int n)

{

    int i,x;

    *p = NULL;

    if(n>0)

    {

        printf("Nhap thong tin cac nut!\n");

        for(i=1;i<=n;i++)

        {

            printf("Nut %d:",i);

            scanf("%d",&x);

            if(search(*p,x)==NULL) ins_node(p,x);

        }

    }

}



int del_node(pointer **p,int info)

{

    pointer *a,*b,*c,*d;

    if(*p==NULL) return -1;

    else

    {

        a=*p;

        b=NULL;

        while(a!=NULL)

        {

            if(info==a->info) break;

            else if(info>a->info)

            {

                b=a;

                a=a->RPTR;

            }

            else

            {

                b=a;

                a=a->LPTR;

            }

        }

        if(a==NULL) return 0;

        else

        {

            if((*p)->LPTR==(*p)->RPTR)

            {

                free(*p);

                *p=NULL;

                return 1;

            }

            else

            {

                if(a->LPTR==NULL)

                {

                    if(b!=NULL)

                    {

                        if(info < b->info) b->LPTR=a->RPTR;

                        else b->RPTR=a->RPTR;

                    }

                    else *p=a->RPTR;

                }

                else if(a->RPTR==NULL)

                {

                    if(b!=NULL)

                    {

                        if(info < b->info) b->LPTR=a->LPTR;

                        else b->RPTR=a->LPTR;

                    }

                    else *p=a->LPTR;

                }

                else

                {

                    d=a;

                    c=a->LPTR;

                    while(c->RPTR!=NULL)

                    {

                        d=c;

                        c=c->RPTR;

                    }

                    if(c->info > d->info)d->RPTR=c->LPTR;

                    else d->LPTR = c->LPTR;

                    if(b!=NULL)

                    {

                        if(info < b->info) b->LPTR=c;

                        else b->RPTR=c;

                    }

                    else *p=c;

                    c->RPTR=a->RPTR;

                    c->LPTR=a->LPTR;

                }

                free(a);

                return 1;

            }

        }

    }

}



void del_tree(pointer **p)

{

    while(*p!=NULL)

    {

        del_node(p,(*p)->info);

    }

}



pointer *first_even(pointer *p)

{

    pointer *l;

    if(p==NULL) return NULL;

    else

    {

        if(p->LPTR != NULL)

        {

            l=first_even(p->LPTR);

            if(l!=NULL) return l;

        }



        if(p->info%2==0) return p;



        if(p->RPTR != NULL) return first_even(p->RPTR);

    }

    return NULL;

}



float avg_total(pointer *p)

{

    float s=0;

    if(p!=NULL)

    {

        if(p->LPTR != NULL) s+=avg_total(p->LPTR);

        if(p->info>0)

        {

            s+=p->info;

            dem++;

        }

        if(p->RPTR != NULL) s+=avg_total(p->RPTR);

    }

    return s;

}



int num_leaves(pointer *p)

{

    int d=0;

    if(p!=NULL)

    {

        if(p->LPTR != NULL) d=num_leaves(p->LPTR);

        if(p->LPTR == p->RPTR) d++;

        if(p->RPTR != NULL) d+=num_leaves(p->RPTR);

    }

    return d;

}