#include <iostream>
#include <algorithm>
#include <vector>

struct Node {
    int data;
    Node* right;
    Node* left;
};

struct Tree {
    Node* start = nullptr;

    Node* current = nullptr;
    Node* current_minus_one = nullptr;
    Node* receiver = nullptr;
    Node* receiver_dad = nullptr;

    void add(int element) {
        Node* node = new Node(element, nullptr, nullptr);
        if (start == nullptr) {
            start = node;
            return;
        }
        current = start;
        while (current != nullptr) {
            current_minus_one = current;
            if (element > current->data) {
                current = current->right;
            }
            else {
                current = current->left;
            }
        }
        if (element > current_minus_one->data) {
            current_minus_one->right = node;
        }
        else {
            current_minus_one->left = node;
        }
    }

    int depht(Node* cur) { // вносится старт
        if (cur == nullptr) {
            return 0;
        }
        else if ((cur->left == nullptr) && (cur->right == nullptr)) {
            return 1;
        }
        else if ((cur->left != nullptr) && (cur->right == nullptr)) {
            return 1 + this->depht(cur->left);
        }
        else if ((cur->left == nullptr) && (cur->right != nullptr)) {
            return 1 + this->depht(cur->right);
        }
        else if ((cur->left != nullptr) && (cur->right != nullptr)) {
            return 1 + std::max({ this->depht(cur->left), this->depht(cur->right) });
        }
        return -1;
    }

    int elementCount(Node* cur) { // вносится старт
        if (cur == nullptr) {
            return 0;
        }
        else if ((cur->left == nullptr) && (cur->right == nullptr)) {
            return 1;
        }
        else if ((cur->left != nullptr) && (cur->right == nullptr)) {
            return 1 + this->depht(cur->left);
        }
        else if ((cur->left == nullptr) && (cur->right != nullptr)) {
            return 1 + this->depht(cur->right);
        }
        else if ((cur->left != nullptr) && (cur->right != nullptr)) {
            return 1 + this->depht(cur->left) + this->depht(cur->right);
        }
        return -1;
    }

    void print(Node* cur) { // вносится старт
        if (this->start == nullptr) {
            std::cout << "дерево не содержит элементов \n";
            return;
        }
        if (cur->left != nullptr) {
            this->print(cur->left);
        }

        std::cout << cur->data << " ";

        if (cur->right != nullptr) {
            this->print(cur->right);
        }
    }

    void sumOfEven(Node* cur, int* sum_of_even) { // вносится старт
        if (cur == nullptr) {
            return;
        }
        else {
            if (cur->data % 2 == 0) {
                (*sum_of_even) += cur->data;
            }
            this->sumOfEven(cur->left, sum_of_even);
            this->sumOfEven(cur->right, sum_of_even);
        }
    }

    void countOfEven(Node* cur, int* count_of_even) {
        if (cur == nullptr) {
            return;
        }
        if (cur->data % 2 == 0) {
            ++(*count_of_even);
        }
        this->countOfEven(cur->left, count_of_even);
        this->countOfEven(cur->right, count_of_even);

    }

};

int main()
{
    setlocale(LC_ALL, "Russian");

    Tree tree;
    int tree_len;
    int element;
    float mean_of_even;
    int count_of_even = 0;
    int sum_of_even = 0;
    std::cout << "введите количество элементов в дереве: \n";
    std::cin >> tree_len;
    std::cout << "введите эленты дерева: \n";
    for (int i = 0; i < tree_len; ++i) {
        std::cin >> element;
        tree.add(element);
    }
    tree.print(tree.start);
    std::cout << "\n";

    tree.countOfEven(tree.start, &count_of_even);
    tree.sumOfEven(tree.start, &sum_of_even);

    if (count_of_even != 0) {
        mean_of_even = (float)sum_of_even / (float)count_of_even;
        std::cout << "среднее занчение всех четных элементов дерева: " << mean_of_even << "\n";
    }
    else {
        std::cout << "дерево не содержит четных элементов \n";
    }

    return 0;
}