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

typedef struct element{  
  struct element* left;  
  char name[30];  
  struct element* right;  
} NODE;  

char character[30];
char nameAnimal[30];
int _TRUE_ = 1, _FALSE_ = 0;

//Функция определения принадлежности к листу (если нет связей)
int isLeaf(NODE* node)
{
  if ((node->left==NULL) && (node->right==NULL)) return _TRUE_;
  return _FALSE_;
}

//Проверяем принадлежность к узлу (есть обе связи)
int isNode(NODE* node)
{
  if ((node->left!=NULL) && (node->right!=NULL)) return _TRUE_;
  return _FALSE_;
}
   
/* Функция добавления характеристики и имени
  Переменная node ссылается на лист в случае ответа НЕТ
  лист трансформируется в узел
  имя узла помещается в лист, при НЕТ (left)
  имя животного помещается в лист при ответе ДА (right)
*/
void addHar (NODE* node) {
  printf ("\nInput a character: ");
  fgets (character, 30, stdin);
  printf ("Input the animal's name: ");
  fgets (nameAnimal, 30, stdin);

  //Создаём левый лист
  NODE* leftN = (NODE*) malloc (sizeof (NODE));
  strcpy (leftN->name, node->name); //Имя листа копируется с узла
  leftN->left = NULL; //Связей нет
  leftN->right = NULL;
   
  //Создаём правый лист
  NODE* rightN = (NODE*) malloc (sizeof (NODE));
  rightN->left = NULL;
  rightN->right = NULL;
  strcpy (rightN->name, nameAnimal); //Правый лист ДА, имя животного
   
  //Меняем имя узла, прикручиваем связи на правый и левый листы, созданные выше
  strcpy (node->name, character); //Имя узла меняется на характеристику
  node->left = leftN;
  node->right = rightN;  
}  
   
// Рекурсивная функция управляемого спуска по дереву  
void perebor (NODE* node) {
   
  printf (node->name);
  printf ("\nYes or No ?(y/n):");  
  char ch=getchar();
  fflush(stdin);

  if (ch=='y') {
  if (isNode(node)) //если узел - это узел
  perebor (node->right); //начинаем перебор с ветки да
  else { //иначе это лист ветви ДА, значит это - решение  
  printf ("This is %s\n",node->name);
  printf ("\nExit ? (y/n):");
  char ch=getchar();
  fflush(stdin);
  if (ch=='y') exit(_TRUE_);}
  }
  else {
  if (!isLeaf(node)) //если узел
  perebor (node->left); //начинаем перебор с ветки НЕТ
  else // иначе это лист  
  addHar (node); // добавляем характеристики
  }
}

int main(int argc, char *argv[]) {
  //Создаём узел с двумя листами  
  NODE* left = (NODE*) malloc (sizeof (NODE));
  strcpy (left->name,"Cat");
  left->left = NULL;
  left->right = NULL;
   
  NODE* right = (NODE*) malloc (sizeof (NODE));
  strcpy (right->name,"Kit");
  right->left = NULL;
  right->right = NULL;
   
  NODE* root = (NODE*) malloc (sizeof (NODE));
  strcpy (root->name, "Big");
  root->left = left;
  root->right = right;
   
  //Бесконечный цикл перебора
  while (_TRUE_) perebor (root);
   
  //Очищаем память от хранящихся в ней данных
  free (root);
  free (right);
  free (left);

  return _TRUE_;
}

typedef struct element{  
  struct element* left;  
  char name[30];  
  struct element* right;  
} NODE;

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  

#define NODE_COUNTS 10
#define MAX_NAME_LENGHT 30

#ifdef _DEBUG
  #define DEB 1
#else
  #define DEB 0
#endif

#define showInfo(param) if (DEB) printf("%s\n",param)
#define showDigInfo(param0,param1) if (DEB) printf("%s - %d\n",param0,param1)

typedef struct element{  
  struct element* left;  
  char name[MAX_NAME_LENGHT];  
  struct element* right;  
} NODE;  

