aps2dz1KRAJ

#include <iostream>
#include <string>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

const int MAX = 100;

class povecanaTabela {

private:

    int brojElem;
    int zauzetoElem;
    int prosirenje;
    int *niz, *flagNiz;

    void sort(int* &niz, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (niz[i] > niz[j]) {
                    int pom = niz[i];
                    niz[i] = niz[j];
                    niz[j] = pom;
                }
            }
        }
    }

    void realociraj() {
        cout << endl << "Doslo je do realokacije tabele!!!" << endl;
        int k = 2 * brojElem;
        int *niz2 = new int[k];
        int *flagNiz2 = new int[k];

        for (int i = 0; i < k; i++) {
            niz2[i] = niz[i / 2];
            flagNiz2[i] = (i % 2 ? 0 : 1);
        }

        delete[] niz;
        delete[] flagNiz;
        flagNiz = flagNiz2;
        niz = niz2;
        brojElem *= 2;
    }

    int ternPret(int key) const {
        int low = 0;
        int high = brojElem - 1;

        while (high >= low) {
            int p1 = low + ceil((high - low)) / 3;
            int p2 = high - ceil((high - low)) / 3;

            if (key == niz[p1]) {
                int k = p1;
                while (flagNiz[k] == 0 and k >= 0) {
                    if (niz[k] != key) break;
                    k--;
                }
                if (niz[k] == key and flagNiz[k] == 1) return k;
                else {
                    while (flagNiz[k] == 0) k++;
                    if (niz[k] == key) return k;
                }

            }
            else if (key == niz[p2]) {
                int k = p2;
                while (flagNiz[k] == 0 and k >= 0) {
                    if (niz[k] != key) break;
                    k--;
                }
                if (niz[k] == key and flagNiz[k] == 1) return k;

            }
            else if (key < niz[p1]) high = p1 - 1;
            else if (key > niz[p1] and key < niz[p2]) {
                low = p1;
                high = p2 - 1;
            }
            else if (key > niz[p2]) low = p2 + 1;
        }

        int k = low;
        while (k >= 0) {
            if (flagNiz[k] == 1 and niz[k] < key) break;
            k--;
        }
        while (flagNiz[k] == 1 and niz[k] == key) k++;
        if (k == 0 and key < niz[k]) return -1;
        else return k;
    }     //UVEK VRACA ELEMENT IZA KOGA TREBA DA SE UBACI NOVI ELEMENT




