//1)-Да се състави двоично дърво, на което потребител да въвежда елементи,  да се отпечатват тези елементи, да има опция за изтриване на  избран елемент от потребителя и функция, която търси елементи. 

-Обхождането на елементите съм го направил във вътрешен ред или (симитрично обхождане). Не е прав ред или обратен ред.

//2)-Създайте фухкция за обединяване на две дадени двоични дървета за търсене в ново подредено двоично дърво .

#include <iostream>
using namespace std;

struct elem
{
    elem* pleft, * pright;
    int key;
}*root = NULL;
int menu();
void add(int n, elem*& t);
void inorder(elem* t);
int del(int k);
elem*& search(int k);
int height(elem* t);
void printNode(int n, int h);
void show(elem* t, int h);
 
void main()
{
    int n = 0, num, h;
    do
    {
        n = menu();
        switch (n)
        {
        case 1:
        {
            cout << "Num= ";
            cin >> num;
            add(num, root);
            break;
        }
        case 2:
        {
            cout << "All elements: ";
            inorder(root);
            break;
        }
        case 3:
        {
            cout << "Search: ";
            cin >> num;
            elem*& p = search(num);
            if (p == NULL)
            {
                cout << "The item is not in the tree: " << endl;
            }
            else
            {
                cout << "The item is in the tree: " << endl;
            }
            break;
        }
        case 4:
        {
            cout << "Enter the item to be delete: ";
            cin >> num;
            if (del(num) == 0)
                cout << "The item is not the tree: " << endl;
            break;
        }
        case 5:
        {
            h = height(root);
            show(root, h);
            cout << endl;

        }
        }
    } while (n != 6);
}
int menu()
{
    int izbor = 0;
    do
    {
        cout << endl << "MENU " << endl;
        cout << "1)-Add element: " << endl;
        cout << "2)-Print: " << endl;
        cout << "3)-Search: " << endl;
        cout << "4)-Delete: " << endl;
        cout << "5)-Show: " << endl;
        cout << "6)-End: " << endl;
        cout << ">> ";
        cin >> izbor;
    } while (izbor < 1 || izbor > 6);
    return izbor;
}
void add(int n, elem*& t)
{
    if (t == NULL)
    {
        t = new elem;
        t->key = n;
        t->pleft = t->pright = NULL;
    }
    else
    {
        if (t->key < n)
            add(n, t->pright);
        else
            add(n, t->pleft);
    }
}
void inorder(elem* t)
{
    if (t)
    {
        inorder(t->pleft);
        cout << t->key << " ";
        inorder(t -> pright);
    }
}
elem*& search(int k)
{
    elem** p = &root;
    for (;;)
    {
        if (*p == NULL)
            return *p;
        if (k < (*p)->key)
            p = &(*p)->pleft;
        else
            if (k > (*p)->key)
                p = &(*p)->pright;
            else
                return *p;
    }
}
int del(int k)
{
    elem*& p = search(k), * p0 = p, ** qq, * q;
    if (p == NULL)
        return 0;
    if (p->pright == NULL)
    {
        p = p->pleft;
        delete p0;
    }
    else
        if (p->pleft == NULL)
        {
            p = p->pright;
            delete p0;
        }
        else
        {
            qq = &p->pleft;
            while ((*qq)->pright)
                qq = &(*qq)->pright;
            p->key = (*qq)->key;
            q = *qq;
            *qq = q->pleft;
            delete q;
        }
    return 1;
}
int height(elem* t)
{
    int u, v;
    if (!t)
        return -1;
    u = height(t->pleft);
    v = height(t->pright);
    if (u > v)
        return u + 1;
    else
        return v + 1;
}
void printNode(int n, int h)
{
    for (int i = 0; i < h; i++)
    {
        cout << "\t";
    }
    cout << n << endl;
}
void show(elem* t, int h)
{
    if (t)
    {
        show(t->pright, h + 1);
        printNode(t->key, h);
        show(t->pleft, h + 1);
    }
}