// tree.cpp : Defines the entry point for the console application.
 
#include "stdafx.h"
#include <iostream>
#include <string>
 
using namespace std;
 
struct item {
    int key;
    item* left;
    item* right;
};
 
item* root=0;
 
item* search(int k){
    item* p=root;
    while (p!=NULL)
    {
       if (k < p->key)
           p = p->left;
       else if(k > p->key)
           p = p->right;
       else return p;
    }
    return p;
}
 
item* search2(int k){
    item* p=root;
    while (p!=NULL && p->key != k)
    {
       if (k < p->key)
           p = p->left;
       else 
           p = p->right;
    }
    return p;
}
 
 
void put (int k){
    item* p=root;
    item* t=NULL;
    while (p!=NULL)
    {
       if (k < p->key)
          { t = p; p = p->left; }
       else if(k > p->key)
          { t = p; p = p->right; }
       else return; // klic jiz byl ve stromu
    }
    if (p == nullptr)
    {
        // klic nebyl ve stromu
        item * u = new item;
        u->key = k;
        u->left = nullptr;
        u->right = nullptr;
        if (t == nullptr) root = u;
        else if (k < t->key) t->left = u;
        else t->right = u;
    }
}
 
item* find (item * p, int k){
    if (p==NULL)
       return NULL;
    else if (k < p->key)
       return find (p->left, k);
    else if (k > p->key)
        return find (p->right, k);
    else return p;
}
 
void enter (item * & p, int k){
    if (p==NULL)
    {
       item * u = new item;
       u->key = k;
       u->left = NULL;
       u->right = NULL;
       p = u;
    }
    else if (k < p->key)
       enter (p->left, k);
    else if (k > p->key)
       enter (p->right, k);
}
 
void insert (int k) {
    enter (root, k);
}
 
item *del (item * & q) {
    if(q->right != NULL)
        return del(q->right);
    else 
    {
        item *r = q;
        q=q->left;
        return r;
    }
}
 
void remove (item * & p, int k){
    if (p==NULL)
    {
    }
    else if (k < p->key)
       remove (p->left, k);
    else if (k > p->key)
       remove (p->right, k);
    else
    {
        item* t = p;
        if (p->left ==NULL)
            p=p->right; 
    else if (p->right==NULL)
        p=p->left;
    else {
        item * u= del (p->left);
        u -> left = p -> left;
        u -> right = p -> right;
        p = u;
        }
    delete t;
    }
}
 
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, int k){
    if (*p==NULL)
    {
       item * u = new item;
       u->key = k;
       u->left = NULL;
       u->right = NULL;
       *p = u;
    }
    else if (k < (*p)->key)
       enter2 (& (*p)->left, k);
    else if (k > (*p)->key)
       enter2 (& (*p)->right, k);
}
 
void enter3 (int k){
    item * * p = & root;
    while (true)
    {
        if (*p==NULL)
        {
           item * u = new item;
           u->key = k;
           u->left = NULL;
           u->right = NULL;
           *p = u;
           return;
        }
        else if (k < (*p)->key)
           p = & ((*p)->left );
        else if (k > (*p)->key)
           p = &	((*p) ->right);
        else return; // duplicita klicu
    }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Hello" << endl;
    insert (7);
    insert (5);
    insert (10);
    insert (1);
    insert (6);
    insert (42);
    insert (17);
    insert (27);
    insert (37);
 
    print (root);
    display(root);
 
    remove (root, 7);
    remove (root, 5);
    remove (root, 1);
    remove (root, 6);
 
    print (root);
    display(root);
 
 
    cout << "End" << endl;
    system ("pause");
 
    return 0;
}