listy

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

class drzewo{
private:
    int iowocow, wiek;
public:
    drzewo *next;
    drzewo *right;
    drzewo *left;
    void wstawl(drzewo *d);
    void wstawdl(drzewo *d);
    void wyswietll();
    void wyswietldl();
    void wyswietldll();
    void wyswietldlr();
    int get_iowocow();
    int get_wiek();
    drzewo();
    drzewo(int q, int w);
};
drzewo::drzewo(){
    next = nullptr; //"next = NULL" rowniez byloby poprawne, ale NULL to wartosc, a nullptr; to wskaznik o wartosci NULL, jest to bardzo wazne
    left = nullptr;
    right = nullptr;
    iowocow = rand() % 1000 + 1;
    wiek = rand() % 200 + 1;
}
drzewo::drzewo(int q, int w){
    next = nullptr;
    left = nullptr;
    right = nullptr;
    iowocow = q;
    wiek = w;
};
int drzewo::get_iowocow() {
    return iowocow;
}
int drzewo::get_wiek() {
    return wiek;
}
void drzewo::wyswietll() {
    cout << "Drzew o ilosci owocow : " << iowocow << " oraz wieku : " << wiek << endl;
    if (next)
        next->wyswietll();
}
void drzewo::wyswietldll() {
    if (left)
        left->wyswietldll(); //cout jest na koncu bo dopiero po dojsciu do ostatniego elementu rekurencja zacznie sie
    cout << "Drzew o ilosci owocow : " << iowocow << " oraz wieku : " << wiek << endl; //"cofac" i wyswietlac od lewej do prawej
}
void drzewo::wyswietldlr(){
    cout << "Drzew o ilosci owocow : " << iowocow << " oraz wieku : " << wiek << endl; //cout na poczatku, by kazde nastepne zagniezdzenie rekurencji
    if (right) //wyswietlalo nastepujace, kazdorazowo drzewa po stronie prawej, az do konca listy (do napotkania NULLa)
        right->wyswietldlr();
}
void drzewo::wyswietldl() { //liste dwukierunkowa wyswietlamy wywolujac dla elementu po lewo wyswietlanie "lewe"
    left->wyswietldll();
    if (right) //oraz pozniej, od roota sprawdzajac czy pod wskaznikiem "nastepnym" jest cokolwiek wyswietlamy w prawo
        right->wyswietldlr(); //do czego uzywamy funkcji skladowych w/w
}
void drzewo::wstawl(drzewo *d) { //wstawianie na liste jednokierunkowa
    if (next) { //jesli istnieje nastepny element
        if (next->iowocow < d->iowocow) //sprawdz czy jego ilosc owocow jest mniejsza niz obiektu wstawianego
            next->wstawl(d); //jesli tak wywolaj funkcje rekurencyjnie dla tego nastepnego elementu
        else { //jesli liczba owocow nastepnego drzewa jest wieksza niz wstawianego
            d->next = next; //nastepny element elementu wstawianego to element nastepny elementu rozwazanego
            next = d; //nastepny element elementu rozwazanego to element wstawiany
        }
    }
    else //jesli nie istnieje nastepny element
        next = d; //element wstawiany staje sie nastepnym elementem
}
void drzewo::wstawdl(drzewo *d) { //wstawianie dla listy dwukierunkowej
    if (iowocow < d->iowocow) //root bedzie elementem "srodkowym", sprawdzamy czy wstawiany el.
    {                          // ma wieksza czy mniejsza ilosc owocow niz root
        if (right) //jesli ma wieksza sprawdzamy czy istnieje element po prawo od roota
        {
            if (right->iowocow < d->iowocow) //sprawdzamy czy ilosc owocow nastepnego elementu po prawo jest wieksza niz i.owocow el. wstawianego
                right->wstawdl(d); //jesli jest mniejsza, nastepuje wykonanie rekurencyjne funkcji dla nastepnego elementu po prawo
            else //jesli jest wieksza musimy nadpisac wskazniki w strukturze listy
                {
                d->right = right; //wskaznik "prawy" el. wstawianego ustawiamy na element nastepny od elementu rozwazanego
                d->left = this; //wskaznik "lewy" el. wstawianego ustawiamy na "this" czyli element rozwazany w obecnym wykonaniu funkcji
                right->left = d; //wskaznik "poprzedni" elementu ktory byl nastepny od rozwazanego ustawiamy na element wstawiany
                right = d; //oraz wskaznik "nastepny" elemenetu rozwazanego ustawiamy na element wstawiany
                } //dzieki powyzszym nadpisaniom mozemy wstawic obiekt w srodek listy zachowujac pelna strukture listy dwukierunkowej
        }
        else { //jesli nie to wstawiamy po prawo od el. rozwazanego element wstawiany, a jego wsaznik "poprzedni" ustawiamy na el. rozwazany
            right = d;
            d->left = this;
        }
    }
    else //dzialania analogiczne dla przypadku jesli element wstawiany ma mniejsza ilosc owocow niz root
    {
        if (left)
        {
            if (left->iowocow > d->iowocow)
                left->wstawdl(d);
            else
            {
                d->left = left;
                d->right = this;
                left->right = d;
                left = d;
            }
        }
        else {
            left = d;
            d->right = this;
        }
    }
}

int main() {
    drzewo *rootsingle = new drzewo(); //tworzymy przez wskaznik obiekt bedacy rootem listy jednokierunkowej
    drzewo *rootdouble = new drzewo(); //tworzymy przez wskaznik obiekt bedacy rootem listy dwukierunkowej
    for (int i = 0; i < 50; i++){
        drzewo *nd = new drzewo(); //tworzymy 50 obiektow typu drzewo, ktore dodamy do listy jednokierunkowej
        if (nd->get_iowocow() < rootsingle->get_iowocow()) { //sprawdzamy czy nowoutworzony element nie ma mniejszej i.owocow od roota
            nd->next = rootsingle; //jesli ma, za pomoca odpowiednich napisan wymieniamy roota na jak najmniejszego
            rootsingle = nd;
        }
        else
            rootsingle->wstawl(nd);
    }
    for (int i = 0; i < 100; i++){ //tworzymy 100 obiektow typu drzewo ktore dodamy do listy dwukierunkowej
        drzewo *nd = new drzewo(); //w zwiazku z tym ze liste dwukierunkowa tworzymy od srodka i wyswietlamy "od lewej do prawej"
        rootdouble->wstawdl(nd); //nie ma potrzeby mechanicznego nadpisywania w tym miejscu, bo struktura sortujaca zostanie zachowana
    }
    cout << "Wyswietlam liste jednokierunkowa : " << endl;
    rootsingle->wyswietll();
    cout << endl;
    cout << endl;
    cout << "Wyswietlam liste dwukierunkowa : " << endl;
    rootdouble->wyswietldl();
    system("pause");
    return 0;
}