#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); //Закрытие файла
}
}
int 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);
}
return 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");
i=tree_obxod(ph->left,0);
j=tree_obxod(ph->right,0);
printf("left: %d;\nright:%d",i,j);
break;
case 0: key=0; break;
}
}
}