Lab3 - Pb6

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

constexpr auto SPATIU = 5;

struct VECTOR
{
    vector<int> sir;
    void citire(string fisier)
    {
        ifstream fin(fisier);
        if (fin.peek() == EOF) {
            cout << "Fisierul este vid. \n";
            return;
        }

        int val;
        while (fin >> val)
            sir.push_back(val);
    }

    void afisare()
    {
        for (auto val : sir)
            cout << val << ' ';
        cout << endl;
    }

    void eliberareMemorie()
    {
        sir.clear();
        sir.shrink_to_fit();
    }
};

struct ARBORE
{
    struct NOD
    {
        int info = INT_MIN;
        NOD* st = NULL, * dr = NULL;
    };

    NOD* radacina = new NOD;

    bool empty()
    {
        if (radacina == NULL)
            return true;
        return false;
    }

    NOD* formareArbore(VECTOR preOrdine, VECTOR inOrdine, int& indexPreordine, int start, int end)
    {
        if (start > end)
            return NULL;

        NOD* nod = new NOD;
        nod->info = preOrdine.sir[indexPreordine++];

        int indexInordine = pozInInordine(nod->info, inOrdine, start, end);

        nod->st = formareArbore(preOrdine, inOrdine, indexPreordine, start, indexInordine - 1);
        nod->dr = formareArbore(preOrdine, inOrdine, indexPreordine, indexInordine + 1, end);

        return nod;
    }

    int pozInInordine(int val, VECTOR vect, int start, int end)
    {
        for (int index = start; index <= end; ++index)
            if (vect.sir[index] == val)
                return index;
        return -1;
    }

    int inaltime(NOD* rad)
    {
        if (rad == NULL)
            return -1;

        int inaltimeSt = inaltime(rad->st);
        int inaltimeDr = inaltime(rad->dr);

        return max(inaltimeSt, inaltimeDr) + 1;
    }

    void afisareNivel(NOD* rad, int nivel)
    {
        if (rad == NULL)
            return;

        if (nivel == 0)
            cout << rad->info << ' ';
        else
        {
            afisareNivel(rad->st, nivel - 1);
            afisareNivel(rad->dr, nivel - 1);
        }
    }

    void BFS()
    {
        int h = inaltime(radacina);
        for (int nivel = 0; nivel <= h; ++nivel)
            afisareNivel(radacina, nivel);
        cout << endl;
    }

    void afisareArbore(NOD* rad, int spatiu)
    {
        if (rad == NULL)
            return;
        spatiu += SPATIU;

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

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

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

    void stergereArbore(NOD*& rad)
    {
        if (rad == NULL)
            return;

        stergereArbore(rad->st);
        stergereArbore(rad->dr);

        delete rad;
        rad = nullptr;
    }
};

int main()
{
    VECTOR preOrdine, inOrdine;
    preOrdine.citire("preordine.in");
    inOrdine.citire("inordine.in");

    cout << "Parcurgerea in preordine: ";
    preOrdine.afisare();
    cout << "Parcurgerea in inordine: ";
    inOrdine.afisare();

    ARBORE arbore;

    int indexPreordine = 0;
    arbore.radacina = arbore.formareArbore(preOrdine, inOrdine, indexPreordine, 0, preOrdine.sir.size() - 1);
    arbore.afisareArbore(arbore.radacina, 0);

    cout << "\n\nParcurgerea in latime: ";
    arbore.BFS();

    preOrdine.eliberareMemorie();
    inOrdine.eliberareMemorie();
    arbore.stergereArbore(arbore.radacina);

    return 0;
}