Lab5 - Pb1

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

constexpr auto SPATIU = 5;

struct NOD
{
    int info;
    NOD* st, * dr, * p;

    NOD() : info(0), st(NULL), dr(NULL), p(NULL) {}

    NOD(int info) : info(info), st(NULL), dr(NULL), p(NULL) {}
};

void preordine(NOD* x)
{
    if (x == NULL)
        return;

    cout << x->info << ' ';
    preordine(x->st);
    preordine(x->dr);

}
void inordine(NOD* x)
{
    if (x == NULL)
        return;

    inordine(x->st);
    cout << x->info << ' ';
    inordine(x->dr);

}
void postordine(NOD* x)
{
    if (x == NULL)
        return;

    postordine(x->st);
    postordine(x->dr);
    cout << x->info << ' ';

}
void BFS(NOD* x)
{
    if (x == NULL)
        return;

    queue<NOD*> coada;
    coada.push(x);

    while (!coada.empty())
    {
        NOD* cap = coada.front();
        cout << cap->info << "  ";
        coada.pop();

        if (cap->st)
            coada.push(cap->st);
        if (cap->dr)
            coada.push(cap->dr);
    }
}
void afisareArbore(NOD* x, int spatiu)
{
    if (x == NULL)
        return;
    spatiu += SPATIU;

    afisareArbore(x->dr, spatiu);
    cout << endl;

    for (int index = SPATIU; index < spatiu; cout << ' ', ++index);

    cout << x->info;
    afisareArbore(x->st, spatiu);
}

struct ARBORE_CAUT
{
    NOD* rad;
    ARBORE_CAUT() : rad(NULL) {}

    void insert(int val)
    {
        NOD* x = rad;
        NOD* y = NULL;
        NOD* z = new NOD(val);

        while (x != NULL)
        {
            y = x;
            if (z->info < x->info)
                x = x->st;
            else
                x = x->dr;
        }

        z->p = y;

        if (y == NULL)
            rad = z;
        else
        {
            if (z->info < y->info)
                y->st = z;
            else
                y->dr = z;
        }
    }

    NOD* maxim(NOD* x)
    {
        NOD* y = x;
        if (y != NULL)
            while (y->dr != NULL)
                y = y->dr;
        return y;
    }
    NOD* minim(NOD* x)
    {
        NOD* y = x;
        if (y != NULL)
            while (y->st != NULL)
                y = y->st;
        return y;
    }

    NOD* succesor(NOD* x)
    {
        NOD* y = new NOD();

        if (x->dr != NULL)
            y = minim(x->dr);
        else
        {
            y = x->p;
            while (y != NULL && x == y->dr)
            {
                x = y;
                y = y->p;
            }
        }

        return y;
    }
    NOD* predecesor(NOD* x)
    {
        NOD* y = new NOD();

        if (x->st != NULL)
            y = maxim(x->st);
        else
        {
            y = x->p;
            while (y != NULL && x == y->st)
            {
                x = y;
                y = y->p;
            }
        }

        return y;
    }

    NOD* search(int val)
    {
        NOD* x = rad;

        while (x != NULL && x->info != val)
            if (val < x->info)
                x = x->st;
            else
                x = x->dr;

        return x;
    }

    void Transplant(NOD* x, NOD* y)
    {
        if (x->p == NULL)
            rad = y;
        else
        {
            if (x == x->p->st)
                x->p->st = y;
            else
                x->p->dr = y;
        }
        if (y != NULL)
            y->p = x->p;
    }
    void del(NOD* x)
    {
        if (x->st == NULL)
            Transplant(x, x->dr);
        else
            if (x->dr == NULL)
                Transplant(x, x->st);
            else
            {
                NOD* y = succesor(x);
                if (y != x->dr)
                {
                    Transplant(y, y->dr);
                    y->dr = x->dr;
                    x->dr->p = y;
                }
                Transplant(x, y);
                y->st = x->st;
                x->st->p = y;
            }
    }

    void print_tree(int opt)
    {
        switch (opt)
        {
        case 1:
            cout << "   Parcurgerea in preordine: ";
            preordine(rad);
            break;

        case 2:
            cout << "   Parcurgerea in inordine: ";
            inordine(rad);
            break;

        case 3:
            cout << "   Parcurgerea in postordine: ";
            postordine(rad);
            break;

        case 4:
            cout << "   Parcurgerea in latime (pe niveluri): ";
            BFS(rad);
            break;

        case 5:
            cout << "\n Toate parcurgerile: ";
            cout << "\n Parcurgerea in preordine: "; preordine(rad);
            cout << "\n Parcurgerea in inordine: "; inordine(rad);
            cout << "\n Parcurgerea in postordine: "; postordine(rad);
            cout << "\n Parcurgerea in latime: "; BFS(rad);
            break;
        }

        cout << endl;
        afisareArbore(rad, 8);
        cout << endl;
    }

    void construct(ARBORE_CAUT& T, vector<int> vect)
    {
        for (auto val : vect)
            T.insert(val);
    }

