#include <stdio.h> //Подключение необходимых библиотек
#include <string.h>
#include <time.h>

struct tree //задание структуры (двоичного дерева)
{
int nn; //счетчик вершин в поддереве
char *str; //указатель на строку
tree *left,*right;//указатель на левую и правую ветку дерева
};
int num=0;

char *extend (char *c) //Создание строки в динамической памяти
{
	if (c == NULL) return NULL; //выход если строка пуста
	char *newc = new char[strlen(c)+1]; //выделение памяти под новую строку
	strcpy(newc, c); //копирование старой строки в новую
	return newc;
}

//Упорядоченное добавление
void insort (tree *&p, char *c)
{
	if (p == NULL) //если вершина пустая
		{
			p = new tree; //создать ее
			p->str = extend(c); //поместить указатель на строку в динамической памяти
			p->nn = 1;
			p->left = p->right = NULL; //занулить потомки
			return;
		}
	if (strcmp(c, p->str)<0) //если строка меньше текущей
		{
			insort (p->left, c); //рекурсия для левого поддерева
			p->nn++; //увеличение счетчика вершин
		}
	else // иначе - для правого
		{
			insort (p->right, c);
			p->nn++;
		}
	return;
}

//Вывод данных
void show(tree *p, int &n) //Вывод данных на экран с учетом ЛН
{
	if (p==NULL) return;
	show (p->left,n);
	printf("n=%d str=%s\n",++n,p->str);
	show (p->right,n);
}
//Балансировка дерева
tree *podbalance(tree *pp[], int a, int b)
{
	if (a>b) return NULL;  // левая граница перешла правую - выход
	tree *q;
	if (a==b) // в диапазоне одна вершина
		{
			q=pp[a]; q->left=q->right=NULL; q->nn=1; return q;
		}
	q=pp[a]; // первая вершина интервала - корневая
	int m=(a+b+1)/2; // середина оставшегося интервала
	q->left=podbalance(pp,a+1,m-1); // левое и правое поддерево сформировать
	q->right=podbalance(pp,m,b); // рекурсивно из половинок интервала
	q->nn=b-a+1; // счетчик вершин в поддереве -
	return q; // ширина интервала
}

void set(tree *pp[], tree *p, int &ln)
{
	if (p==NULL) return; // ln - порядковый (логический) номер
	pp[ln++]=p; // запомнить указатель на текущую вершину
	set(pp,p->left,ln); // рекурсивно выполнить для поддеревьев
	set(pp,p->right,ln);
}

void balance(tree *&ph)
{
	if (ph==NULL) return;
	int sz=ph->nn;  // создать динамический массив указателей
	tree **pp=new tree*[sz];
	int ln=0;
	set(pp,ph,ln);  //и заполнить его элементами дерева
	ph=podbalance(pp,0,sz-1);  // вызвать рекурсивную функцию балансировки
}

// Функция выделения слов в прочитанной строке
void dist(char in[],tree *&p)
{
	char out[1000];
	int l=strlen(in),sb,i,j;
	if (l==0) return;
	in[l]=' ';
	for (i=0,j=0;in[i]==' ';i++);
	while (i<l+1)
		{
			if (in[i]==' ')
			{
				out[j]=0;
				j=0;
				num++;
				char *str=strdup(out);
				for (;in[i]==' ';i++);
			}
			else out[j++]=in[i++];
		}
}
//Загрузка
void load(tree *&p,char *F)
{
	num=0;
	FILE *fd=fopen(F,"r"); //открытие файла дял чтения
	char c[80];
	if (fd==NULL) { printf ("Error, can't found file\n"); return; }
	else
		{
			int time=clock();
			for (int i=0;fscanf(fd,"%s\n",c)!=EOF;i++) //Чтение построчно до конца файла
			{
				insort (p,c);dist(c,p);
			}
//Упорядоченная вставка строки в дерево
			printf("Time: %ld\n", clock()-time);
			printf("%d words read\n\n",num);
			fclose(fd); //Закрытие файла
		}
}

void tree_obxod(tree *p, int *i)
{
	if(p!=NULL)
		{
			if(p->left!=NULL||p->right!=NULL)
			*i++;
			tree_obxod(p->left,i);
			tree_obxod(p->right,i);
		}
}

//Тело Функции
int main()
{
	tree *ph=NULL, *psort=NULL;
	char newstr[80], searchstr[80],fname[80]; //вспомогательные строки
	int tn=0,a,key=-1,i=0,j=0;
	while(key!=0) //главное меню
		{
			printf ("Menu: \n\n1 - Add\n2 - Balance tree\n3 - Show tree\n4 - Count ");
			printf ("\n0 - Exit\n\nWhat todo?:\n");
                        
                        scanf("%d",&key);
			switch(key)
				{
					case 1: printf ("\nEnter file name: \n");
					scanf("%s",fname);
					load(ph,fname); //Загрузка данных из файла
					break;

					case 2: balance(ph); //Вызов функции балансировки
					break;

					case 3:
					printf("-----------------------\n");
					show (ph,tn); //Выозв функции вывода
					tn=0; //Сброс нумерации вершин
					printf("\n-----------------------\n\n");
					break;

					case 4:
					printf("-----------------------\n");
					tree_obxod(ph->left,&i);
					tree_obxod(ph->right,&j);
					printf("left: %d;\nright:%d",i,j);
                                        break;
                                        case 0: key=0; break;
				}
		}
}