Бинарное дерево не создается - C (СИ)
Формулировка задачи:
ptree Form()
{
ptree root=NULL;
char info;
scanf("%c",&info);
if(info!='*')
{
root=Mem;
root->info=info;
root->left=Form();
root->right=Form();
}
else
root=NULL;
return root;
}Решение задачи: «Бинарное дерево не создается»
#include <string.h>
#include <locale.h>
#define Mem (ptree)malloc(sizeof(ttree))
typedef struct tree
{
int info;
struct tree *left;
struct tree *right;
}ttree, *ptree ;
ptree Form();
int schet(ptree root, char inf);
ptree Form()
{
ptree root=NULL;
int info;
scanf("%i",&info);
if(info!=0)
{
root=Mem;
root->info=info;
root->left=Form();
root->right=Form();
}
else
root=NULL;
return root;
}
int schet(ptree root, char inf)
{
int i=0,rez_left,rez_right;
if (root!=NULL)
{
if(root->info==inf)
i=1;
rez_left=i+schet(root->left,inf);
rez_right=i+schet(root->right,inf);
if(rez_right>rez_left)
return rez_right;
else
return rez_left;
}
else
return i;
}
void main()
{
setlocale(LC_ALL,"Rus");
ptree root;
int info;
int rez;
printf("введите элементы дерева(для завершения образования ветки введите 0)\n");
root=Form();
printf("введите число \n");
scanf("%i",&info);
rez=schet( root, info);
if (rez==0)
printf("такого числа нет\n");
else
printf("до числа %i максимальная длина %i \n",info,rez);
system("pause");
}
Объяснение кода листинга программы
В данном коде реализуется бинарное дерево, но оно не создается полностью, а только дочерние узлы. Код начинается с определения структуры дерева и двух функций: Form() и schet().
Функция Form() отвечает за создание нового узла дерева. Если пользователь вводит ноль, то функция возвращает NULL, иначе она выделяет память под новый узел, заполняет его информацией и вызывает себя рекурсивно для создания дочерних узлов.
Функция schet() отвечает за подсчет количества узлов в левой и правой поддеревьях и возвращает максимальное значение из этих двух подсчетов. Если введенное число совпадает с информацией в текущем узле, то функция увеличивает счетчик.
В функции main() устанавливается локальная настройка на русский язык, затем создается корневой узел дерева, вызывается функция Form() для его заполнения, после чего пользователю предлагается ввести число для проверки наличия в дереве. После ввода числа вызывается функция schet(), которая возвращает количество узлов в поддереве с данным числом. Если это число отсутствует в дереве, выводится сообщение такого числа нет, иначе выводится сообщение вида до числа X максимальная длина Y, где X - искомое число, Y - максимальная длина поддерева с этим числом.