char character[MAX_NAME_LENGHT];  
char nameAnimal[MAX_NAME_LENGHT];
NODE** masNodes;
int nodeCount=0;
int pereborCount=0;
int _TRUE_ = 1,  
  _FALSE_ = 0;
int dif=1;

//Проверяем принадлежность к узлу (есть обе связи)  
int isNode(NODE* node)  
{  
  if ((node->left!=NULL) && (node->right!=NULL))  
  return _TRUE_;  
  return _FALSE_;  
}  

NODE* createNode (const char nameIn[MAX_NAME_LENGHT], NODE* leftNode, NODE* rightNode) {
  NODE* p = NULL;
  NODE* tmp = NULL;

  showDigInfo("nodeCount - ", nodeCount);
  if (nodeCount > (NODE_COUNTS*dif - 1)) {
  showInfo("adding mem for nodes");
  dif++;
  realloc(masNodes, sizeof(NODE*) * NODE_COUNTS * dif);
  }
  p = (NODE*) malloc (sizeof(NODE));
  strcpy (p->name, nameIn);  
  p->left = leftNode;  
  p->right = rightNode;
  *(masNodes+nodeCount) = p;
  nodeCount++;
  return p;
}

void freeMem(void) {
  int i;

  showDigInfo("free mem, all node - ", nodeCount);
  for (i=0; i<nodeCount; i++) {
  free(*(masNodes+i));
  }
}

/* Функция добавления класса и названия животных
Переменная node ссылается на лист в случае ответа НЕТ  
лист трансформируется в узел  
имя узла помещается в лист, при НЕТ (left)  
имя животного помещается в лист при ответе ДА (right)  
*/  
void addHar (NODE* node) {
  char tmpName[MAX_NAME_LENGHT];
  printf ("\nInput a class of animal: ");  
  fgets (character, MAX_NAME_LENGHT, stdin);  
  printf ("Input the animal's name: ");  
  fgets (nameAnimal, MAX_NAME_LENGHT, stdin);  

  //Меняем имя узла, прикручиваем связи на правый и левый листы, созданные выше  
  strcpy(tmpName, node->name);
  strcpy (node->name, character); //Имя узла меняется на характеристику  
  node->left = createNode (tmpName, NULL, NULL);  
  node->right = createNode (nameAnimal, NULL, NULL);  
}  

// Рекурсивная функция управляемого спуска по дереву  
void perebor (NODE* node) {
  char ch=0;
  int i=0;

  pereborCount++;

  showDigInfo("Level - ", pereborCount);

  printf (node->name);  
  printf ("\nYes or No ?(y/n):");  
  ch=getchar();  
  fflush(stdin);  

  //Двигаемся вправо
  if (ch=='y') {  
  if (isNode(node)) { //если узел - это узел  
  perebor (node->right); //начинаем перебор с ветки да  
  } else { //иначе это лист ветви ДА, значит это - решение  
  printf ("This is %s\n", node->name);  
  printf ("Exit ? (y/n):");  
  ch=getchar();  
  fflush(stdin);  
  if (ch=='y') {  
  freeMem();
  exit(_TRUE_);
  } else {
  pereborCount = 0;
  addHar(node);
  }
  }  
  } //иначе двигаемся влево  
  else {  
  if (isNode(node)) { //если узел  
  perebor (node->left); //начинаем перебор с ветки НЕТ  
  } else { // иначе это лист  
  pereborCount = 0;
  addHar (node); // добавляем характеристики  
  }
  }
}  

int main(int argc, char *argv[]) {  
  NODE* left = NULL;
  NODE* right = NULL;
  NODE* root = NULL;
  masNodes = (NODE**)calloc(NODE_COUNTS, sizeof(NODE*));
  showInfo("DEBUG version\n");
  //Создаём узел с двумя листами
  root = createNode("Big", left, right);
  left = createNode("Cat", NULL, NULL);
  right = createNode("Kit", NULL, NULL);
  root->left = left;
  root->right = right;

  //Бесконечный цикл перебора  
  while (_TRUE_) {
  perebor (root);  
  }

  //Очищаем память от хранящихся в ней данных  
  free(masNodes);
  return _TRUE_;  
}