#include <iostream>

template <class T>
class BinaryTree // Шаблонный класс дерева
{
    struct node { // Узел дерева
        T data;
        struct node* rightBr;
        struct node* leftBr;
    };

public:
    BinaryTree(); // Конструктор дерева
    ~BinaryTree(); // Деструктор дерева
    void add(T dat); // Добавить элемент
    void printTree(); // Вывести дерево на экран
    int size(); // Возвращение размера дерева
    bool lookup(T dat); // Поиск похожих значений дерева
private:
    struct node* root;
    int treeSize;
    void add(struct node** node, T dat);
    bool lookup(struct node* node, T dat);
    void printTree(struct node* node);
    void deleteTree(struct node* node);
};

template <class T>
BinaryTree<T>::BinaryTree() {
    this->root = nullptr;
    this->treeSize = 0;
}

template <class T>
BinaryTree<T>::~BinaryTree() {
    deleteTree(this->root);
}

template <class T>
int BinaryTree<T>::size() {
    return this->treeSize;
}

template <class T>
void BinaryTree<T>::add(T dat) {
    add(&(this->root), dat);
}

template <class T>
void BinaryTree<T>::add(struct node** node, T dat) {

    if (*node == nullptr) {
        struct node* temp = new struct node;
        temp->data = dat;
        temp->leftBr = nullptr;
        temp->rightBr = nullptr;
        *node = temp;

        this->treeSize++;
    }
    else {
        if (dat > (*node)->data) {
            add(&(*node)->rightBr, dat);
        }
        else {
            add(&(*node)->leftBr, dat);
        }
    }
}

template <class T>
void BinaryTree<T>::printTree() {
    printTree(this->root);
    std::cout << std::endl;
}

template <class T>
void BinaryTree<T>::printTree(struct node* node) {
    if (node != nullptr) {
        printTree(node->leftBr);
        std::cout << node->data << ", ";
        printTree(node->rightBr);
    }
}

template <class T>
void BinaryTree<T>::deleteTree(struct node* node) {
    if (node != nullptr) {
        deleteTree(node->leftBr);
        deleteTree(node->rightBr);
        delete node;
    }
}

template <class T>
bool BinaryTree<T>::lookup(T dat) {
    return lookup(this->root, dat);
}

template <class T>
bool BinaryTree<T>::lookup(struct node* node, T dat) {
    if (node == nullptr) {
        return false;
    }
    else {
        if (dat == node->data) {
            return true;
        }

        if (dat > node->data) {
            return lookup(node->rightBr, dat);
        }
        else {
            return lookup(node->leftBr, dat);
        }
    }

}

int main() {
    setlocale(LC_ALL, "ru");
    BinaryTree<int> tree;

    tree.add(5);
    tree.add(4);
    tree.add(7);
    tree.add(10);
    tree.add(1);
    tree.add(2);

    tree.printTree();

    std::cout << "Размер дерева: " << tree.size() << std::endl;

    std::cout << "Содержит 7?: " << ((tree.lookup(7)) ? "true" : "false") << std::endl;

    std::cout << "Удаляем 7: " << std::endl;
    tree.printTree();

    return 0;
}