Структуры данных. Деревья - 25 стр.

UptoLike

Составители:

Рубрика:

function Search_P(T : Tree; ch : char) : Tree;

var flag : boolean; { признак удачного поиска }

begin

flag:=false;

while (T <> nil) and not flag do

if T^.inf = ch then flag:=true

else

if ch < T^.inf then T:=T^.L

else T:=T^.R;

Search_P:=T

end; { Search_P }

Возможности динамического размещения данных более наглядно прояв-

ляются в примерах, где дерево растет или сокращается в ходе выполнения про-

граммы.

Рассмотрим сначала случай, когда дерево только растет, но не убывает.

Типичный пример – построение алфавитного частотного словаря. Задача со-

стоит в чтении

текста, выборке из него слов и подсчете частоты их появления.

Вначале дерево – пустое. Затем, если слово найдено, то счетчик его вхождений

увеличивается на единицу, а если нет, то это - новое слово и оно включается в

дерево с единичным значением счетчика.

Такой алгоритм часто называют [ 2 ] поиском по дереву с включением.

Пример 4.3.

Описать процедуру включения слова в частотный словарь.

В этом случае тип Elem информационной части inf узлов дерева

(см. раздел 2 ) – запись из двух полей: слова ( строки из 20 символов ) и количе-

ства его появления в тексте :