Что общего между лексической игрой "Отгадай слово" и двоичным деревом?

Садовая Ирина Владимировна

Процесс поиска решения был трудным и, одновременно, захватывающим. И вот к чему пришли.

Используется словарь, содержащий более 43000 тысяч существительных (словарь, правда, пришлось искать в Интернете). Эти слова хранятся в текстовом файле. Теперь каждый ход игрока должен проверяться на наличие такого слова в словаре, то есть категорически не разрешается использовать в качестве тестов отдельные буквы. Простое перечисление букв запрещено.

В программе используется динамическая структура данных - двоичное дерево. Раздел программирования "Динамические структуры данных" достаточно труден для усвоения, но в данной ситуации, был изучен учащимся с огромным интересом и глубоким пониманием. Сочли, что применение именно этой структуры значительно сэкономит объем оперативной памяти и позволит реализовать более быстрый поиск слова в словаре. Сам словарь пришлось составить таким образом, чтобы в начале файла находились слова с такой буквы, с какой их больше всего в словаре, и, соответственно, в конце словаря находятся слова, каких меньше всего. Рекордсменами оказались слова, начинающиеся на букву П - их более 6000, затем идут слова с буквы С - около 4000, потом буква К - более 3000 и т.д.

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

Итак, описание вершины дерева имеет вид:

Type pt = ^node;
node = record
data : char; {информационное поле - одна буква}
left, right : pt; {ссылки на левого и правого потомков}
fin : boolean; {признак, является ли данная буква окончанием какого- либо слова}
end;

Логику построения дерева рассмотрим на примере словаря, содержащего 5 слов:
Пасс
Пассаж
Паста
Пастух
Пар

Корень дерева - вершина первого уровня содержит первую букву первого слова - П, далее размещаем по правым потомкам буквы - а, с, с. У вершины, содержащей вторую букву "с", признак окончания слова должен быть равен "истина" (на рисунке это знак ' ), правый потомок должен быть равен nil и левые потомки всех вершин также равны nil.