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

    typedef struct elDrzewa
    {
        int dana;
        struct elDrzewa *prawy;
        struct elDrzewa *lewy;
        struct elDrzewa *rodzic;
    }drzewo;

    drzewo *T=NULL, *D=NULL;
    FILE *F;
    char a;

    drzewo *dodajD(drzewo *T, int x, drzewo *rodzic)
    {
        drzewo *q;
        if(T==NULL)
        {
            q=malloc(sizeof(drzewo));
            q->dana=x;
            q->lewy=NULL;
            q->prawy=NULL;
            q->rodzic=rodzic;
            return q;
        }
        else{
            if(T->dana<x)
                T->prawy=dodajD(T->prawy,x,T);
            else
                T->lewy=dodajD(T->lewy,x,T);
            return T;
        }
    }



void drukowanieDrzewa(drzewo *d, unsigned h, unsigned long long M)
    {
            if (d == NULL)
            {
                    printf("Drzewo jest puste.");
                    //return 0;
            }
            int i;
            if (d->prawy)
                    drukowanieDrzewa(d->prawy, h + 1, M << 1);
            for (i = h - 2; i < h; --i)
            {
                    unsigned long long m = (M >> i) & 3;

                    if ((m == 0) || (m == 3))
                            printf(" ");
                    else
                            printf("\xB3");
                    printf(" ");
            }
            if (h)
            {
                    if (M & 1)
                            printf("\xC0");
                    else
                            printf("\xDA");
                    printf("\xC4");
            }
            printf("%d \n", d->dana);
            if (d->lewy)
                    drukowanieDrzewa(d->lewy, h + 1, (M << 1) | 1);
            //return 1;
    }

void drukuj_struk(drzewo *T, int glebokosc)
    {
        int i;
        if (T==0)
            return;

        drukuj_struk(T->lewy,glebokosc+1);

        for(i=0;i<glebokosc;i++)
            putchar(' ');

        printf("%d\n",T->dana);
        drukuj_struk(T->prawy,glebokosc+1);
    }

drzewo *szukanieD(drzewo *T,int x)
    {
        if(T!=0)
        {
            if(T->dana==x)
            {
                printf("element znaleziony\n");
                return T;
            }
              else if(T->dana>x)
                {
                    szukanieD(T->lewy,x);
                }
              else if(T->dana<x)
                {
                    szukanieD(T->prawy,x);
                }
        }
    else
        {
            printf("nie znaleziono elementu w drzewie\n");
            return NULL;
        }
    }

drzewo *znajdz_MIN(drzewo *T)
    {
        drzewo *q=T;
        if(T==NULL)
        {
            printf("Drzewo nie ma min");
        }
        else
        {
            while(q->lewy!=NULL)
                q=q->lewy;

            printf("Element MIN: %d\n",q->dana);
            return q;
        }
    }

drzewo *znajdz_MAX(drzewo *T)
    {
        drzewo *q=T;
        if(T==NULL)
        {
            printf("Drzewo nie ma min");
        }
        else
        {
            while(q->prawy!=NULL)
                q=q->prawy;

            printf("Element MAX: %d\n",q->dana);
            return q;
        }
    }

drzewo *poprzednik(drzewo *q)
    {
        drzewo *p;
        if(q->lewy)
            return znajdz_MAX(q->lewy);
        else
        {
            p=q->rodzic;
            while (p && p->lewy == q)
            {
                q=p;
                p=q->rodzic;
            }
            if(p!=NULL)
                return NULL;
            else
                return p;
        }
    }

drzewo *nastepnik(drzewo *q)
    {
        drzewo *p;
        if(q->prawy)
            return znajdz_MIN(q->prawy);
        else
        {
            p=q->rodzic;
            while (p && p->prawy == q)
            {
                q=p;
                p=q->rodzic;
            }
            if(p!=NULL)
                return NULL;
            else
                return p;
        }
    }

