AISD_Drzewa_v2

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <fstream>

using namespace std;

// struktura pojedynczego wezla
struct Element
{
    int klucz;
    Element *wsk_prawy;
    Element *wsk_lewy;
    // konstruktor automatycznie ustawia odpowiednie wartosci
    Element(int wartosc)
    {
        klucz = wartosc;
        wsk_prawy = NULL;
        wsk_lewy = NULL;
    }
};

// generuje malejacy ciag o odpowiedniej dlugosci
void generate_sequence(int sequence_size, vector <int> &numbers)
{
    srand(time(NULL));
    numbers.push_back(rand()%100+1);
    for(int i = 1; i < sequence_size; i++)
    {
        numbers.insert(numbers.begin(), numbers[0]+rand()%100+1);
    }
}

// przeksztalca ciag poprzez polowienie binarne na ciag, ktory pozwoli zbudowac drzewo AVL
//                    FROM                  TO
void sequence_for_AVL(vector <int> numbers, vector <int> &numbers_altered, int lewy, int prawy)
{
    int srodek = (lewy+prawy)/2;
    //cout << "Numbers[srodek] " << "[" << srodek << "] " << numbers[srodek] << endl;
    numbers_altered.push_back(numbers[srodek]);
    // wywoluje polowienie rekurencyjnie
    if(srodek-lewy>0)
    {
        sequence_for_AVL(numbers, numbers_altered, lewy, srodek);
    }
    if(prawy-srodek>1)
    {
        sequence_for_AVL(numbers, numbers_altered, srodek+1, prawy);
    }
}

// dodaje element (wartosc) do drzewa
void add_element(Element * & wezel, int wartosc)
{
    // jezeli wezel jest pusty to po prostu wstawia na niego nowy element
    if(wezel == NULL)
    {
        wezel = new Element(wartosc);
    }
    // jezeli nie no to wywolujemy funkcje rekurencyjnie dla lewego syna lub prawego
    else
    {
        if(wartosc > wezel->klucz)
        {
            add_element(wezel->wsk_prawy, wartosc);
        }
        if(wartosc < wezel->klucz)
        {
            add_element(wezel->wsk_lewy, wartosc);
        }
    }
}

void wyszukaj_MAX(Element * & wezel)
{
    if(wezel->wsk_prawy == NULL)
    {
        cout << endl;
        cout << "MAX: " << wezel->klucz << endl;
        cout << "---KONIEC PROCEDURY---" << endl;
    }
    else
    {
        cout << wezel->klucz << " ";
        wyszukaj_MAX(wezel->wsk_prawy);
    }
}

int wyszukaj_element(int klucz, Element * & wezel)
{
    if(wezel == NULL)
        return NULL;
    if(wezel->klucz == klucz)
    {
        return int(&wezel);
    }
    else if(wezel->klucz > klucz)
    {
        wyszukaj_element(klucz, wezel->wsk_prawy);
    }
    else
    {
        wyszukaj_element(klucz, wezel->wsk_lewy);
    }
}

// NIE WIEM czy nie trzeba rozdzielic tego na dwie funkcje - szukanie elementu i usuwanie elementu
void usuwanie_elementu(int klucz, Element * & wezel)
{
    if(wezel == NULL)
        return;
    if(wezel->klucz == klucz)
    {
        // To DO
    }
    else if(wezel->klucz > klucz)
    {
        usuwanie_elementu(klucz, wezel->wsk_prawy);
    }
    else
    {
        usuwanie_elementu(klucz, wezel->wsk_lewy);
    }
}

// wyswietla cale drzewo w porzadku pre-order
void wyswietl_preorder(Element * & wezel)
{
    if(wezel == NULL)
        return;
    cout << wezel->klucz << " ";
    wyswietl_preorder(wezel->wsk_lewy);
    wyswietl_preorder(wezel->wsk_prawy);
}

// wyswietla cale drzewo w porzadku in-order
void wyswietl_inorder(Element * & wezel)
{
    if(wezel == NULL)
        return;
    wyswietl_inorder(wezel->wsk_lewy);
    cout << wezel->klucz << " ";
    wyswietl_inorder(wezel->wsk_prawy);
}


// usuwa cale drzewo w porzadku post-order
void usun_postorder(Element * & wezel)
{
    if(wezel == NULL)
        return;
    usun_postorder(wezel->wsk_lewy);
    usun_postorder(wezel->wsk_prawy);
    delete wezel;
}