public:
    ~povecanaTabela() {
        delete[] niz;
        delete[] flagNiz;
    }
    int getBrojElem()const {
        return brojElem;
    }
    int getZauzetoElem()const {
        return zauzetoElem;
    }
    int getProsirenje()const {
        return prosirenje;
    }

    void formirajTabelu() {
        cout << "Unesite broj elemenata tabele: " << endl;
        int n;
        cin >> n;

        if (n < 1 or n > MAX) {
            cout << "Nevazeci broj elemenata!" << endl;
            return;
        }

        int *nizx = new int[n];
        for (int i = 0; i < n; i++) {
            cout << "Unesite " << i + 1 << ". element tabele: ";
            cin >> nizx[i];
        }
        sort(nizx, n);
        cout << "Unesite prosirenje: ";
        int p;
        cin >> p;

        int *niz2 = new int[n * p];
        flagNiz = new int[n * p];

        for (int i = 0; i < n * p; i++) {
            niz2[i] = nizx[i / p];
            flagNiz[i] = (i % p == 0 ? 1 : 0);
        }

        delete[] nizx;
        this->niz = niz2;
        this->brojElem = n * p;
        this->prosirenje = p;
        this->zauzetoElem = n;
        cout << endl << "Tabela uspesno formirana! Ispis: " << endl;
        this->ispisiTabelu();
    }

    void ispisiTabelu() const {
        cout << endl;
        for (int i = 0; i < brojElem; i++) {
            cout << niz[i] << "|";
        }
        cout << endl;
        for (int i = 0; i < brojElem; i++) {
            cout << flagNiz[i] << "|";
        }
        cout << endl;
    }



    void ispisiElem(int key) const {
        int k = ternPret(key);
        if (niz[k] == key and flagNiz[k] == 1) {
            cout << "Element " << key << " nadjen na poziciji " << k << "." << endl;
            return;
        }
        else {
            cout << "Nije nadjen element koji ima vrednost " << key << endl;
            return;
        }
    }

    void umetanjeKljuca(int key) {

        if (zauzetoElem == brojElem) realociraj();

        int k = ternPret(key);

        if (k == -1) {
            k = 0;
            while (1) {
                if (flagNiz[k] == 0) break;
                k++;
            }
            for (int i = k; i > 0; i--) {
                flagNiz[i] = flagNiz[i - 1];
                niz[i] = niz[i - 1];
            }
            flagNiz[0] = 1;
            niz[0] = key;
            zauzetoElem++;
            cout << "Kljuc uspesno umetnut na poziciji " << 0 << endl;
            return;
        }

        else if (k == brojElem - 1) {
            while (1) {
                if (flagNiz[k] == 0) break;
                k--;
            }
            for (int i = k; i < brojElem - 1; i++) {
                flagNiz[i] = flagNiz[i + 1];
                niz[i] = niz[i + 1];
            }
            flagNiz[brojElem - 1] = 1;
            niz[brojElem - 1] = key;
            zauzetoElem++;
            cout << "Kljuc uspesno umetnut na poziciji " << brojElem - 1 << endl;
            return;
        }

        if (k != brojElem - 1 and k!=-1) k++; //pozicija gde treba da stavimo element
        int poz = k;

        if (flagNiz[k] == 0) {
            niz[k] = key;
            flagNiz[k] = 1;
            k++;
            while (flagNiz[k] == 0 and k < brojElem) {
                niz[k] = key;
                k++;
            }
            zauzetoElem++;
            cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
            return;
        }

        // trazenje mesta udesno

        else {
            while (k < brojElem - 1) {
                if (flagNiz[k] == 0) break;
                k++;
            }
            if (flagNiz[k] == 0) {
                for (int i = k; i > poz; i--) {
                    niz[i] = niz[i - 1];
                    flagNiz[i] = flagNiz[i - 1];
                }
                niz[poz] = key;
                flagNiz[poz] = 1;
                zauzetoElem++;
                cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
                return;
            }

            // trazenje mesta ulevo

            poz--;

            while (k >= 0) {
                if (flagNiz[k] == 0) break;
                k--;
            }

            if (flagNiz[k] == 0) {
                for (int i = k; i < poz; i++) {
                    niz[i] = niz[i + 1];
                    flagNiz[i] = flagNiz[i + 1];
                }
                niz[poz] = key;
                flagNiz[poz] = 1;
                zauzetoElem++;
                cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
                return;
            }
        }
    }

    void brisanjeKljuca(int key) {
        int k = ternPret(key);
        if (niz[k] == key and flagNiz[k] == 1) {
            flagNiz[k] = 0;
            cout << "Uspesno brisanje kljuca na poziciji " << k << endl;
            zauzetoElem--;
            return;
        }
        else {
            cout << "Element nije pronadjen ili je nevazeci! " << endl;
        }
    }

    int* nizValidnihElem() const {
        int *nizValidnih = new int[zauzetoElem];
        int cnt = 0;
        for (int i = 0; i < brojElem; i++) {
            if (flagNiz[i]) {
                nizValidnih[cnt] = niz[i];
                cnt++;
            }
        }
        cout << "Od sledecih elemenata se pravi stablo:"<<endl;
        for (int i = 0; i < cnt; i++) {
            cout << nizValidnih[i] << " ";
        }
        cout << endl;
        return nizValidnih;
    }
};

typedef struct node {
    node *father;
    node *left;
    node *right;
    int val;
    int brojCvorova;
}node;

class binarnoStablo {

private:

    node *root;
    int brojCvorova;

public:

    ~binarnoStablo() {

        queue <node*> q;
        node *p = root;
        q.push(p);

        while (!q.empty()) {
            p = q.front();
            q.pop();
            if (p != nullptr) {
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
            }
            delete p;
        }

    }

    node *getRoot() const {
        return root;
    }
    binarnoStablo() {
        brojCvorova = 0;
    }

