BST

q// wezel ktory nie ma rodzica jest korzeniem
// wezel ktory nie ma dziecka jest liściem
// dzielimy drzewo na poziomy

// preorder (root, left, right)
// inorder (left, root, right)
// postorder (left, right, root)

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
using namespace std;

class node // sam w sobie węzeł
{
public:

    int value;
    node* left;
    node* right;

    node();
};

node::node()
{
    value = 0;
    left = nullptr;
    right = nullptr;
}

class binaryTree // klasa obsługująca funkcje drzewa
{
private:

    node* root;

    void inOrderPrint(node* element);
    void postOrderPrint(node* element);
    void preOrderPrint(node* element);
    void destroyTree(node* element);
    void insert(int key, node* element);


public:

    binaryTree();
    ~binaryTree();

    void readDataOfADataFromFile();
    void insert(int key); // dodanie elementu do drzewa
    void destroyTree(); // kasowanie drzewa
    void inOrderPrint();
    void postOrderPrint();
    void preOrderPrint();
};



binaryTree::binaryTree() // na samym początku drzewo będzie puste więc root będzie nullptr
{
    root = nullptr;
}

binaryTree::~binaryTree() // podczas uruchomienia destruktora kasowana jest cała zawartość sterty (czyli tam gdzie są węzły drzewa)
{
    destroyTree();
    cout << "Usuwanie drzewa..." << endl;
}


void binaryTree::destroyTree()
{
    destroyTree(root);
}

void binaryTree::destroyTree(node* element)
{
    if (element != nullptr)
    {
        destroyTree(element->left);
        destroyTree(element->right);
        delete element;
    }
}

void binaryTree::insert(int key, node* element)
{
    if (key < element->value) // elementy mniejsze lądują na lewej stronie, a większą bądź równe na prawej
    {
        if (element->left != nullptr) // jeżeli mamy wartość mniejszą i chcemy ją zapisać jako nowy węzeł
        {                             // ale okaże się, że wskaźnik do następnego elementu istnieje i ma wartość to musimy jeszcze raz wywołać funkcje rekursywnie aby przejść do następnego elementu i od niego stworzyć nowy węzeł
            insert(key, element->left); // tutaj rekursywne przejście do następnego elementu drzewa
        }
        else
        {
            element->left = new node(); // tworzymy nowy węzeł
            element->left->value = key;
            element->left->left = nullptr;
            element->left->right = nullptr;
        }
    }
    else if (key >= element->value) // analogicznie jak dla if(key < element>value)
    {
        if (element->right != nullptr)
        {
            insert(key, element->right);
        }
        else
        {
            element->right = new node();
            element->right->value = key;
            element->right->right = nullptr;
            element->right->left = nullptr;
        }
    }
}

void binaryTree::insert(int key) // funkcja do ogarnięcia czy drzewo jest puste czy nie
{
    if (root != nullptr)
    {
        insert(key, root); // jeżeli nie jest pusta to lecimy z prywatną metodą insert(int key, node* element), która leci po całym drzewie szukając odpowiedniego węzła do stworzenia drzewa
    }
    else // jeżeli drzewo jest puste to tworzymy pierwszy węzeł drzewa (korzeń)
    {
        root = new node();
        root->value = key;
        root->left = nullptr;
        root->right = nullptr;
    }
}

void binaryTree::inOrderPrint(node* element) // (left, root, right)
{

    if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
    {
        return;
    }
    inOrderPrint(element->left);
    cout << element->value << endl;
    inOrderPrint(element->right);
}

void binaryTree::inOrderPrint() // (left, root, right)
{
    inOrderPrint(root);
    cout << endl;
}


void binaryTree::postOrderPrint(node* element) // (left, right, root)
{
    if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
    {
        return;
    }
    postOrderPrint(element->left);
    postOrderPrint(element->right);
    cout << element->value << endl;


}

void binaryTree::postOrderPrint() // (left, right, root)
{
    postOrderPrint(root);
    cout << endl;
}

void binaryTree::preOrderPrint(node* element) // (root, left, right)
{
    if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
    {
        return;
    }
    cout << element->value << endl;
    preOrderPrint(element->left);
    preOrderPrint(element->right);
}

void binaryTree::preOrderPrint() // (root, left, right)
{
    preOrderPrint(root);
    cout << endl;
}

void binaryTree::readDataOfADataFromFile()
{
    string line;
    int number;
    fstream plik;

    plik.open("lista.txt", ios::in); // powiązanie strumienia z plikiem

    if (plik.good() == false) // jezeli jest zamkniety to error
    {
        cout << "Plik nie istnieje" << endl;
        exit(EXIT_FAILURE);
    }
    else // jezeli nie lecimy
    {
        while (!plik.eof()) // działa dopóty, dopóki coś sie nie "zepsuje"
        {
            getline(plik, line, ' ');
            number = atoi(line.c_str());

            insert(number); // funkcja zrobi z tego co wczytalismy liste
        }
    }
    plik.close(); // zamykanie
}


int main()
{
    binaryTree* tree = new binaryTree();

    tree->readDataOfADataFromFile();

    tree->preOrderPrint(); // (root, left, right), 15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20 (ok, dobrze działa) (poza zerem)
    //tree->inOrderPrint(); // (left, root, right), 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 (ok, dobrze działa) (poza zerem)
    //tree->postOrderPrint(); // (left, right, root), 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15 (ok, dobrze działa) (poza zerem)

    delete tree; // trzeba to jawnie zainicjować ponieważ wtedy wywoła się domyślny destruktor bez ciała


    return 0;
}