#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 Zacznę od tego, że zadanie jest zrobione w C++, według wymagań zadania jest to dozwolone.
 Jest to spowodowane tym, że jednym z wymogów strukturalnego C jest brak globalnej zmiennej na roota.
 Generalnie przekazywanie za każdym razem korzenia jest problematyczne, więc wolałem to zrobić obiektowo w C++. Sorry
*/

using namespace std; // określenie przestrzeni nazwy

class Tree;

// klasa węzła drzewa, na podstawie której tworzone są obiekty węzła
class TreeNode
{
    int key; // klucz węzla
    char tab[10]; // tablica znaków

    TreeNode* left; // wskaźnik na lewego potomka
    TreeNode* right; // wskaźnik na prawego potomka

    TreeNode(int); // konstruktor, czyli funkcja, na podstawie której jest tworzony obiekt

    friend class Tree; // to jest po to, żeby klasa Tree mogła korzystać ze składników tej klasy
};

class Tree
{
    int count; // zmienna przechowująca ilość elementów w drzewie
    TreeNode* root; // wskaźnik na korzeń drzewa

public:
    Tree(); // konstruktor drzewa, czyli jego inicjalizacja
    ~Tree(); // destruktor drzewa, który wypierdala z pamięci wszystkie

    void addNode(int); // dodawanie elementu do drzewa
    void fillTree(int); // zapełnianie drzewa losowymi elementami

    TreeNode* search(int); // szukanie elementu po kluczu podanym w parametrze
    TreeNode* findParent(TreeNode*); // szukanie rodzica elementu
    TreeNode* findSuccessor(TreeNode*); // szukanie nastepnika elementu

    void deleteNode(int); // wypierdalanie elementu z drzewa
    void clearTree(); // wypierdolenie wszystkich elementów z drzewa

    void preOrder(TreeNode*); // wyświetlanie w trybie preorder
    void inOrder(TreeNode*); // wyświetlanie w trybie inorder
    void postOrder(TreeNode*); // domyśl się

    void printPreOrder();
    void printInOrder();
    void printPostOrder();
};

int main()
{
    srand((unsigned int) time(NULL)); // inicjalizacja generatora pseudolosowości

    FILE* file = fopen("inlab03.txt", "r"); // to już było

    // to też
    if (!file)
    {
        cerr << "Niepowodzenie przy otwarciu pliku!" << endl << endl;
        exit(EXIT_FAILURE);
    }

    // tu również bez niespodzianek
    int X, k1, k2, k3, k4;

    fscanf(file, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);
    fclose(file);

    clock_t start = clock();

    Tree* tree = new Tree(); // tu jest inicjalizacja

    tree->deleteNode(k1);
    tree->deleteNode(k1);
    tree->fillTree(X);
    tree->printInOrder();
    tree->printPreOrder();
    tree->addNode(k2);
    tree->printInOrder();
    tree->addNode(k3);
    tree->addNode(k4);
    tree->deleteNode(k1);
    tree->printPreOrder();
    tree->search(k1);
    tree->deleteNode(k2);
    tree->printInOrder();
    tree->deleteNode(k3);
    tree->deleteNode(k4);

    clock_t stop = clock();
    cout << fixed << "Time spent: " << (double) (stop - start) / CLOCKS_PER_SEC << endl << endl;

    delete tree; // porządki
}

// konstruktor, który jest wywoływany przy tworzeniu nowego elementu drzewa
TreeNode::TreeNode(int key)
{
    this->key = key;

    sprintf(this->tab, "%d", key); // ta funkcja tworzy do tablicy znaków ciąg znaków na podstawie keya

    // każdy nowy element nie ma dzieci
    this->left = NULL;
    this->right = NULL;
}

// konstruktor drzewa
Tree::Tree()
{
    root = NULL;
}

void Tree::addNode(int key)
{

    // jeżeli w drzewie nic nie ma, to root jest nowym elementem
    if (!root)
    {
        root = new TreeNode(key); // tak tworzy się nowy element
        return; // kończymy zabawę w tej funkcji
    }

    TreeNode* temp = root; // ustawiamy się na rootcie

    // szukanie miejsca na nowy element
    while (temp)
    {
        // jeżeli klucz jest już w drzewie, to kończymy się bawić tą funkcją
        if (temp->key == key)
            return;

        // jeżeli klucz jest mniejszy od klucza tempa, to idziemy na lewo, jak nie, to na prawo
        if (key < temp->key)
            // jeżeli nie ma lewego potomka, to znaleźliśmy miejsce na nowy element
            if (temp->left)
                temp = temp->left;
            else
                break;
        else
            // analogicznie w przypadku prawego potomka
            if (temp->right)
                temp = temp->right;
            else
                break;
    }

    TreeNode* newNode = new TreeNode(key); // tworzymy nowy węzeł

    // wkładamy element do drzewa w taki sposób
    if (key < temp->key)
        temp->left = newNode;
    else
        temp->right = newNode;
}

void Tree::fillTree(int X)
{
    // tu bez niespodzianek
    for (int i = 0; i < X; i++)
        addNode(-10000 + rand()%20001); // zakres podałem własny, ponieważ w dokumencie był podany od 10000 do 10000. Uznałem to za błąd, więc jak się ktoś przyczepi, zamień zakres tutaj
}

TreeNode* Tree::search(int key)
{
    if (!root)
        return NULL;

    TreeNode* temp = root; // ustawiamy się standardowo na rootcie

    // szukamy elementu, jeżeli znajdziemy, to zwracamy wskaźnik, jeśli nie, to zwracamy nulla
    while (temp)
    {
        if (temp->key == key)
            return temp;

        if (key < temp->key)
            temp = temp->left;
        else
            temp = temp->right;
    }

    return NULL;
}

