( Примечание

Двоичное дерево - это такая конструкция, которая отображает связь между данными исходя из того, что данные находятся в так называемых узлах. Под узлом понимается переменная типа структура (ее еще называют записью). Первая запись двоичного дерева (его корень) содержит один узел. В узле содержится некая полезная информация, для обработки которой мы и строим само дерево, а также два указателя на нижестоящие узлы. Из корневого узла вырастают всего две веточки : левый нижний узел (первый указатель) и правый нижний узел (второй указатель). Из каждого из этих узлов тоже вырастает по две веточки и т. д. Можно сказать, что в такой конструкции каждый узел - это тоже двоичное дерево (корень, из которого выходят две веточки ).

В нашем случае двоичное дерево строится так:

□ никакой узел этого дерева не содержит более двух ближайших потомков (детей);

П в корневом узле слова нет;

П первое поступившее слово записывается в корневой узел, а остальные поступающие будут распределяться так: если поступившее слово меньше первого, то оно записывается в левое поддерево, если больше корневого - в правое;

П каждое слово будет находиться в структуре типа (***);

П слово записывается в переменную word, а счетчик count в данной структуре устанавливается в единицу: слово пока что встретилось (в нашем случае, введено) один раз.

Если встретится еще такое же слово, то к счетчику count в данной структуре добавится единица. При этом в корневой структуре в переменной left формируется указатель на структуру, в которую записалось слово меньшее, чем слово в корневой структуре. Если же поступило слово, которое больше слова в корневой структуре, то оно записывается, как уже говорилось, в отдельную аруктуру (узел), а указатель на этот узел записывается в переменную right корневой структуры.

Потом вводится третье слово. Оно опять сравнивается со словами, находящимися в структурах дерева (***), начиная с корневой структуры и далее по тем же принципам, что описаны ранее. Если поступившее слово меньше корневого, то дальнейшее сравнение идет в левой части дерева. Это означает, что из корневой структуры выбирается указатель, хранящийся в переменной left, по нему отыскивается следующее (меньшее, чем в данном узле) слово, с которым и станет сравниваться поступившее. Если поступившее слово

меньше, то из нового узла извлекается указатель, хранящийся в переменной left, и по нему выбирается следующий левый узел и т. д.

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

В итоге получим двоичное дерево: от каждого узла будут выходить не более двух подузлов и таких, что в левом подузле всегда будет слово меньшее, чем в самом узле, а в правом подузле всегда будет находиться слово большее, чем в в самом узле. Так как физически каждое слово будет находиться в отдельной структуре типа (***), то в этой же структуре в переменных left и right будут располагаться указатели на структуры, где хранятся подузлы данной j структуры. И все это дерево располагается в памяти.

Программа, реализующая рекурсию в структурах, приводится в листинге 7.10. На рис. 7.10 отражен результат выполнения этой программы.

/1истинг7.10 ,

ЗО.срр : Defines the entry point for the console application.

#include stdafx.h ♦include <stdio.h> ttinclude <conio.h> ttinclude <string.h> ttinclude <malloc.h>

strcpyO

ttdefine maxline 1000 ttdefine eof -1

-------Ввод строки с клавиатуры

int getline(char s[],int lim) {

/Функция выделяет по maiioc () память по длине строки s, ив эту Пс1мять помещает саму строку s, а затем выдает указатель на начало помещенной в буфер строки. */

char *р;

p=(char *)malloc(sizeof(strlen(s)+l));

if((p != NULL) ) strcpy(p, s); return (p) ;

/*т. к. maiiocО выдает указатель типа void, то принудительно приводим его к типу char, чтобы согласовать с р*/

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

tnod *NodAlloc (void)

int с,i;

for(i=0; i<lim-l && (c=getchar()) != eof && с != \n; i++) s[i]=c; s[i] = \0;

i++; для учета количества

return(i) ;

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

struct tnod базовый узел

char *word; значение переменной - символьная строка в узле

(слово)

int count; здесь накапливается число встреч данного слова

struct tnod *left; /*левый потомок: здесь хранится указатель на левый подузел, т. е. на структуру, в которой хранится слово, меньшее данного. Если слов меньших данного нет, то здесь хранится нуль*/

struct tnod *right; /*правый потомок: здесь хранится указатель на правый подузел, т. е. на структуру, в которой хранится слово, большее данного. Если слов больших данного нет, то здесь хранится нуль*/

char *strsave(char *s) С++ позволяет объявлять без слова struct