    void dodajCvor(int val) {
        node *n = new node;
        n->val = val;
        n->left = nullptr;
        n->right = nullptr;
        if (brojCvorova == 0) {
            n->father = nullptr;
            root = n;
            brojCvorova++;
            return;
        }
        else {
            node *p = root;
            node *f = nullptr;
            while (p) {
                if (val == p->val) {
                    cout << endl << "Broj kljuceva koji imaju vrenost " << val << " je povecan za 1!" << endl;
                    p->brojCvorova++;
                    return;
                }
                else if (val < p->val) {
                    f = p;
                    p = p->left;
                }
                else if (val > p->val) {
                    f = p;
                    p = p->right;
                }
            }

            if (f->val > val) {
                f->left = n;
            }
            else if (f->val < val) {
                f->right = n;
            }
            n->father = f;
            brojCvorova++;
            return;
        }
    }

    //Ne koristi se
    void formirajStabloRek(int low, int high, int *niz) {
        if (low <= high) {
            int mid = (high + low) / 2;
            dodajCvor(niz[mid]);
            formirajStabloRek(low, mid - 1, niz);
            formirajStabloRek(mid + 1, high, niz);
        }
    }

    void formirajStablo(int low, int high, int *niz) {

        stack<int>s1;
        stack<int>s2;
        int mid = ceil((low + high) / 2);
        dodajCvor(niz[mid]);
        s1.push(mid + 1);
        s2.push(high);
        high = mid - 1;
        while (low <= high) {
            mid = ceil((low + high) / 2);
            dodajCvor(niz[mid]);
            s1.push(mid + 1);
            s2.push(high);
            high = mid - 1;
        }
        while (!s1.empty()) {
            low = s1.top();
            s1.pop();
            high = s2.top();
            s2.pop();
            if (low <= high) {
                mid = ceil((low + high) / 2);
                dodajCvor(niz[mid]);
                s1.push(mid + 1);
                s2.push(high);
                high = mid - 1;
                while (low <= high) {
                    mid = ceil((low + high) / 2);
                    dodajCvor(niz[mid]);
                    s1.push(mid + 1);
                    s2.push(high);
                    high = mid - 1;
                }
            }
        }
    }


    void ispisiStabloX() const {
        int space = (int)pow(brojCvorova, 1.71);
        int level = 0;

        queue <node*> q;
        node *p = root;
        q.push(p);
        q.push(nullptr);
        int k1 = 2;

        while (!q.empty()) {
            p = q.front();
            q.pop();
            if (p != nullptr) {
                for (int i = 0; i < space / k1; i++) {
                    cout << " ";
                }
                if (p->val != -243){
                    cout << p->val;
                    if (p->left) q.push(p->left);
                    else {
                        node *pom = new node;
                        pom->val = -243; // KARAKTERISTICNA VREDNOST
                        q.push(pom);
                    }
                    if (p->right) q.push(p->right);
                    else {
                        node *pom = new node;
                        pom->val = -243; // KARAKTERISTICNA VREDNOST
                        q.push(pom);
                    }
                } else {
                    if (p->val == -243) delete p;
                }

            }
            else if (!q.empty()) {
                level++;
                q.push(nullptr);
                cout << endl;
                k1 = pow(2,level) + 1;
            }

        }

    }

    void ispisiKljuc(int key) const {

        cout << "Putanja do trazenog kljuca je: " << endl;
        node *p = root;
        while (p) {
            cout << p->val;
            if (p->val > key) p = p->left;
            else if (p->val < key) p = p->right;
            else if (p->val == key) return;
            cout << "->";
        }

        if (p == nullptr) cout << "Nema trazenog elementa!" << endl;
    }

    void rotirajCvor(int val) {

        node *p = root;

        while (p) {
            if (val == p->val) break;
            else if (val < p->val) p = p->left;
            else if (val > p->val) p = p->right;
        }

        if (!p) {
            cout << "Nema trazenog cvora! " << endl;
            return;
        }

        cout << "Za levu rotaciju unesite 1, a za desnu 2: ";
        int r;
        cin >> r;
        while (r != 1 and r != 2) {
            cout << "Nevalidna vrednost!" << endl;
            cout << "Za levu rotaciju unesite 1, a za desnu 2: ";
            cin >> r;
        }
        if (r == 1) {


            node *y = p->right;
            if (!y){
                cout << "Nemoguca rotacija!" << endl;
                return;
            }
            node *temp = y->left;
            if (p == root) {
                root = y;
            }
            y->left = p;
            if (p) p->father = y;
            p->right = temp;
            if (temp) temp->father = p;
        }
        else if (r == 2) {

            node *y = p->left;
            if (!y){
                cout << "Nemoguca rotacija!" << endl;
                return;
            }
            node *temp = y->right;
            if (p == root) {
                root = y;
            }
            y->right = p;
            if (p) p->father = y;
            p->left = temp;
            if (temp) temp->father = p;

        }

    }

};

