#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct pn {
    int valoare;
    struct pn* sting, *drept;
}nod; /* tipul unui nod din arborele binar ordonat */
nod* root = NULL; /* radacina arborelui */

nod* adauga(nod* t, int v) {
    if (t == NULL)
        if ((t = (nod*)malloc(sizeof(nod))) == NULL) {
            printf("Eroare: memorie insuficienta\n");
            exit(1);
        }
        else {/* s-a putut crea nodul */
            t->valoare = v;
            t->sting = t->drept = NULL;
        }
    else
        if (t->valoare < v)
            /* inserarea e în subarborele drept */
            t->drept = adauga(t->drept, v);
        else
            if (t->valoare > v)
                /* inserarea e în subarborele stâng */
                t->sting = adauga(t->sting, v);
            else
                printf("Valoarea % d apare in evidenta\n", v);
    return t;
} /* adauga */

void tipareste_inordine(nod* t) {
    if (t != NULL) {
        tipareste_inordine(t->sting); /* tipareste subarborele stang */
        printf("%d ", t->valoare);
        tipareste_inordine(t->drept); /* tipareste subarborele drept */
    }
} /* tipareste */

void tipareste_preordine(nod* t) {
    if (t != NULL) {
        printf("%d ", t->valoare);
        tipareste_preordine(t->sting); /* tipareste subarborele stang */

        tipareste_preordine(t->drept); /* tipareste subarborele drept */
    }
} /* tipareste */
void tipareste_postordine(nod* t) {
    if (t != NULL) {

        tipareste_postordine(t->sting); /* tipareste subarborele stang */

        tipareste_postordine(t->drept); /* tipareste subarborele drept */
        printf("%d ", t->valoare);
    }
} /* tipareste */
nod* supred(nod* t, nod* p) {
    nod* q, *q_aux;
    q = t;
    if (q->drept != NULL)
        q->drept = supred(q->drept, p); /* gaseste nodul cel mai mare din subarborele indicat de t */
    else { /* pentru nodul cel mai mare din subarborele indicat de t */
    /* muta campurile nodului indicat de q în nodul indicat de p */
        p->valoare = q->valoare;
        q_aux = q;
        q = q->sting; /* fiul stang este returnat */
        free(q_aux); /* elibereaza memoria ocupata de nod */
    }
    return q;
} /* supred */
nod* elimina(nod* p, int v) {
    nod* q;
    if (p == NULL)
        printf("Eroare: %d nu apare in evidenta\n", v);
    else
        if (p->valoare < v)
            /* nodul e in subarborele drept */
            p->drept = elimina(p->drept, v);
        else
            if (p->valoare > v)
                /* nodul e in subarborele stang */
                p->sting = elimina(p->sting, v);
            else /* s-a gasit nodul ce trebuie sters */
                if (p->sting == NULL) { /* daca nu are fiu stang */
                    q = p->drept;
                    free(p);
                    return q;
                }
                else
                    if (p->drept == NULL) { /* nu are fiu drept */
                        q = p->sting;
                        free(p);
                        return q;
                    }
                    else /* are ambii fii */
                        p->sting = supred(p->sting, p);
    return p;
} /* elimina */

int main() {
    int opt;
    int x;
    do {
        printf("[1] Inserare nod\n");
        printf("[2] Afisare inordine SVD\n");
        printf("[3] Afisare preordine VSD\n");
        printf("[4] Afisare postordine SDV\n");
        printf("Opt:");
        (void)scanf("%d", &opt);
        system("cls");
        switch (opt)
        {
        case 1:
            printf("Valoare :");
            (void)scanf("%d", &x);
            root = adauga(root, x);
            break;
        case 2:
            tipareste_inordine(root);
            printf(" -Inordine de la stanga la drapta\n\n");
            break;
        case 3:
            tipareste_preordine(root);
            printf("preordine varf la stanga  ramura din stanga apoi ramura din dreapta\n\n");
            break;
        case 4:
            tipareste_postordine(root);
            printf("postordine pleaca din ramura din stanga catre ramura dreapta, ultimul afisat este varful\n");
            break;
        default:
            break;
        }
    } while (opt);
    return 0;
}