Работа со структурами данных типа дерево.

В данном разделе собраны задачи, которые позволяют освоить методы работы со структурами данных типа дерево. Из всего многообразия деревьев рассматриваем только бинарные деревья, то есть ветвление из каждого узла дерева возможно только в двух направлениях: направо и налево.

Структура данных, позволяющая описать элемент такого дерева это:

type pElem=^Elem;

Elem=record

inf: integer;

left,right: pElem;

end;

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

procedure postfix(t:pElem);

Begin

if t<>nil then begin

postfix(t^.left);

postfix(t^.right);

{операции над узлом }

end;

end; {Это постфиксный вариант чтения дерева, когда знак операции располагается после операнда}

procedure infix(t:pElem);

Begin

if t<>nil then begin

infix(t^.left);

{операции над узлом }

infix(t^.right);

end; {Это инфиксный вариант чтения дерева, когда знак операции располагается между операндами- обычный вариант записи формул}

end;

procedure prefix(t:pElem);

Begin

if t<>nil then begin

{операции над узлом }

prefix(t^.left);

prefix(t^.right);

end;

end; {Это префиксный вариант чтения дерева, когда знак операции располагается до операнда}

 

2.5.1. Задается набор ключевых слов для анализа правильности записи некоторой программы на абстрактном языке. Записать все ключевые слова в виде дерева, упорядочив слова по алфавиту. Обеспечить с помощью методов объекта с данными типа дерева следующие способы обработки слов: поиск в тексте ключевых слов с указанием уровня, на котором слово найдено, определение количества слов, правильности записи слов. Исходные данные в виде списка слов и текста создать и хранить в файлах.

2.5.2. Дана последовательность из N целых чисел. Записать значения элементов последовательности упорядоченными по возрастанию в виде двоичного дерева.

Разработать методы объекта дерева:

Ø определения числа узлов дерева

Ø определения числа листьев

Ø вывод результатов обработки

Ø меню, обеспечивающее процесс создания, сохранения и обработки дерева.

2.5.3. Ввести последовательность из N элементов. Создать из последовательности дерево, в котором элементы последовательности расположены в порядке убывания своих значений. Разработать методы объекта дерева для обхода дерева от листьев к вершине и наоборот. Методы должны также включать ввод произвольной последовательности, сохранение элементов последовательности в файле и вывод результатов обходов дерева.

2.5.4. Ввести последовательность из N элементов, представляющих собой следующую информацию:

ключ

фамилия

номер группы

Представить все сведения в виде дерева, упорядоченного по ключам.

Разработать методы объекта дерева: сортировки дерева по ключам, сортировки по фамилиям, ввод новых данных, удаление данных по ключу, вывод сведений по номерам групп, сохранение исходных данных в файлах.

2.5.5. Разработать объект дерево для вычисления произвольной формулы, содержащей только знаки арифметических операций и переменные.

Реализовать обходы дерева, обеспечивающие два способа записи формулы:

Ø инфиксный

Ø префиксный

Методы объекта для данных типа дерева должны также обеспечить ввод формулы, ее вычисление и вывод результатов, сохранение в памяти введенной формулы, исправление любого операнда.

Пояснение: Названные в задаче методы обхода дерева соответствуют приведенным вариантам записи формул:

Ø * + abcd - *ef --- префиксная запись - знак предшествует операнду

Ø a+bc*d - e*f --- инфиксная запись - обычное представление

2.5.6. Разработать объект дерево для вычисления произвольной формулы, содержащей только знаки арифметических операций и переменные.

Реализовать обходы дерева, обеспечивающие два способа записи формулы:

Ø инфиксный

Ø постфиксный

Пояснение: Названные в задаче методы обхода дерева соответствуют приведенным вариантам записи формул:

Ø a+bc*d - e*f --- инфиксная запись - обычное представление

Ø abcd +/ *ef* - --- постфиксная запись - знак операции ставится после операнда.

Методы должны обеспечивать ввод, вывод результатов и сохранение введенной формулы, исправление любого из операндов, изменение операции.

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

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

2.5.9. Разработать объект-дерево для выполнения следующих операций над последовательностью из произвольного количества слов, которая в памяти представлена в виде дерева. Определить количество вхождений каждого слова в дерево. Для оформления результатов этой обработки создать список- слово, количество вхождений. Определить максимальную глубину дерева, т.е. число ветвей на пути от корня до листа. Подсчитать число вершин на любом N-ом уровне дерева (корень считается вершиной 0-го уровня).

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

2.5.11. В файле записана некоторая программа на языке Паскаль. Известно, что каждое служебное слово содержит не более 9 символов. Разработать объект- дерево из элементов - служебное слово и количество вхождений этого слова в текст программы.

Методы обработки объекта должны обеспечить сортировку слов по количеству вхождений в текст программы, выдачу номеров строк программы, в которых встречается каждое из найденных служебных слов, определение глубины дерева.

2.5.12. Разработать дерево для вычисления произвольной формулы, содержащей только знаки арифметических операций и переменные.

Реализовать обходы дерева, обеспечивающие два способа записи формулы:

Ø префиксный

Ø постфиксный

* + abcd - *ef --- префиксная запись - знак предшествует операнду.

abcd +/ *ef* - --- постфиксная запись - знак операции ставится после операнда.

Методы объекта должны обеспечивать ввод, вывод результатов и сохранение введенной формулы.

2.5.13. Разработать дерево для упорядочивания по алфавиту всех служебных слов языка Object pascal. Обеспечить поиск любого из слов в дереве, с указанием уровня, на котором находится это слово. Ввести произвольный текст на языке. Проверить правильность записи служебных слов. При обнаружении ошибок в записи слов выводить сообщение: какое слово неверно записано и как надо его записать правильно. Методы объекта должны обеспечивать ввод, вывод результатов и сохранение введенных слов и текстов в файлах через соответствующие альтернативы меню.

