BinarySearchTree_FamiHug

/* Problem
 *  viết c.tr
 * 1.tạo 1 cây tìm kiếm chứa số nguyên
 * 2.Tìm 1 nút nào đấy
 * 3.xóa 1 nút nào đó trên cây
 * 4.xóa hết
 * 5.xác định nút chẵn đầu tiên trong danh sách duyệt giữa
 * 6.tìm trung bình cộng của các phần tử duong
 * 7.đếm số nút lá
 * Ver 1.0
 * Nhap cac gtri tu file

 * Future: 2.0
 * Chinh lai gtri nhap vao TRUC TIEP: truong hop a, aa, a-4759234
 */

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

typedef struct nod
{
    int info;
    //int count;
    struct nod * Lptr;
    struct nod * Rptr;
} Node_Type;

Node_Type* Add(Node_Type*,int);
Node_Type* Create_Node(int);
void Traverse(Node_Type* );
void Visit(Node_Type*);
Node_Type* Find(Node_Type*, int);
Node_Type* Find_R(Node_Type*,int);
Node_Type* First_Even(Node_Type *);
Node_Type* Create_Tree(Node_Type*,int);
float Mean(Node_Type *);
int Count_Leaf(Node_Type* );
Node_Type* Delete_Node(Node_Type*,int);
void Delete_Tree(Node_Type *p);

Node_Type *T,*p,*r,*u,*k,*d;

int f=0,cntr=0;
float s=0;
int main(int argc, char** argv)
{
    T=NULL;
    r=NULL;
    char Choice, w[80];
    int x;
    int l=0;

    printf( "\nCHUONG TRINH MINH HOA CAY NHI PHAN"
            "\n Go aX de nhap so nguyen X."
            "\n-Go rX de xoa nut co noi dung X khoi cay"
            "\n-Go fX de tim kiem nut co noi dung X"
            "\n-Go D de xoa tat ca cac nut"
            "\n-Go P de in ra cay theo cach duyet giua"
            "\n-Go E de tim phan tu chan dau tien theo cach duyet giua"
            "\n-Go M de tinh trung binh cong cac phan tu duong"
            "\n Go L de dem so nut la"
            "\n-Go ! de thoat khoi chuong trinh\n");

    while(1)
    {
        Choice=0;
        x=0;//phai init x=0 vi ham sscanf lay 2 args, truong hop ta khong dien gtri cho x (dien P de in) thi x van thoa man dk cua if(x!=0)
        fflush(stdin);
        printf("Nhap: ");
        sscanf(gets(w),"%c %d",&Choice,&x);
        if((x>=(-32768))&&(x<=32767))//g.han kieu int
        {
            switch (Choice)
            {
                case 'a':
                    T = Add(T,x);
                    break;
                case 'P':
                    if(T==NULL)
                        printf("Cay rong\n\n");
                    else
                    {
                        Traverse(T);
                        printf("\n\n");
                    }
                    break;
                case 'f':
                    p=Find(T,x);
                    if(p!=NULL)
                        printf("Tim thay nut %d trong cay\n\n",x);
                    else
                        printf("KHONG tim thay nut %d trong cay\n\n",x);
                    break;

                case 'd':
                    d=Find_R(T,x);
                    printf("Nut cha cua %d la %d\n",x,d->info);
                    break;

                case 'r':
                    r=Find(T,x);
                    if(r==NULL)
                        printf("Khong tim thay so %d trong cay\n\n",x);
                    else
                    {r=Delete_Node(T,x);
                    if(r==NULL)
                    {
                        T=(Node_Type *)malloc(sizeof(Node_Type));
                        T=NULL;
                    }}
                    break;

                case 'D':
                    if(T==NULL)
                        printf("Cay rong, khong the xoa!\n\n");
                    else
                    {
                    Delete_Tree(T);
                    printf("Da xoa cay\n\n");
                    T=(Node_Type *)malloc(sizeof(Node_Type));
                    T=NULL;
                    }
                    break;

                case 'E':
                    k=First_Even(T);
                    if(k!=NULL)
                        printf("Phan tu chan dau tien theo cach duyet giua la: %d\n\n",k->info);
                    else
                        printf("Cay khong co nut chan nao!\n\n");
                    break;

                case 'L':
                    l=Count_Leaf(T);
                    printf("So nut la cua cay da cho la: %d\n\n",l);
                    break;

                case 'M':
                    s=0;
                    cntr=0;
                    s=Mean(T);
                    printf("Trung binh cong cua cac phan tu duong la : %f\n\n",s/cntr);
                    break;

                case '!':
                    printf("\nChuong trinh ket thuc!");
                    exit(1);
            }
        }

    }

    return 0;
}

Node_Type* Add(Node_Type* p,int x)
{
    if(p==NULL)
        p=Create_Node(x);
    else
        {

            if(x<p->info)
                p->Lptr=Add(p->Lptr,x);
            else
                if(x>p->info)
                    p->Rptr=Add(p->Rptr,x);
                else
                    printf("Gia tri nhap vao da co trong cay. Nhap lai so khac!\n");

        }
    return p;
}

Node_Type* Create_Node(int x)
{
    Node_Type *l;
    l=(Node_Type *)malloc(sizeof(Node_Type));
    l->info=x;
    l->Lptr=NULL;
    l->Rptr=NULL;
    printf("Da them %d vao cay nhi phan\n",x);
    return l;
}