void konzola() {
    cout << endl << "Unosom rednog broja izaberite komandu: " << endl << endl;
    cout << "1. Pravljenje i inicijalizacija prosirene tabele" << endl;
    cout << "2. Ispisivanje indeksa(pozicije) odredjenog elementa u tabeli" << endl;
    cout << "3. Umetanje odredjenog elementa u tabelu" << endl;
    cout << "4. Brisanje odredjenog elementa iz tabele" << endl;
    cout << "5. Ispis cele tabele" << endl;
    cout << "6. Formiraj binarno stablo prema tabeli" << endl;
    cout << "7. Ispisi binarno stablo" << endl;
    cout << "8. Pronadji zadati kljuc u stablu" << endl;
    cout << "9. Dodaj novi kljuc u stablo" << endl;
    cout << "10. Rotiraj zadati cvor u stablu" << endl;
    cout << "0. Izlazak iz programa" << endl << endl << endl;
}


int main(void) {

    cout << "Dobrodosli u program!!! :) :) :)" << endl;
    int napravljenaTabela = 0;
    int napravljenoStablo = 0;
    povecanaTabela *povTab = nullptr;
    binarnoStablo *binSt = nullptr;



    while (1) {
        konzola();
        cout << "Unesite komandu: ";
        int komanda;
        cin >> komanda;
        int key;
        switch (komanda) {
            case 1:
                if (napravljenaTabela) {
                    cout << "Tabela je vec napravljena!" << endl;
                    break;
                }
                cout << "Formiranje povecane tabele: " << endl;
                povTab = new povecanaTabela;
                povTab->formirajTabelu();
                napravljenaTabela = 1;
                break;
            case 2:
                if (!napravljenaTabela) {
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite element(key) za pretragu: ";
                cin >> key;
                povTab->ispisiElem(key);
                break;
            case 3:
                if (!napravljenaTabela) {
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite vrednost elementa koji stavljate u tabelu: ";
                cin >> key;
                povTab->umetanjeKljuca(key);
                povTab->ispisiTabelu();
                break;
            case 4:
                if (!napravljenaTabela) {
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite vrednost(key) elementa za brisanje: ";
                cin >> key;
                povTab->brisanjeKljuca(key);
                povTab->ispisiTabelu();
                break;
            case 5:
                if (!napravljenaTabela) {
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Ispis cele tabele: " << endl;
                povTab->ispisiTabelu();
                break;
            case 6:
                if (napravljenoStablo) {
                    cout << "Stablo je vec napravljeno!" << endl;
                    break;
                }
                else if (!napravljenaTabela) {
                    cout << "Morate prvo napraviti tabelu!" << endl;
                    break;
                }
                napravljenoStablo = 1;
                binSt = new binarnoStablo;
                binSt->formirajStablo(0, povTab->getZauzetoElem() - 1, povTab->nizValidnihElem());
                break;
            case 7:
                if (!napravljenoStablo) {
                    cout << "Stablo jos ne postoji!" << endl;
                    break;
                }
                binSt->ispisiStabloX();
                break;
            case 8:
                if (!napravljenoStablo) {
                    cout << "Stablo jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite broj koji trazite u stablu: ";
                cin >> key;
                binSt->ispisiKljuc(key);
                break;
            case 9:
                if (!napravljenoStablo) {
                    cout << "Stablo jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite broj koji dodajete u stablo: ";
                cin >> key;
                binSt->dodajCvor(key);
                break;
            case 10:
                if (!napravljenoStablo) {
                    cout << "Stablo jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite element oko koga zelite da napravite rotaciju: ";
                cin >> key;
                binSt->rotirajCvor(key);
                cout << endl << "Stanje stabla posle rotiranja: " << endl;
                binSt->ispisiStabloX();
                break;
            case 0:
                delete povTab;
                delete binSt;
                exit(1);
                break;

            default:
                cout << "Nevazeca komanda!!!" << endl;
                break;
        }
    }
}