СиАОД4

#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define N 6

int trueN=0;

typedef struct tsapex
	{
	  char x;
	  struct tsapex *left,*right;
	} tapex;

typedef struct tsitem
	{
	  struct tsitem *next;
	  tapex *link;
	} titem;

void FIFOput(titem **head, titem **tail, tapex *apex)
{
  titem *item=NULL;
  if(apex)
  {
  item=(titem *)malloc(sizeof(titem));
  item->link=apex;
  item->next=NULL;
  };
  if((*head))
  {
    (*tail)->next=item;
    (*tail)=(*tail)->next;
  }
  else
    (*head)=((*tail)=item);
};

tapex *FIFOget(titem **head)
{
  titem *t=(*head)->next;
  tapex *link=(*head)->link;
  free((*head));
  (*head)=t;
  return link;
};

int FIFOempty(titem *head)
{
  return (head==NULL);
};

int calcChild(tapex *root)
{
  int t=0;
  if(root==NULL)
    t=0;
  else
  {
    if(root->left)
    {
      t++;
      t+=calcChild(root->left);
    };
    if(root->right)
    {
      t++;
      t+=calcChild(root->right);
    };
  };
  return t;
};

int widthSearch(tapex *root)
{
  static int n=0;
  titem *head=NULL,*tail=NULL,t;
  tapex *link;
  FIFOput(&head,&tail,root);
  while(!FIFOempty(head))
  {
    link=FIFOget(&head);
    if(calcChild(link)<=1)
      n++;
    if(link->left)
      FIFOput(&head,&tail,link->left);
    if(link->right)
      FIFOput(&head,&tail,link->right);
    printf("%c ",link->x);
  };
  return n;
};

tapex *generate(int r)
{
  static char name='a';
  if((random(r/2)+random(r))*r)
  {
    tapex *root=(tapex*)malloc(sizeof(tapex));
    root->left=generate(r-1);
    root->x=(name++);
    root->right=generate(r-1);
    return root;
  }
  else
    return NULL;
};

void out(tapex *root)
{

  static y=1,x=40;
  gotoxy(x,y);
  if(root)
  {
    trueN++;
    printf("%c",root->x);
    y++;
    x=x-64/pow(2,y);
    out(root->left);
    x=x+2*64/pow(2,y);
    out(root->right);
    x=x-64/pow(2,y);
    y--;
  }
  else
    printf(".");
};

void clear(tapex *head)
{
  if(head)
    {
      clear(head->left);
      clear(head->right);
      free(head);
    };
};

int main()
{
  randomize();
  clrscr();
  tapex *head=NULL;
  head=generate(N);
  out(head);
  printf("\n\n\n\n\n\n\n");
  printf("\n%d \n",widthSearch(head));
  clear(head);
  return 0;
};