#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//struktura wg konspektu
struct Node
{
    struct Node * leftChild;
    struct Node * rightChild;
    int value;
};

//zmienna globalna na wskaznik do root'a drzewa
struct Node * g_Root;

//deklaracje funkcji wg konspektu, na dole implementacje
struct Node * Create(int value);
void Add(struct Node * root, int value);
//te trzy printy.. to niescislosc w konspekcie, bo tam jest 1 print ale potem nagle gosciu chce trzy metody - zrobilem trzy
void PrintInOrder(struct Node * root);
void PrintPreOrder(struct Node * root);
void PrintOrder(struct Node * root);
struct Node * Find(struct Node * root, int value);
struct Node * Remove(struct Node * root, int value);
void Free(struct Node * root);

int main()
{
    //scenariusz wg konspektu
    g_Root = Create(100);

    Add(g_Root, 50);
    Add(g_Root, 120);
    Add(g_Root, 40);
    Add(g_Root, 45);
    Add(g_Root, 150);
    Add(g_Root, 35);
    Add(g_Root, 48);

    PrintInOrder(g_Root);

    Remove(g_Root, 120);
    Remove(g_Root, 40);
    Remove(g_Root, 50);

    PrintInOrder(g_Root);

    printf("\n\n48 search result: %s", (NULL != Find(g_Root, 48))
        ? "Found!" : "Not found..");

    printf("\n70 search result: %s\n", (NULL != Find(g_Root, 70))
        ? "Found!" : "Not found..");

    srand(time(NULL));
    for (int i = 0; i < 10; i++)
    {
        Add(g_Root, rand() % 100);
    }

    PrintInOrder(g_Root);
    PrintOrder(g_Root);
    PrintPreOrder(g_Root);

    Free(g_Root);

    printf("\n");
    system("PAUSE");
    return 0;
}

Node * Create(int value)
{
    //tworzymy wskaznik i alokujemy miejsce w pamieci na nowy node
    struct Node * result = (struct Node *)malloc(sizeof(struct Node));

    //przypisujemy wartosci dla nowego node
    result->value = value;
    result->leftChild = NULL;
    result->rightChild = NULL;

    //zwracamy nowy node
    return result;
}

void Add(Node * root, int value)
{
    //sprawdzamy czy root z argumentu nie jest nullem
    if (NULL != root)
    {
        //jesli wartosc z argumentu jest mniejsza od wartosci w aktualnym node..
        if (root->value > value)
        {
            //i lewy child jest nullem..
            if (NULL == root->leftChild)
            {
                //to wlasnie znalezlismy dla niego miejsce w drzewie i robimy mu nowy node korzystajac z funkcji create
                root->leftChild = Create(value);
            }
            else
            {
                //albo jesli root w ktorym teraz jestesmy ma lewego childa, no to rekurencyjnie nurkujemy dalej..
                Add(root->leftChild, value);
            }
        }
        //albo jesli value z argumentu funkcji jest wiekszy od value node w ktorym aktualnie jestesmy, to..
        else if(root->value < value)
        {
            //jesli lewy child jest nullem, wlasnie znalezlismy dla niego miejsce w drzewie..
            if (NULL == root->rightChild)
            {
                //no i tworzymy nowego node
                root->rightChild = Create(value);
            }
            //jesli jednak prawy child nie jest nullem..
            else
            {
                //no to rekurencyjnie nurkujemy w prawego childa..
                Add(root->rightChild, value);
            }
        }
        //jesli jednak znajdziemy node ktorego value jest rowne value z argumentu funkcji..
        else if (root->value == value)
        {
            //no to obslugujemy to, poniewaz nie moga byc dwie takie same wartosci w jednym drzewie - wyswietlamy stosowny komunikat
            printf("Value %d already exist in the tree!\n", value);
        }
    }
}

