/♦Функция выделяет пс1мять под структуру tnod и возвращает указатель на

эту Пс1МЯТЬ*/

tnod *р=р=(tnod *)malloc(S i zeof(tnod)); return(p);

tnod *MakeTree(tnod *p,char *w)

/*Эта функция формирует двоичное дерево.

р-указатель на структуру, по которой будет создаваться новый узел или будут проверяться старые узлы.

w-слово, поступающее для его поиска в дереве.

Если такое слово уже есть, то в счетчик структуры, где оно обнаружено, добавляется единица: подсчитывается, сколько одинаковых слов.

Если такого слова в дереве нет, то для него образуется новый узел (новая структура)

int cond;

if(p==NULL) /*появилось новое слово. Для этого слова еще нет узла и его надо создать*/

p=NodAlloc(); выделяется Пс1мять под новый узел

p->word=strsave(w);

/*введенное слово по strsaveO записывается в память и на него выдается указатель */

p->count =1; слово пока единственное

p->left=p->right= NULL;

/*т. к. это слово пока последнее в дереве, то этот узел не указывает на следующие (меньшие - слева или большие - справа) слова дерева*/

else if((cond=strcmp(w,p->word))==0)

/* слово не новое, тогда оно сравнивается со словом в узле, на который указывает указатель р*/

p->count++;

/*в этом узле - такое же слово, поэтому добавляем к счетчику единицу*/ else if(cond < 0)

-----------------------------

int TreePrint (tnod *р)

/Эта функция печатает или выводит на экран все дерево, рекурсивно себя вызьшая*/

if(p != NULL) I

TreePrint(p->left); выводит левый узел:

printf( p->count=%d p->word=%s\n ,p->count,p->word);

TreePrint(p->right); выводит правый узел

return (0); }

-------------------------------------------------------------

Ipragma argsused

int tmain(int argc, char* argv[]) I

tnod *pp,-

char s [maxline];

pp=NULL;

/ слово меньше того, которое в узле, поэтому его помещаем в левую часть к дерева опять же с помощью этой функции. Ее первая часть создаст узел в I динамической памяти, поместит в него слово, в левые и правые подузлы по-liieCTOT нули, т. к. пока дальше этого слова ни справа, ни слева ничего

нет, а в левую часть узла-предка поместит указатель на эту структуру */

p->left=MakeTree(p->left,w);

else if(cond > 0)

p->right=MakeTree(p->right,w);

/слово больше того, которое в узле, поэтому мы его помещаем в правую часть дерева опять же с помощью этой же функции: ее первая часть создаст узел в динамической памяти, поместит в него слово, в левые и правые подузлы поместит нули, т. к. пока дальше этого слова ни справа, ни слева ничего нет, а в правую часть уэла-предка поместит указатель на эту структуру */

return (р) ;

/возвращает указатель на область, где создана новая структура, или на структуру, в которую добавлена единица, т. к. поступившее слово совпало со словом в этой структуре*/

Глава}

int i=0;

printf( Enter your words: >\n ); while(getline(s,maxline)-1)

/*getline() возвращает количество введенных символов

Когда нажимаем только <Enter>, вводится всего один символ (\п).

Если от единицы отнять единицу, получим нуль, а это - для оператора while] сигнал о прекращении цикла*/

рр=МакеТгее(рр,S); формирует очередной узел

рр всегда указывает на начало дерева

} while TreePrint(рр); вывод дерева getch();

C:\WIND0WS\sy8tem32\cmd.exe

Рис. 7.10. Результат работы программы листинга 7.10

Физическая структура дерева приведена в табл. 7.1, а логическая - рис. 7.11.

Таблица 7.1. Физическая структура дерева! построенного программой листинга 710