Task 4

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct __BTNode BTNode;
typedef struct __BSTree BSTree;

int count = 0;

//имплементация сущности нашего узла (значение, ссылки на левый и правый дочерние узлы)
struct __BTNode
{
    int value;
    BTNode *left;
    BTNode *right;
};

//конструктор, создающий сущность узла (выделяет под него память), ссылки на левый и правый дочерние узлы и заполняющий узел его
//значением
BTNode *BTree_new(int value)
{
    BTNode *self = malloc(sizeof(BTNode));
    if (self == NULL)
    {
        abort();
    }
    self->value = value;
    self->left = NULL;
    self->right = NULL;

    return self;
}

//вспомогательная сущность
struct __BSTree
{
    BTNode *root;
};

//конструктор дерева (выделяет под него память)
BSTree *BSTree_new(void)
{
    BSTree *self = malloc(sizeof(BSTree));
    if(self == NULL)
    {
        fprintf(stderr, "Out of Memory!\n");
        abort();
    }
    self->root = NULL;
    return self;
}

//вставка в дерево происходит рекурсивно (функция будет вызывать сама себя до тех пор,
//пока не найдёт место, куда можно вставить новый узел с его значением)
//принцип - если значение дочернего узла больше, чем в родительском, то такой узел присоединяется справа от родительского узла
//если меньше - слева
//визулальное представление дерева из задания -- по ссылке https://ibb.co/4JMP315
static void insert(BTNode *node, int key)
{
    if (key < node->value)
    {
        if (node->left == NULL)
        {
            node->left = BTree_new(key);
        }
        else
        {
            insert(node->left, key);
        }
    }
    else if (key > node->value)
    {
        if (node->right == NULL)
        {
            node->right = BTree_new(key);
        }
        else
        {
            insert(node->right, key);
        }
    }
    else
    {
        fprintf(stderr, "Not unique!\n");
        abort();
    }
}

//вспомогательная функция (обёртка) для вставки
void BSTree_insert(BSTree *self, int key)
{
    if (self->root == NULL)
    {
        self->root = BTree_new(key);
    }
    else
    {
        insert(self->root, key);
    }
}

//рекурсивный обход узлов по уровням (начинается с 0), проверка значений на некратность трём
static void print_level(BTNode *node, int level)
{
    for (int i = 0; i < level; i++)
    {
        putchar('.');
    }
    if (node == NULL)
    {
        printf("(null)\n");
    }
    else
    {
        printf("%i\n", node->value);
        //проверка выполенения условия задания для инкрементация счётчика
        if (level % 2 == 0 && node->value % 3 != 0)
            count++;
        //если на текущем уровне не осталось неохваченных узлов - переход на следующий уровень, функция снова вызывает сама себя
        if (node->left || node->right)
        {
            level++;
            print_level(node->left, level);
            print_level(node->right, level);
        }
    }
}

//вспомогательная функция для печати
void BSTree_printFormat(BSTree * self)
{
    print_level(self->root, 0);
}

int main()
{
    BSTree *tree = BSTree_new();
    BSTree_insert(tree, 560);
    BSTree_insert(tree, 952);
    BSTree_insert(tree, 875);
    BSTree_insert(tree, 360);
    BSTree_insert(tree, 86);
    BSTree_insert(tree, 850);
    BSTree_insert(tree, 522);
    BSTree_insert(tree, 733);
    BSTree_insert(tree, 455);
    BSTree_insert(tree, 257);
    BSTree_insert(tree, 468);
    BSTree_insert(tree, 97);
    BSTree_insert(tree, 775);
    BSTree_insert(tree, 141);
    BSTree_insert(tree, 940);
    BSTree_insert(tree, 177);
    BSTree_insert(tree, 743);
    BSTree_insert(tree, 281);
    BSTree_insert(tree, 616);
    BSTree_insert(tree, 122);

    BSTree_printFormat(tree);

    printf("\nAmount of nodes on odd levels with keys, which are not a multiple on three: %d", count);

    return 0;
}