void PrintInOrder(Node * root)
{
    if (g_Root == root)
    {
        //podpis przy pierwszym wywolaniu funkcji, gdy root jest pierwszym node drzewa :) zeby ladniej bylo
        printf("\nInOrder print:\t");
    }

    //jesli aktualny node nie jest nullem, to..
    if (NULL != root)
    {
        //rekurencyjnie nurkujemy w lewego childa
        PrintInOrder(root->leftChild);
        //wyswietlamy value aktualnego node w ktorym jestesmy
        printf("%d, ", root->value);
        //i rekurencyjnie nurkujemy w prawego childa
        PrintInOrder(root->rightChild);
    }

}

void PrintPreOrder(Node * root)
{
    if (g_Root == root)
    {
        //to samo co w in order
        printf("\nPreOrder print:\t");
    }

    //tez..
    if (NULL != root)
    {
        //roznica taka, ze kolejnosc sie zmienia - szczegoly patrz w PrintInOrder
        printf("%d, ", root->value);
        PrintPreOrder(root->leftChild);
        PrintPreOrder(root->rightChild);
    }
}

void PrintOrder(Node * root)
{
    //tez tylko roznica w kolejnosci, patrz w PrintInOrder
    if (g_Root == root)
    {
        printf("\nOrder print:\t");
    }

    if (NULL != root)
    {
        PrintOrder(root->leftChild);
        PrintOrder(root->rightChild);
        printf("%d, ", root->value);
    }
}

Node * Find(Node * root, int value)
{
    //robimy sobie zmienna ze wskaznikiem na rezultat metody
    struct Node * result = NULL;

    //sprawdzamy czy root z argumenty nie jest nullem
    if (NULL != root)
    {
        //jesli value w aktualnym node jest mniejsza od value z argumentu funkcji..
        if (root->value > value)
        {
            //to nurkujemy rekurencyjnie w lewego childa, jednoczesnie przypisujac wartosc zwracana do zmiennej result (w niej bedzie znaleziony node)
            result = Find(root->leftChild, value);
        }
        //jesli value w aktualnym node jest wieksza od value z argumentu funkcji no to..
        else if (root->value < value)
        {
            //rekurencyjnie nurkujemy w praweo childa jednoczesnie przypisujac wynik find do zmiennej result - tak wyluskamy wynik wyszukiwania
            result = Find(root->rightChild, value);
        }
        //jesli obie value sa rowne..
        else if (root->value == value)
        {
            //no to brawo, znalezlismy szukana wartosc i juz konczymy rekurencje, tylko przypisujemy do zmiennej result root w ktorym aktualnie jestesmy bo go szukalismy
            result = root;
        }
    }

    //zwracamy zmienna result z wynikiem wyszukiwania
    return result;
}

struct Node* Remove(struct Node* root, int valueToRemove)
{
    struct Node * result = root;
    if (NULL != result)
    {
        struct Node * tempNode = NULL;

        if (root->value > valueToRemove)
        {
            root->leftChild = Remove(root->leftChild, valueToRemove);
        }
        else if (root->value < valueToRemove)
        {
            root->rightChild = Remove(root->rightChild, valueToRemove);
        }
        else if(valueToRemove == root->value)
        {
            if (root->leftChild == NULL)
            {
                tempNode = root->rightChild;
                free(root);
                result = tempNode;
            }
            else if (root->rightChild == NULL)
            {
                tempNode = root->leftChild;
                free(root);
                result = tempNode;
            }
            else
            {
                struct Node* minValueNode = root->rightChild;
                while (NULL != minValueNode->leftChild)
                {
                    minValueNode  = minValueNode->leftChild;
                }
                root->value = minValueNode->value;
                root->rightChild = Remove(root->rightChild, minValueNode->value);
                result = root;
            }
        }
    }

    return result;
}

void Free(Node * root)
{
    if (NULL != root && root != g_Root)
    {
        Free(root->leftChild);
        Free(root->rightChild);
        free(root);
    }
    else if (root == g_Root)
    {
        Free(root->leftChild);
        Free(root->rightChild);
        free(root);
        g_Root = NULL;
    }
}