Struk Lab 5

// Cvor.h
#pragma once
#include <iostream>
using namespace std;

class Cvor {
public:
    int info;
    Cvor* levo;
    Cvor* desno;
    Cvor() {
        info = 0;
        levo = 0;
        desno = 0;
    }
    Cvor(int x) {
        info = x;
        levo = 0;
        desno = 0;
    }
};

// Stablo.h
#pragma once
#include "Header.h"

class Stablo {
    Cvor* root;
    int num;
    void brisac(Cvor* a);
    Cvor* trazi(Cvor* a, Cvor& x);
    Cvor* trazi(Cvor* a, int x);
    void preOrder(Cvor* a);
    Cvor* preOrderOgledalo(Cvor* a, Cvor* b); // WIP
public:
    Stablo();
    Stablo(Cvor& a);
    ~Stablo();
    void insert(int x);
    Cvor* parent(Cvor& a);
    Cvor* sister(Cvor& a);
    bool isLeft(Cvor& a);
    bool isRight(Cvor& a);
    void deleteEl(int x);
    void stampaj();
    Cvor* trazi(int x);
    Stablo* ogledalo();  // WIP
};

// Stablo.cpp
#pragma once
#include "Stablo.h"

Stablo::Stablo() {
    root = 0;
    num = 0;
}

Stablo::Stablo(Cvor& a) {
    root = &a;
    num = 1;
}

Stablo::~Stablo() {
    if (root != 0) {
        brisac(root);
        delete root;
    }
}

void Stablo::brisac(Cvor* a) {
    if (a->levo != 0)
        brisac(a->levo);
    if (a->desno != 0)
        brisac(a->desno);
    delete a->levo;
    delete a->desno;
}

Cvor* Stablo::parent(Cvor& a) {
    return trazi(root, a);
}

Cvor* Stablo::sister(Cvor& a) {
    Cvor* tmp = parent(a);
    if (tmp->levo == &a)
        return tmp->desno;
    else
        return tmp->levo;
}

void Stablo::preOrder(Cvor* a) {
    if (a == 0)
        return;
    cout << a->info << " ";
    preOrder(a->levo);
    preOrder(a->desno);
}

Cvor* Stablo::trazi(Cvor* a, int x) {
    Cvor* tmp = a;
    while (tmp != 0) {
        if (tmp->info == x)
            return tmp;
        if (tmp->info < x)
            tmp = tmp->desno;
        else
            tmp = tmp->levo;
    }
    return 0;
    /*if (a == 0)
        return 0;
    if (a->info == x)
        return a;
    Cvor* x1 = trazi(a->levo, x);
    if (x1 != 0)
        return x1;
    Cvor* x2 = trazi(a->desno, x);
    if (x2 != 0)
        return x2;
    return 0;

    /*Cvor* tmp = a;
    while (tmp != 0) {
        if (tmp->info == x)
            return tmp;
        if (tmp->levo != 0)
            tmp = tmp->levo;
        else
            tmp = tmp->desno;
    }*/
}

Cvor* Stablo::trazi(Cvor* a, Cvor& x) { //MOZDA NE VALJA
    if (a == 0)
        return 0;
    if (a->levo == &x || a->desno == &x)
        return a;
    Cvor* x1 = trazi(a->levo, x);
    if (x1 != 0)
        return x1;
    Cvor* x2 = trazi(a->desno, x);
    if (x2 != 0)
        return x2;
    return 0;
};

Cvor* Stablo::trazi(int x) {
    return trazi(root, x);
}

void Stablo::insert(int x) {
    Cvor* tmp = root;
    Cvor* prev = 0;
    while (tmp != 0) {
        prev = tmp;
        if (tmp->info < x)
            tmp = tmp->desno;
        else
            tmp = tmp->levo;
    }
    if (root == 0)
        root = new Cvor(x);
    else
        if (prev->info < x)
            prev->desno = new Cvor(x);
        else
            prev->levo = new Cvor(x);
    num++;
}

bool Stablo::isLeft(Cvor& a) {
    Cvor* tmp = parent(a);
    if (tmp->levo == &a)
        return true;
    else
        return false;
}

bool Stablo::isRight(Cvor& a) {
    Cvor* tmp = parent(a);
    if (tmp->desno == &a)
        return true;
    else
        return false;
}

void Stablo::deleteEl(int x) {
    Cvor* brisi = trazi(root, x);
    Cvor* brisiP = parent(*brisi);
    if (brisi->levo == 0 && brisi->desno == 0) {
        brisiP->levo = 0;
        brisiP->desno = 0;
        delete brisi;
        num--;
        return;
    }
    if (brisi->levo == 0) {
        if (brisiP->levo == brisi)
            brisiP->levo = brisi->desno;
        else
            brisiP->desno = brisi->desno;
        delete brisi;
        num--;
        return;
    }
    if (brisi->desno == 0) {
        if (brisiP->levo == brisi)
            brisiP->levo = brisi->levo;
        else
            brisiP->desno = brisi->levo;
        delete brisi;
        num--;
        return;
    }
    Cvor* tmp = brisi->levo;
    Cvor* prev = 0;
    while (tmp != 0) {
        prev = tmp;
        tmp = tmp->desno;
    }
    if (prev == brisi->levo) {                // poseeban slucaj
        if (brisiP->levo == brisi)
            brisiP->levo = prev;
        else
            brisiP->desno = prev;
        prev->desno = brisi->desno;
        delete brisi;
        num--;
        return;
    }
    if (prev->levo != 0) {
        parent(*prev)->desno = prev->levo;
    }
    if (brisiP->levo == brisi)
        brisiP->levo = prev;
    else
        brisiP->desno = prev;
    delete brisi;
    num--;
}

void Stablo::stampaj() {
    preOrder(root);
    cout << endl;
}

Cvor* Stablo::preOrderOgledalo(Cvor* a, Cvor* b) {
    b = new Cvor(a->info);
    if (root == 0)
        root = b;
    if (a->desno != 0)
        b->levo = preOrderOgledalo(a->desno, b->levo);
    if (a->levo != 0)
        b->desno = preOrderOgledalo(a->levo, b->desno);
    return b;
}


Stablo* Stablo::ogledalo() {
    Stablo* s = new Stablo;
    s->preOrderOgledalo(root, s->root);
    return s;
}

// mejn
#include "Stablo.h"
#include "Header.h"

void main() {
    Stablo drvo;
    drvo.insert(7);
    drvo.insert(3);
    drvo.insert(2);
    drvo.insert(8);
    drvo.insert(9);
    drvo.insert(5);
    drvo.insert(1);
    drvo.insert(4);
    drvo.stampaj();
    drvo.deleteEl(5);
    drvo.stampaj();
    Cvor* pom = drvo.trazi(4);
    if (drvo.isLeft(*pom))
        cout << "JESTE\n";
    else
        cout << "NIJE\n";
    pom = drvo.trazi(4);
    if (drvo.isLeft(*pom))
        cout << "JESTE\n";
    else
        cout << "NIJE\n";
    pom = drvo.trazi(4);
    if (drvo.isRight(*pom))
        cout << "JESTE\n";
    else
        cout << "NIJE\n";
    Stablo* pok = drvo.ogledalo();
    pok->stampaj();
    delete pok;
}