void Traverse(Node_Type* pt)
{
    if(pt!=NULL)
    {
        Traverse(pt->Lptr);
        Visit(pt);
        Traverse(pt->Rptr);
    }
}

void Visit(Node_Type* p)
{
    printf("%d ",p->info);
}

Node_Type * Find(Node_Type *p, int x)
{
    int i=0;
    while(p!=NULL)
    {
        if(x<p->info)
        {
            p=p->Lptr;
        }
        else
            if(x==p->info)
                {
                    i++;
                    return p;
                }
            else
                {
                    p=p->Rptr;
                }
    }
    return p;
}
Node_Type* Find_R(Node_Type *p,int x)
{
    int i=0;
    r=p;
    while(p!=NULL)
    {
        if(x<p->info)
        {
            r=p;
            p=p->Lptr;
        }
        else
            if(x==p->info)
                {
                    i++;
                    return r;
                }
            else
                {
                    r=p;
                    p=p->Rptr;
                }
    }
    return r;
}


Node_Type* Delete_Node(Node_Type *T,int x)
{
    Node_Type *p,*temp,*nr;

    p=Find(T,x);
    r=Find_R(T,x);
    if(p==T)//Xoa Goc
        {
            if((p->Lptr==NULL)&&(r->Rptr==NULL))
            {

                r=NULL;
                printf("Da xoa nut %d\n",x);
                free(p);
                return r;
            }
            else if((p->Lptr!=NULL)&&(r->Rptr==NULL))//Goc chi co con trai
            {
                r=r->Lptr;
                T=r;
                printf("Da xoa nut %d\n",x);
                free(p);
                return r;
            }
            else if((p->Lptr==NULL)&&(r->Rptr!=NULL))
            {
                r=r->Rptr;
                T=r;
                printf("Da xoa nut %d\n",x);
                free(p);
                return r;
            }
            else if(p->Lptr!=NULL&&p->Rptr!=NULL)
            {
                nr=p->Rptr;
                r=p->Lptr;
                temp=nr;
                while(temp->Lptr!=NULL)
                    temp=temp->Lptr;
                temp->Lptr=r;
                r=nr;
                T=nr;
                free(p);
                printf("Da xoa nut %d\n",x);
                return r;
            }
        }

        //P la nut la
    else if((p->Lptr==NULL)&&(r->Rptr==NULL))
        {
            printf("Da xoa la %d\n",p->info);
            if(r->Lptr==p)
                r->Lptr=NULL;
            if(r->Rptr==p)
                r->Rptr=NULL;
            r=T;
            free(p);
            return r;

        }



        //TH p chi co 1 con
            if(p->Lptr==NULL&&p->Rptr!=NULL)//p chi co con phai
                {
                    if(p==r->Lptr)//p la con trai cua R
                        r->Lptr=p->Rptr;
                    else if(p==r->Rptr)
                        r->Rptr=p->Rptr;
                    p->Rptr=NULL;
                    free(p);
                    r=T;
                    printf("Da xoa nut %d\n",x);
                    return r;
                }
            if(p->Lptr!=NULL&&p->Rptr==NULL)//p chi co con trai
                {
                    if(p==r->Lptr)
                        r->Lptr=p->Lptr;
                    else if(p==r->Rptr)
                        r->Rptr=p->Lptr;
                    p->Lptr=NULL;
                    free(p);
                    r=T;
                    printf("Da xoa nut %d\n",x);
                    return r;
                }
        //p co 2 con
        if(p->Lptr!=NULL&&p->Rptr!=NULL)
        {
            if(r->Lptr==p)
            {
                temp=p->Lptr;
                r->Lptr=p->Lptr;
                while(temp->Rptr!=NULL)
                    temp=temp->Rptr;
                temp->Rptr=p->Rptr;
                p->Lptr=NULL;
                p->Rptr=NULL;
            }
            else if(r->Rptr==p)
            {
                temp=p->Rptr;
                r->Rptr=p->Rptr;
                while(temp->Lptr!=NULL)
                    temp=temp->Lptr;
                temp->Lptr=p->Lptr;
                p->Lptr=NULL;
                p->Rptr=NULL;
            }

            free(p);
            r=T;
            printf("Da xoa nut %d\n",x);
            return r;
        }

    return T;
}



Node_Type* First_Even(Node_Type *p) {
    if(p!=NULL) {
        Node_Type *found = First_Even(p->Lptr);
        if(found!=NULL) { return found; }
        return (p->info%2==0) ? p : First_Even(p->Rptr);
    }
    return NULL;
}

int Count_Leaf(Node_Type* p)
{
    if(p == NULL) return 0;
    if(p->Lptr == NULL && p->Rptr==NULL)
    return 1;
  else
    return Count_Leaf(p->Lptr)+ Count_Leaf(p->Rptr);
}

float Mean(Node_Type *p)
{
    float s=0;
    if(p!=NULL)
    {
        if(p->Lptr != NULL) s+=Mean(p->Lptr);
        if(p->info>0)
        {
            s+=p->info;
            cntr++;
        }
        if(p->Rptr != NULL) s+=Mean(p->Rptr);
    }
    return s;
}

void Delete_Tree(Node_Type *p)
{
    if(p->Lptr!=NULL)
    {
        Delete_Tree(p->Lptr);
        p->Lptr=NULL;
    }
    if(p->Lptr!=NULL)
    {
        Delete_Tree(p->Rptr);
        p->Rptr=NULL;
    }
    free(p);
}