asp2dz1

#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();
    }
    //MOZDA POPRAVI KONZOLU

    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;
    }
    //OVDE POPRAVI ISPIS


    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 != brojElem - 1) k++; //pozicija gde treba da stavimo element

        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;
        }

        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;
        }

        int poz = k;

        if (flagNiz[k] == 0) {
            niz[k] = key;
            flagNiz[k] = 1;
            k++;
            while (flagNiz[k] == 0) {
                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;
            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++;
            }
        }
        for (int i = 0; i < cnt; i++){
            cout << nizValidnih[i];
        }
        return nizValidnih;
    }
};

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

class binarnoStablo{

private:

    node *root;
    int brojCvorova;

public:
    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){
                    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;
        }
    }

    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){

        queue<int>lq;
        queue<int>mq;
        queue<int>hq;

        lq.push(low);
        mq.push((high+low)/2);
        hq.push(high);


        for (int i = 0; i < high; i++){
            int l = lq.front();
            lq.pop();
            int m = mq.front();
            mq.pop();
            int h = hq.front();
            hq.pop();
            dodajCvor(niz[m]);
            lq.push(l);
            hq.push(m - 1);
            mq.push((l + m - 1) / 2);

            lq.push(m + 1);
            hq.push(h);
            mq.push((m + 1 + h) / 2);

        }


    }


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

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

        while (!q.empty()){
            p = q.front();
            q.pop();
            if (p != nullptr){
                for (int i = 0; i < space / k2 ; i++){
                    cout << " ";
                }
                cout << p->val;
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
            } else if (!q.empty()){
                level++;
                q.push(nullptr);
                cout << endl;
                int pom = k2;
                k2 += k1;
                k1 = pom;
            }

        }

    }

};

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 << "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;
                }
                napravljenoStablo = 1;
                binSt = new binarnoStablo;
                binSt->formirajStabloRek(0, povTab->getZauzetoElem()-1, povTab->nizValidnihElem());
                break;
            case 7:
                if (!napravljenoStablo){
                    cout << "Stablo jos ne postoji!" << endl;
                    break;
                }
                binSt->ispisiStabloX();
                break;
            case 0:
                delete povTab;
                exit(1);
                break;

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


    }

}