#include <string>
#include <vector>
#include <iostream>

// Двоичное дерево поиска
// Ключ левого поддерева меньше, чем ключ узла
// Ключ правого поддерева больше или равен ключу узла
class BinaryTree {
private:
    struct Node {
        std::string name; // Имя студента
        std::vector<int> mark; // Три оценки
        float average_mark; // Средняя оценка
        Node* left; // Указатель на левое поддерево
        Node* right; // Указатель на левое поддерево

        Node(std::string &name, std::vector<int> &mark)
                : left(nullptr), right(nullptr) {
            this->name = name;
            this->mark = mark;
            average_mark = (float)(mark[0] + mark[1] + mark[2]) / 3;
        }
    };

    Node* root = nullptr; // Корень дерева
public:
    // Функция нужна для получения вершины, в которую будем вставлять
    inline Node* getParentNode(Node* &insertNode) {
        auto parentNode = root;
        while (true) {
            if (parentNode->average_mark > insertNode->average_mark) {
                if (parentNode->left == nullptr) return parentNode;
                else parentNode = parentNode->left;
            } else {
                if (parentNode->right == nullptr) return parentNode;
                else parentNode = parentNode->right;
            }
        }
    }

    // Функция для добавления новой записи в дерево
    void addToTree(std::string &name, std::vector<int> &mark) {
        auto newNode = new Node(name, mark);

        // Ищем вершину, в которую будем вставлять узел
        if (root == nullptr) {
            root = newNode;
        }else {
            Node* parentNode = getParentNode(newNode);
            if (parentNode->average_mark > newNode->average_mark) parentNode->left = newNode;
            else parentNode->right = newNode;
        }
    }

    // Позволяет обойти все узлы дерева в порядке убывания ключей
    // следуя порядку (правое поддерево, вершина, левое поддерево)
    void suffix_traverse(Node* node) {
        if (node != nullptr) {
            suffix_traverse(node->right);
            // TODO: За такое обычно руки отрывают, но, ладно
            std::cout << "Имя: " << node->name << "   Средняя оценка: "
                      << node->average_mark << "   Оценки: " << node->mark[0]
                      << " " << node->mark[1] << " " << node->mark[1] << std::endl;
            suffix_traverse(node->left);
        }
    }
    void suffix_traverse() {
        suffix_traverse(root);
    }

    ~BinaryTree() {
        postfix_delete(root);
    }
    void postfix_delete(Node* node) {
        // Сначала удаляем левое поддерево
        if (node->left != nullptr) postfix_delete(node->left);
        // Потом удаляем правое поддерево
        if (node->right != nullptr) postfix_delete(node->right);
        // Удаляем узел
        delete node;
    }
};