Final_task

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
#include <queue>

using namespace std;

class Exception
{
private:
    string content;
public:
    Exception(string message) : content(message) {}

    string Message()
    {
        return content;
    }
};

template<class TKey, class TValue> class BinaryTree
{
private:
    class Node
    {
    private:
        Node* left;
        Node* right;
        TKey key;
        TValue val;
    public:
        Node(TKey key, TValue val) : key(key), val(val), left(0), right(0) {}

        Node(TKey key, TValue val, Node* left, Node* right) : key(key), val(val), left(left), right(right) {}

        Node* Left()
        {
            return left;
        }

        void Left(Node* left)
        {
            this->left = left;
        }

        Node* Right()
        {
            return right;
        }

        void Right(Node* right)
        {
            this->right = right;
        }

        TKey Key()
        {
            return key;
        }

        TValue Value()
        {
            return val;
        }
    };

    Node* head;
    int cnt;

    bool is_less(const TKey& a, const TKey& b) const
    {
        return a < b;
    }

    bool is_more(const TKey& a, const TKey& b) const
    {
        return b < a;
    }

    bool is_equally(const TKey& a, const TKey& b) const
    {
        return !(a < b) && !(b < a);
    }

    Node* find_parrent(TKey key)
    {
        if (!count) throw Exception("Empty tree");

        Node* tnode = head;

        if (is_equally(key, tnode->Key())) throw Exception("Have not this parent.");

        while (true)
        {
            if (is_less(key, tnode->Key()))
            {
                if (!tnode->Left()) throw Exception("Have not this key.");

                if(is_equally(key, tnode->Left()->Key())) return tnode;

                tnode = tnode->Left();
                continue;
            }

            if (is_more(key, tnode->Key()))
            {
                if (!tnode->Right()) throw Exception("Have not this key.");

                if(is_equally(key, tnode->Right()->Key())) return tnode;

                tnode = tnode->Right();
                continue;
            }
        }
    }

    Node* find_node(TKey key, Node* parent)
    {
        if(is_equally(key, parent->Right()->Key())) return parent->Right();

        if(is_equally(key, parent->Left()->Key())) return parent->Left();

        throw Exception("Have not this key.");
    }

    void retreeing(Node* start, Node* del)
    {
        queue<Node*> tq, all_nodes;

        tq.push(start);
        Node* tnode;

        while(tq.size())
        {
            tnode = tq.front();
            tq.pop();

            if(tnode->Key() != del->Key()) all_nodes.push(tnode);

            if(tnode->Left())
            {
                tq.push(tnode->Left());
                all_nodes.push(tnode->Left());
            }

            if(tnode->Right())
            {
                tq.push(tnode->Right());
                all_nodes.push(tnode->Right());
            }
        }

        // TODO smth
    }
public:
    BinaryTree() : head(), cnt(0) {}

    bool Insert(TKey key, TValue val)
    {
        if (!head)
        {
            head = new Node(key, val);
            cnt = 1;
            return true;
        }

        Node* tnode = head;

        while (true)
        {
            if (is_equally(key, tnode->Key())) return false;

            if (is_less(key, tnode->Key()))
            {
                if (!tnode->Left())
                {
                    tnode->Left(new Node(key, val));
                    cnt++;
                    return true;
                }

                tnode = tnode->Left();
                continue;
            }

            if (is_more(key, tnode->Key()))
            {
                if (!tnode->Right())
                {
                    tnode->Right(new Node(key, val));
                    count++;
                    return true;
                }

                tnode = tnode->Right();
                continue;
            }
        }
    }

    TValue Get(TKey key)
    {
        if (!count) throw Exception("Empty tree");

        Node* tnode = head;

        while (true)
        {
            if (is_equally(key, tnode->Key())) return tnode->Value();

            if (is_less(key, tnode->Key()))
            {
                if (!tnode->Left()) throw Exception("Kave not this key.");

                tnode = tnode->Left();
                continue;
            }

            if (is_more(key, tnode->Key()))
            {
                if (!tnode->Right()) throw Exception("Kave not this key.");

                tnode = tnode->Right();
                continue;
            }
        }
    }

    bool Remove(TKey key)
    {
        if(head->Key() == key)
        {
            if(!head->Left() && !head->Right())
            {
                delete head;
                head = 0;
                return true;
            }

            if()

            return true;
        }


    }
};

int main()
{
    //freopen("output.txt", "w", stdout);
    cout << "start. \n";

    BinaryTree<string, int> t;

    t.insert("1", 1);
    t.insert("2", 2);
    t.insert("3", 3);
    t.insert("4", 4);
    t.insert("5", 5);

    cout << t.get("1") << "\n";
    cout << t.get("2") << "\n";
    cout << t.get("3") << "\n";
    cout << t.get("4") << "\n";
    cout << t.get("5") << "\n";

    cout << "\nend.\n";
    return 0;
}