2.5.14. Каталог файлов, к которым происходит обращение в некоторой прикладной системе программ, организован в виде двоичного дерева. В каждом узле дерева записано имя соответствующего файла и последняя дата обращения к этому файлу. Разработать объект, который обеспечивает создание дерева из файлов, удаление из дерева тех файлов, обращения к которым не производились в последние N дней. Список из этих файлов создать в виде некоторого резервного списка и при очередном запуске программы всегда проверять дерево и список. При необходимости запуска файла из резервного списка этот файл вместе с датой его вызова опять заносится в дерево. Методы объекта должны обеспечить создание и сохранение всех исходных и промежуточных данных в файлах.

2.5.15. Разработать объект- дерево для создания последовательности чисел Фибоначчи. Методы работы с деревом Фибоначчи должны обеспечить сохранение найденного количества чисел в файле, определение суммы чисел Фибоначчи до заданного числа K, меньшего количества найденных и записанных в виде дерева чисел, поиск введенного числа и определение уровня его в дереве, печать дерева чисел Фибонччи до заданного числа. Предусмотреть удаление всего дерева и создание нового дерева Фибоначчи.

2.5.16. Разработать объект для анализа текста. Текст, вводимый с клавиатуры и хранящийся в файле, прочитывается и записываетсся по словам в виде дерева, в котором все слова упорядочены по длине. На вершине дерева находится самое длинное слово. Обеспечить удаление слова заданной длины из дерева, вставку нового слова в дерево на правильное место, исправление слова и правильное его размещение в дереве. Вывод всех этапов преобразования на экран должен отражать изменения в дереве.

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

 

ПРИМЕР 2.5.

В качестве примера рассмотрим создание сбалансированного дерева и выполнение всех действий с элементами дерева: поиск заданного элемента в дереве, вставку любого нового элемента, удаление заданного элемента из дерева, вывод дерева в достаточно наглядной форме. Решение задачи состоит из двух файлов: основной программы и модуля, в котором описаны все названные действия над элементами дерева.

Program Number_2_5;

uses crt,prg11;

Var

tree:ttree;

c:integer;

procedure pause;

Begin

write('Нажмите любую клавишу для продолжения');

readkey;

while keypressed do readkey;

end;

procedure menu;

Begin

clrscr;

writeln(' Выберите действие');

writeln('1. Создание дерева');

writeln('2. Вывод дерева на экран');

writeln('3. Нахождение требуемого элемента');

writeln('4. Удаление элемента из дерева');

writeln('5. Добавление элемента в дерево');

writeln('6. Завершение работы');

writeln;

Case readkey of

'1': begin

write ('Введите количество узлов дерева ');

readln(c);

tree.first:=tree.create(c);

clrscr;

gotoxy(30,10);

writeln('Дерево создано');

pause;

end;

'2': begin

tree.vivod(tree.first,0);

pause;

end;

'3': begin

write('Введите искомый элемент ');

readln(c);

tree.findel(tree.first,0,c);

tree.vivod(tree.first,0);

pause;

end;

'4': begin

write('Введите удаляемый элемент ');

readln(c);

tree.delel(tree.first,c);

pause;

end;

'5': begin

write('Введите новый элемент ');

readln(c);

tree.addel(c,tree.first);

tree.vivod(tree.first,0);

pause;

end;

'6': begin

write(' Завершение задачи ');

tree.done(tree.first);{Уничтожение дерева}

halt;

end;

end; end;

Begin

tree.init;

repeat menu until false;

End.

unit prg11;

Interface

Type

pnode=^node;

node= record

key:integer;

left,right:pnode;

end;{один элемент двоичного дерева}

ttree= object {объект, для работы со структурой

данных типа дерева}

n: integer;{число узлов в дереве}

f,first:pnode;

constructor init;

destructor done(var t:pnode);

function create(m:integer):pnode;

procedure vivod(var t:pnode;m:integer);

procedure findel(var t:pnode;m:integer;ikey:integer);

procedure delel(var t:pnode;ikey:integer);

procedure addel(ikey:integer;var t:pnode);

end;

Implementation

uses crt;

constructor ttree.init;

Begin

first:=nil;

n:=0;{создаем элемент пустого дерева}

end;

destructor ttree.done(var t:pnode);

Begin

if t<>nil then

Begin

with t^ do begin

done(left);

done(right);

end;

dispose(t);{Уничтожаем все дерево}

end;

end;

function ttree.create(m:integer):pnode;

var newnode:pnode;

x,nl,nr:integer;

Begin

n:=m;

if n=0 then

Begin

create:=nil;

exit;

end;

nl:=n div 2;

nr:=n-nl-1;

{Создаем сбалансированное дерево}

new(newnode);

with newnode^ do begin

write('Введите очередное число ');

readln(key);

left:=create(nl);

right:=create(nr);

end;

create:=newnode;

end;

procedure ttree.vivod(var t:pnode;m:integer);

var i: word;

Begin

if t<> nil then {процедура вывода дерева

также рекурсивна, как и функция для его создания}

with t^ do begin

vivod(left,m+1);

for i:=1 to m do write('***');

writeln(key);

vivod(right,m+1);

End else

if m= 0 then

writeln('Дерева уже нет или еще нет!');

end;

procedure ttree.findel(var t:pnode; m:integer; ikey:integer);

Begin

if t<> nil then

with t^ do begin

findel(left,m+1,ikey);

if key=ikey then

Begin

writeln(' Элемент на ',m+1,'-ом уровне ');

writeln(ikey);

end;{Процедура поиска элемента в дереве