#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
 
struct Item {
    string key;
    Item*left;
    Item*right;
 
    Item ();
};
 
Item*root = nullptr;
 
Item::Item () :key (""), left (nullptr), right (nullptr){}
 
Item*search (Item* p, string name) 
{
    while (p!= nullptr && p->key != name) 
    { 
      if (name < p->key)
        p = p->left;
      else /* if (p->key < name) */
        p = p->right;
    }
    /* p == nullptr || p->key == name */
    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 (name > p->key) */
        return find (p->right, name);
}
 
void print (Item*p)
{
    if (p != nullptr) {
        print (p->left);
        cout << p->key << endl;
        print (p->right);
    }
}
 
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 (name > p->key) */
        enter (p->right, name);
}
 
void enter2 (Item** p, string name)
{
    while (*p != nullptr && (*p)->key != name)
    {
       if (name < (*p)->key)
         p = & (*p)->left;
       else
         p = & (*p)->right;
    }
    if (*p == nullptr)
    {
        Item * n = new Item ();
        n->key = name;
        n->left = nullptr;
        n->right = nullptr;
        *p = n;
    }
}
 
Item* uvolnit (Item *& t)
{
    if (t->right == nullptr)
    {
        Item * result = t;
        t = t->left;
        result->left = nullptr;
        return result;
    }
    else
    {
        return uvolnit (t->right);
    }
}
 
void remove (Item*& p, string name)
{
    if (p == nullptr)
    {
    }
    else if (name < p->key)
        remove (p->left, name);
    else if (name > p->key) 
        remove (p->right, name);
    else if (p->key == name)
    {
        Item* nalezeny = p;
        if (p->left == nullptr)
            p = p->right;
        else if (p->right==nullptr)
            p = p->left;
        else
        {
            Item *a = uvolnit (p->left);
            a->left = p->left;
            a->right = p->right;
            p = a;
        }
        nalezeny->left = nullptr;
        nalezeny->right = nullptr;
        delete nalezeny;
    }
}
 
int main()
{
 
    enter (root, "10");
    enter (root, "07");
    enter (root, "20");
    enter (root, "05");
    enter (root, "08");
    enter (root, "06");
    enter (root, "06.5");
    enter (root, "06.1");
    print (root);
 
    cout << "-------" << endl;
    display (root, 1);
 
    remove (root, "07");
 
    cout << "-------" << endl;
    display (root, 1);
    cout << "-------" << endl;
    print (root);
 
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}