#include "stdafx.h"
 
#include <iostream>
#include <string>
using namespace std;
 
struct item {
    int key;
    item* left;
    item* right;
};
item* root = nullptr;
 
item* hledat(item* p, int k){
 
	while (p != nullptr)
	{
		if(p -> key == k){
		return p;
		}
		if (k < p->key) {p = p->left;} else {p = p->right;}
	}
 
return p;
}
 
item* hledat2 (item* p, int k)
{
   while (p != nullptr && p->key != k)
   {
       if (k < p->key) 
         p = p->left; 
       else 
         p = p->right;
   }
 
   return p;
}
 
item* find (item* p, int k)
{
   if (p == nullptr || p->key == k)
         return p;
   else if (k < p->key) 
          return find (p->left, k); 
   else 
          return find (p->right, k); 
}
 
void enter (item* &p, int k)
{
    if (p == nullptr ){
        item* t = new item;
        t->key = k;
        t->left= nullptr;
        t->right= nullptr;
        p=t;
    }
 
   else if ( p->key == k)
         ;
   else if (k < p->key) 
           enter (p->left, k); 
   else 
           enter (p->right, k); 
}
 
item* utrhni (item* &b){
    if (b->right != nullptr)
        return utrhni(b->right);
    else {
       item* a = b;
       b = a->left;
       a->left=nullptr;
       return a;
    }
}
 
void smaz (item* &p, int k){
    if (p == nullptr) {
        return;}
    else if (k < p->key)
        smaz (p->left, k);
    else if (k > p->key)
        smaz (p->right, k);
    else {
        item *u = p;
        if(p->right == nullptr)
            p = p->left;
        else if(p->left == nullptr)
            p = p->right;
        else{
            item *a = utrhni(p->left);
            a->left = u->left;
            a->right = u->right;
            p = a;
        } 
        delete u;	
    }
}
 
void enter2 (item * * p, int k)
{
    if (*p == nullptr ){
        item* t = new item;
        t->key = k;
        t->left= nullptr;
        t->right= nullptr;
        *p=t;
    }
 
   else if ( (*p)->key == k)
         ;
   else if (k < (*p)->key) 
           enter2 (& ((*p)->left), k); 
   else 
           enter2 (& ((*p)->right), k); 
}
 
void enter3 (int k)
{
	item * * p = & root;
	while (*p != nullptr && (*p)->key != k)
	{
       if (k < (*p)->key) 
           p = & ((*p)->left);
       else 
           p = & ((*p)->right); 
	}
 
    if (*p == nullptr ){
        item* t = new item;
        t->key = k;
        t->left= nullptr;
        t->right= nullptr;
        *p=t;
    }
 
   else 
   {
   }
}
 
 
 
void tiskni (item* p){
	if (p != nullptr){
	tiskni (p->left);
	cout << p->key << endl;
	tiskni (p->right);
	}
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    enter (root, 10);
    enter (root, 17);
    enter (root, 7);
    enter (root, 5);
    enter (root, 1);
    enter2 (&root, 12);
    enter3 (20);
    enter3 (2);
 
	tiskni(root);
 
    item * u = hledat (root, 2);
    if (u != nullptr)
        cout << "Nalezeno " << u->key << endl;
    else
        cout << "Nic" << endl;
 
	tiskni(root);
 
    cout << "Mazu" << endl;
	smaz (root, 7);
	smaz (root, 10);
	smaz (root, 1);
 
	tiskni(root);
 
    system ("pause");
    return 0;
}