#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <conio.h>
#include <locale.h>
#include <time.h>

// В заданном бинарном дереве посчитать количество вершин на N-ном уровне, считая корень вершиной 0-ого уровня


//дерево
typedef struct bTREE
{
    int inf;
    struct bTREE* left;
    struct bTREE* right;
}TREE;
//очередь
typedef struct qQUEUE
{
    TREE *tr;
    struct qQUEUE *next;
}QUEUE;
QUEUE *q;
//функция добавления элемента в очередь
void Put(TREE *a)
{
    QUEUE *n, *prev;
    prev = q;
    n = malloc(sizeof(QUEUE));
    n->tr = a;
    n->next = NULL;
    if (q != NULL)
    {
        while (prev->next != NULL)
            prev = prev->next;
        prev->next = n;
    }
    else
        q = n;
}
//функция удаления элемента из очереди
TREE* Get()
{
    QUEUE *prev;
    TREE *a;
    if (q != NULL)
    {
        prev = q;
        a = q->tr;
        if (q->next != NULL)
            q = q->next;
        else
            q = NULL;
        free(prev);
        return a;
    }
    else
        return NULL;
}
//функция проверки на пустоту очереди
int Empty(QUEUE *q)
{
    if (q == NULL) return 1;
    else return 0;
}
//функция добавления элемента в дерево
TREE* Add(TREE *root, int x)
{
    if (root == NULL)
    {
        root = malloc(sizeof(TREE));
        root->inf = x;
        root->left = root->right = NULL;
    }
    else {
        if (x <= root->inf)
            root->left = Add(root->left, x);
        else
            root->right = Add(root->right, x);
    }
    return root;
}
//функция вывода дерева на экран обходя дерево в ширину
int ShowTree(TREE *root, int N)
{
    size_t level = 0, res = 0;
    q = NULL;
    TREE *t;
    TREE *z;
    t = NULL;
    Put(root);
    Put(t);
    while (!Empty(q))
    {
        t = Get();
        if (t == NULL)
        {
            level++;
            Put(NULL);
            if (level == N)
            break;
        }
        else
        {
            if (t->left != NULL)
                Put(t->left);
            if (t->right != NULL)
                Put(t->right);
            printf("%d ", t->inf);
        }
    }
    while (!Empty(q))
    {
        z = Get();
        res = res + 1;
    }
    return res;
    puts("");
}
void main(void)
{
    setlocale(LC_CTYPE, "Russian");
    TREE *mytree = NULL; //указатель на дерево
    FILE *file;
    int k;
    int N;
    printf("Введите N: ");
    scanf("%d", &N);
    fopen_s(&file, "hello.txt", "r");
    if (file == NULL)
    {
        printf("Ошибка при открытии файла");
    }
    else {
        while (fscanf_s(file, "%d", &k) != EOF)
        {
            mytree = Add(mytree, k);
        }
    }
    printf("Дерево:");
    printf("res = %d", ShowTree(mytree, N));
    _getch();
}