drzewo *usunD(drzewo *T, int x)
    {
        drzewo *w,*v;
        if (T!=NULL)
        {
            if(T->dana>x)
            {
                T->lewy=usunD(T->lewy,x);
                return T;
            }

            if(T->dana<x)
            {
                T->prawy=usunD(T->prawy,x);
                return T;
            }

            w=T;
            if(w->lewy==NULL)
                v=w->prawy;

            else if(w->prawy==NULL)
                v=w->lewy;

            else
            {
                w=w->lewy;
                if(w->prawy==NULL)
                {
                    T->lewy=w->lewy;
                    T->dana=w->dana;
                    v=T;
                }
            else
            {
               v=T;
                while(w->prawy!=NULL)
                {
                    v=w;
                    w=w->prawy;
                }
                v->prawy=w->lewy;
                T->dana=w->dana;
                v=T;
            }
            }
            free(w);
            return v;
        }

    }


void zapisz_do_pliku(drzewo *T, FILE *F)
    {
        if(T!=NULL)
        {
            fprintf(F,"%d\t",T->dana);
            zapisz_do_pliku(T->lewy,F);
            zapisz_do_pliku(T->prawy,F);
        }
        else fprintf(F, "0\t");
    }


drzewo *dodaj_z_pliku(drzewo *T, FILE *F, int rodzic)
{
            drzewo *q;
            int x = 0;
            if (feof(F) == NULL)
                {
                    fscanf(F, "%d", &x);
            if (x == 0)
                    return NULL;
                    q = malloc(sizeof(drzewo));
                    q->dana = x;
                    q->rodzic = rodzic;
                    q->lewy = dodaj_z_pliku(q->lewy, F, q);
                    q->prawy = dodaj_z_pliku(q->prawy, F, q);
                    return q;
                }
    }


//************* zad 14

int SprawdzD(drzewo *T, drzewo *D)
{
    if (T != NULL && D != NULL)
        {
        if (T->dana != D->dana)
            return 1;

    else
    {
    SprawdzD(T->lewy, D->lewy);
    SprawdzD(T->prawy, D->prawy);
    return 0;
    }
        }
}
















    int main()
    {


        drzewo *z,*nast;
        int x,u,s,por;

        printf("Podaj wartosc do drzewa \n");
        scanf("%d",&x);
        while(x!=0)
        {
            T=dodajD(T,x,0);
            printf("Podaj wartosc do drzewa \n");
            scanf("%d",&x);
        }


        drukowanieDrzewa(T,0,0);

        znajdz_MAX(T);
        znajdz_MIN(T);

        printf("Podaj jaki element chcesz wyszukac\n");
        scanf("%d",&s);
        z=szukanieD(T,s);
        if(z==0)
        {
            printf("Nie znaleziono\n\n");
        }


        else
        {
        nast=nastepnik(z);
        if(nast!=NULL)
        {
            printf("nastepnik %u wynosi %d \n",s,nast->dana);
        }
        }


        printf("Podaj jakie element chcesz usunac z drzewa\n");
        scanf("%d",&u);

        T=usunD(T,u);
        drukowanieDrzewa(T,0,0);


        getchar();
        printf("\nChcesz zapisac drzewo do pliku txt");
            scanf("%c", &a);
            if (a == 'y')
            {
                F = fopen("drzewo.txt", "a");
                zapisz_do_pliku(T, F);
                fclose(F);
            }

        F = fopen("drzewo.txt", "r");

                    if (F == NULL)
                    {
                        printf("\nPlik drzewo.txt nie istnieje!\n");
                        return 1;
                    }
                   D = dodaj_z_pliku(T, F, T);
                   fclose(F);

        if (D != NULL)
        printf("drzewo z pliku: \n\n\n\n");


        drukowanieDrzewa(D,0,0);



        por=SprawdzD(T,D);
        if(por!=1)
            printf("\n\nDrzewa Sa takie same");

        return 0;
    }