#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
 
struct Item
{
    string key;
    Item* left;
    Item* right;
    Item ();
};
 
Item::Item () : key (""), left (nullptr), right (nullptr) {}
 
Item* root = nullptr;
 
Item * search (Item * p, string name)
{
    // while (p != nullptr && p->key != name)
    while (! (p == nullptr || p->key == name) )
    {
        if (name < p->key)
            p = p->left;
        else
            p = p->right;
    }
    return p;
}
 
Item * find (Item * p, string name)
{
    if (p == nullptr)
        return nullptr;
    else if (p->key == name)
        return p;
    else if (name < p->key)
        return find (p->left, name);
    else /* if (p->key < name) */
        return find (p->right, name);
}
 
void enter (Item * & p, string name)
{
    if (p == nullptr)
    { 
        Item * n = new Item;
        n->key = name;
        n->left = nullptr;
        n->right = nullptr;
        p = n;
    }
    else if (p->key == name)
    {  }
    else if (name < p->key)
       enter (p->left, name);
    else /* if (p->key < name) */
       enter (p->right, name);
}
 
Item * release (Item * & c)
{
    if (c->right != nullptr)
        return release (c->right);
    else
    {
        Item * d = c;
        c = c->left;
        d->left = nullptr;
        return d;
    }
}
 
void remove (Item * & p, string name)
{
    if (p == nullptr)
    {
    }
    else if (name < p->key)
        remove (p->left, name);
    else if (p->key < name)
        remove (p->right, name);
    else
    {
        Item * a = p;
        if (p->left == nullptr)
            p = p->right;
        else if (p->right == nullptr)
            p = p->left;
        else
        {
            Item * b = release(p->left);
            b->left = p->left;
            b->right = a->right;
            p = b;
        }
        a->left = nullptr;
        a->right = nullptr;
        delete a;
    }
}
 
void print (Item* p)
{
    if (p != nullptr)
    {
        print (p->left);
        cout << p->key << endl;
        print (p->right);
 
    }
}
 
void display (Item* p, int level=1)
{
    if (p != nullptr)
    {
        display (p->left, level + 1);
        for (int i = 1; i < level; i++)
            cout << "    ";
        cout << p->key << endl;
        display (p->right, level + 1);
 
    }
}
 
void enter2 (Item * * p, string name)
{
    while (true)
    {
        if (*p == nullptr)
        {
            Item * n = new Item;
            n->key = name;
            n->left = nullptr;
            n->right = nullptr;
            *p = n;
            break;
        }
        else if ((*p)->key == name)
        {
            break;
        }
        else if (name < (*p)->key)
            p = & (*p)->left;
        else /* if (p->key < name) */
            p = & ( (*p)->right );
    }
}
 
int main()
{
    enter (root, "10");
    enter (root, "05");
    enter (root, "20");
    enter (root, "03");
    enter2 (&root, "25");
    enter2 (&root, "15");
    enter (root, "06");
    enter (root, "08");
    enter (root, "07");
    print (root);
    cout << "---" << endl;
    display (root);
    remove (root, "10");
    /*
    remove (root, "20");
    remove (root, "15");
    remove (root, "25");
    remove (root, "10");
    remove (root, "05");
    remove (root, "03");
    */
    cout << "---" << endl;
    display (root);
    cout << "---" << endl;
    print (root);
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}