int main()
{
    int sequence_size;
    bool proper_value;
    bool quit = false;
    bool good_input = false;
    int choice;
    int klucz_usuwania;
    vector <int> numbers;
    vector <int> numbers_altered;
    Element *root_BST = NULL;
    Element *root_AVL = NULL;
    while(!quit)
    {
        proper_value = false;
        while(!proper_value)
        {
            cout << "Podaj wielkosc ciagu malejacego: ";
            cin >> sequence_size;
            if(cin && sequence_size > 0)
            {
                generate_sequence(sequence_size, numbers);
                sequence_for_AVL(numbers, numbers_altered, 0, numbers.size());
                // tworzenie drzew BST i AVL
                for(int i = 0; i<numbers.size(); i++)
                {
                    add_element(root_BST, numbers[i]);
                    add_element(root_AVL, numbers_altered[i]);
                }
                // wyjscie z petli wewnetrznej programu
                proper_value = true;
            }
        }
        while(!good_input)
        {
            // do zrobienia:  2  6  7
            cout << "Wybierz akcje: 1)Wyszukaj MAX, 2)Usun wybrane wezly, 3)Wypisz in-order" << endl;
            cout << "4)Wypisz pre-order, 5)Usun drzewo post-order, 6)Wypisz poddrzewo (pre-order)," << endl;
            cout << "7)Rownowarz drzewo BST(DSW), 8)Wyjscie, Wybor:";
            cin >> choice;
            if(cin && choice > 0 && choice < 9)
            {
                good_input = true;
            }
        }
        switch(choice)
        {
        case 1:
            cout << "Sciezka BST: ";
            wyszukaj_MAX(root_BST);
            cout << endl;
            cout << "Sciezka AVL: ";
            wyszukaj_MAX(root_AVL);
            break;
        /*case 2:
            int ile_usunac;
            int klucz;
            bool user_input = false;
            while(!user_input)
            {
                cout << "Ile wezlow usunac?:";
                cin >> ile_usunac;
                if(cin && ile_usunac > 0 && ile_usunac < numbers.size())
                {
                    user_input == true;
                }
            }
            for(int i = 1; i<=ile_usunac; i++)
            {
                cout << "[" << i << "] klucz:";
                cin >> klucz;
                if(!cin)
                {
                    cout << "Zly input!" << endl;
                    exit(0);
                }
                else
                {
                    usuwanie_elementu(klucz, root_BST);
                    usuwanie_elementu(klucz, root_AVL);
                }
            }
            break;*/
        case 3:
            cout << "BST pre-order: " << endl;
            wyswietl_preorder(root_BST);
            cout << endl;
            cout << "--- KONIEC PROCEDURY ---" << endl;
            cout << "AVL pre-order: " << endl;
            wyswietl_preorder(root_AVL);
            cout << endl;
            cout << "--- KONIEC PROCEDURY ---" << endl;
            break;
        case 4:
            cout << "BST in-order: " << endl;
            wyswietl_inorder(root_BST);
            cout << endl;
            cout << "--- KONIEC PROCEDURY ---" << endl;
            cout << "AVL in-order: " << endl;
            wyswietl_inorder(root_AVL);
            cout << endl;
            cout << "--- KONIEC PROCEDURY ---" << endl;
            break;
        case 5:
            cout << "BST usun post-order... " << endl;
            usun_postorder(root_BST);
            cout << endl;
            cout << "--- KONIEC PROCEDURY ---" << endl;
            cout << "AVL usun post-order... " << endl;
            usun_postorder(root_AVL);
            cout << endl;
            cout << "--- KONIEC PROCEDURY ---" << endl;
            break;
        /*case 6:
            cout << "Usuwanie poddrzewa. Podaj klucz: ";
            cin >> klucz_usuwania;
            if(!cin)
            {
                cout << "Blad wejscia!" << endl;
                exit(0);
            }
            cout << "USUWANIE Z BST..." << endl;
            if(wyszukaj_element(klucz_usuwania, root_BST))
            {
                usun_postorder(wyszukaj_element(klucz_usuwania, root_BST));
            }
            cout << "USUWANIE Z AVL..." << endl;
            if(wyszukaj_element(klucz_usuwania, root_AVL))
            {
                usun_postorder(wyszukaj_element(klucz_usuwania, root_AVL);
            }
            cout << "--- KONIEC PROCEDURY ---" << endl;
        */
        case 8:
            exit(0);
            break;
        }

    }
    return 0;
}