TreeNode* Tree::findParent(TreeNode* child)
{
    //chyba nie muszę tłumaczyć
    if (!root)
        return NULL;

    if (!child)
        return NULL;

    if (child == root)
        return NULL;

    TreeNode* temp = root;

    /// jeżeli lewy potomek, lub prawy jest jest naszym childem, to zwracamy ten wskaźnik
    while (temp)
    {
        if (temp->left == child || temp->right == child)
            return temp;

        if (child->key < temp->key)
            temp = temp->left;
        else
            temp = temp->right;
    }

    return NULL; // to się wykona, jeżeli nie znajdziemy rodzica, czyli roota
}

TreeNode* Tree::findSuccessor(TreeNode* target)
{
    if (!root)
        return NULL;

    // żeby znaleźć następnika, trzeba iść na prawo, potem do oporu w lewo
    TreeNode* temp = target->right;

    while (temp->left)
        temp = temp->left;

    return temp;
}

void Tree::deleteNode(int key)
{
    if (!root)
    {
        cout << "Drzewo jest puste" << endl;
        return;
    }

    // szukamy węzła docelowego oraz jego rodzica
    TreeNode* temp = search(key);
    TreeNode* parent = findParent(temp);

    // jeżeli parent jest nullem, to znaczy, że musimy usunąć roota
    if (!parent)
    {
        // jeżeli root nie ma potomków, to po prostu kasujemy roota i wyjebane
        if (!root->left && !root->right)
        {
            delete root;
            root = NULL;

            return;
        }

        // jeżeli root ma tylko lewego potomka, to kasujemy roota i podciągamy jego lewego potomka na miejsce roota
        if (root->left && !root->right)
        {
            TreeNode* left = root->left;
            delete root;
            root = left;

            return;
        }

        // analogicznie, jeżeli root ma tylko prawego potomka
        if (!root->left && root->right)
        {
            TreeNode* right = root->right;
            delete root;
            root = right;

            return;
        }

        // pobieramy sobie następnika i rodzica następnika
        TreeNode* successor = findSuccessor(root);
        TreeNode* parentSuccessor = findParent(successor);

        // jeżeli rodzic następnika jest rootem, to znaczy, że wystarczy tylko wstawić następnika na miejsce roota i podpiąć lewe poddrzewo roota do lewego wskaźnika successora
        if (parentSuccessor == root)
        {
            TreeNode* rootLeft = successor->left;

            delete root;
            root = successor;

            root->left = rootLeft;
        }
        else // w przeciwnym wypadku pod następnika podpinamy lewe i prawe poddrzewo roota, a prawe podrzewo nastepnika podpinamy pod lewy wskaźnik rodzica następnika
        {
            TreeNode* successorRight = successor->right;

            successor->left = root->left;
            successor->right = root->right;

            delete root;
            root = successor;

            parentSuccessor->left = successorRight;
        }

        return;
    }


    // w przypadku innego węzła, niż roota, musimy też następnik podpiąć pod lewe lub prawe poddrzewo rodzica usuwanego węzła w zależności od sytuacji. Reszta jest taka sama
    if (!temp->left && !temp->right)
    {

        // tutaj następuje sprawdzenie
        if (parent->left == temp)
            parent->left = NULL;
        else
            parent->right = NULL;

        delete temp;

        return;
    }

    if (temp->left && !temp->right)
    {
        TreeNode* child;

        child = temp->left;
        delete temp;

        if (parent->left == temp)
            parent->left = child;
        else
            parent->right = child;

        return;
    }

    if (!temp->left && temp->right)
    {
        TreeNode* child;

        child = temp->right;
        delete temp;

        if (parent->left == temp)
            parent->left = child;
        else
            parent->right = child;

        return;
    }

    TreeNode* successor = findSuccessor(temp);
    TreeNode* parentSuccessor = findParent(successor);

    if (parentSuccessor == temp)
    {
        successor->left = temp->left;

        if (parent->left == temp)
            parent->left = successor;
        else
            parent->right = successor;
    }
    else
    {
        TreeNode* successorRight = successor->right;

        successor->left = temp->left;
        successor->right = temp->right;

        parentSuccessor->left = successorRight;

        if (parent->left == temp)
            parent->left = successor;
        else
            parent->right = successor;
    }

    delete temp;
}

void Tree::preOrder(TreeNode* node)
{
    if (node)
    {
        count++;
        cout << node->key << endl;
        preOrder(node->left);
        preOrder(node->right);
    }
}

void Tree::inOrder(TreeNode* node)
{
    if (node)
    {
        inOrder(node->left);
        count++;
        cout << node->key << endl;
        inOrder(node->right);
    }
}

void Tree::postOrder(TreeNode* node)
{
    if (node)
    {
        postOrder(node->left);
        postOrder(node->right);
        count++;
        cout << node->key << endl;
    }
}

void Tree::printPreOrder()
{
    cout << "Wyświetlanie preorder: " << endl << endl;

    preOrder(root);
    cout << endl << "Total elements: " << count << endl;
    count = 0;
}

void Tree::printInOrder()
{
    cout << "Wyswietlanie inorder: " << endl << endl;

    inOrder(root);
    cout << endl << "Total elements: " << count << endl;
    count = 0;
}

void Tree::printPostOrder()
{
    cout << "Wyświetlanie postorder: " << endl << endl;

    postOrder(root);
    cout << endl << "Total elements: " << count << endl;
    count = 0;
}

void Tree::clearTree()
{
    if (!root)
    cout << "Drzewo jest puste!" << endl;

    while (root)
        deleteNode(root->key);
}

Tree::~Tree()
{
    clearTree();
}