Задача:
В заданном непустом бинарном дереве подсчитать число вершин на n-м уровне, считая корень вершиной 0-го уровня.
Помогите пожалуйста, как подсчитать число вершин на n-м уровне, считая корень вершиной 0-го уровня?
Вот все, что я смог написать
Код:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <conio.h>
#include <locale.h>
//дерево
typedef struct tagTREE
{
int inf;
struct tagTREE* left;
struct tagTREE* right;
}TREE;
//очередь
typedef struct tagQUEUE
{
TREE *tr;
struct tagQUEUE *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;
}
//функция удаления элемента из дерева
TREE* Del(TREE *root, int x)
{
TREE *t;
if (root == NULL) return 0;
if (x == root->inf)
{
if (root->left == NULL)
{
t = root->right;
free(root);
return t;
}
t = root->left;
while (t->right) t = t->right;
t->right = root->right;
return root->left;
}
if (x <= root->inf)
root->left = Del(root->left, x);
else
root->right = Del(root->right, x);
return root;
}
//функция вывода дерева на экран
//обходя дерево в ширину
void ShowTree(TREE *root)
{
q = NULL;
TREE *t;
Put(root);
while (!Empty(q))
{
t = Get();
if (t->left != NULL)
Put(t->left);
if (t->right != NULL)
Put(t->right);
printf("%d ", t->inf);
}
puts("");
}
void main(void)
{
setlocale(LC_CTYPE,"Russian");
TREE *mytree = NULL; //указатель на дерево
FILE *file;
int k;
fopen_s(&file, "hello.txt", "r");
if (file == NULL)
printf("Ошибка при открытии файла");
else {
printf("Дерево:");
while (fscanf_s(file, "%d", &k) != EOF)
{
mytree = Add(mytree, k);
}
}
printf("Дерево:");
ShowTree(mytree);
_getch();
}