    bool empty()
    {
        return (rad == NULL);
    }
    void clear()
    {
        if (empty())
            return;

        queue<NOD*> coada;
        coada.push(rad);

        NOD* cap = NULL;

        while (!coada.empty())
        {
            cap = coada.front();
            coada.pop();

            if (cap->st)
                coada.push(cap->st);
            if (cap->dr)
                coada.push(cap->dr);

            delete cap;
        }

        rad = NULL;
    }
};

void main()
{
    ARBORE_CAUT T;
    int opt = 0, val;

    do
    {
        system("CLS");
        cout << "-----Comenzi-----\n";
        cout << "1 pentru insertia unui nod\n";
        cout << "2 pentru cautarea unui nod\n";
        cout << "3 stergerea unui nod\n";
        cout << "4 pentru determinarea minimului\n";
        cout << "5 pentru determinarea maximului\n";
        cout << "6 pentru determinarea succesorului unui nod\n";
        cout << "7 pentru determinarea predecesorului unui nod\n";
        cout << "8 pentru afisarea arborelui\n";
        cout << "9 pentru stergerea nodurilor din arbore\n";
        cout << "10 pentru crearea unui arbore pornind de la un vector de intregi\n";
        cout << "0 pentru iesirea din meniu\n\n";
        cout << "Introduceti comanda: ";
        cin >> opt;

        switch (opt)
        {
        case 1:
        {
            cout << "   Introduceti valoarea: ";
            cin >> val;
            T.insert(val);
            cout << "   Valoarea a fost introdusa in arbore. \n";
            break;
        }

        case 2:
        {
            cout << "   Introduceti valoarea: ";
            cin >> val;
            if (T.search(val))
                cout << "   Valoarea se afla in arbore. ";
            else
                cout << "   Valoarea nu se afla in arbore. ";
            cout << endl;
            break;
        }

        case 3:
        {
            cout << "   Introduceti valoarea: ";
            cin >> val;
            NOD* gasit = T.search(val);
            if (gasit != NULL)
            {
                T.del(gasit);
                cout << "   Am sters nodul cu cheia " << val;
            }
            else
                cout << "   Nodul cu cheia " << val << " nu a fost gasit. ";
            cout << endl;
            break;
        }

        case 4:
        {
            NOD* minim = T.minim(T.rad);
            if (minim != NULL)
                cout << "   Valoarea minima din arbore: " << minim->info << endl;
            else
                cout << "   Arborele este vid. \n";
            break;
        }

        case 5:
        {
            NOD* maxim = T.maxim(T.rad);
            if (maxim != NULL)
                cout << "   Valoarea maxima din arbore: " << maxim->info << endl;
            else
                cout << "   Arborele este vid. \n";
            break;
        }

        case 6:
        {
            cout << "   Introduceti valoarea: ";
            cin >> val;
            NOD* gasit = T.search(val);
            if (gasit != NULL)
            {
                if (gasit != T.maxim(T.rad))
                    cout << "   Succesorul nodului cu cheia " << val << " este: " << T.succesor(gasit)->info;
                else
                    cout << "   Nodul cu cheia " << val << " reprezinta elementul maxim din arbore. ";
            }
            else
                cout << "   Nodul cu cheia " << val << " nu a fost gasit. ";
            cout << endl;
            break;
        }

        case 7:
        {
            cout << "   Introduceti valoarea: ";
            cin >> val;
            NOD* gasit = T.search(val);
            if (gasit != NULL)
            {
                if (gasit != T.minim(T.rad))
                    cout << "   Predecesorul nodului cu cheia " << val << " este: " << T.predecesor(gasit)->info;
                else
                    cout << "   Nodul cu cheia " << val << " reprezinta elementul minim din arbore. ";
            }
            else
                cout << "   Nodul cu cheia " << val << " nu a fost gasit. ";
            cout << endl;
            break;
        }

        case 8:
        {
            cout << "   1 pentru afisarea arborelui in preordine\n";
            cout << "   2 pentru afisarea arborelui in inordine\n";
            cout << "   3 pentru afisarea arborelui in postordine\n";
            cout << "   4 pentru afisarea arborelui pe niveluri\n";
            cout << "   5 pentru afisarea tuturor parcurgerilor\n";
            cout << "   Introduceti comanda: ";
            int afis;
            cin >> afis;

            cout << endl;
            T.print_tree(afis);
            cout << endl;
            break;
        }

        case 9:
        {
            T.clear();
            cout << "   Am golit arborele. \n";
            break;
        }

        case 10:
        {
            int dim;
            vector<int> vect;

            cout << "   Introduceti dimensiunea vectorului: ";
            cin >> dim;

            cout << "   Introduceti elementele vectorului: ";
            for (int index = 0; index < dim; ++index)
            {
                int x;
                cin >> x;
                vect.push_back(x);
            }

            ARBORE_CAUT T_vect;
            T_vect.construct(T_vect, vect);
            T_vect.print_tree(5);
            cout << endl;

            vect.clear();
            T_vect.clear();
        }
        }

        if (opt != 0)
        {
            cout << endl;
            system("PAUSE");
        }

    } while (opt != 0);

    if (!T.empty())
        T.clear();
}