#include //Подключение необходимых библиотек #include #include 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 (ileft!=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; } } }