Полный обучающий курс (стр. 60 )

then

begin

SetColor(n+1);

Line(x1,y1+10,x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10);

SetColor(n+2);

Line(x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1-arr[n],y1+arr1[n]-10);

Strel(x1-arr[n],y1+arr1[n]-10,(arr1[n]-20)/arr[n]);

Wiv(y^.next[1],n+1,x1-arr[n],y1+arr1[n]);

end;

if y^.next[2] <> nil

then

begin

SetColor(n+1);

Line(x1,y1+10,x1+arr[n],y1+arr1[n]-10);

SetColor(n+2);

Line(x1+(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1+arr[n],y1+arr1[n]-10);

Strel(x1+arr[n],y1+arr1[n]-10,-(arr1[n]-20)/arr[n]);

Wiv(y^.next[2],n+1,x1+arr[n],y1+arr1[n]);

end;

end;

end;

Begin

ClrScr;

Randomize;

Repeat

new(x);

a:=6;

x^.next[1]:=Nil;

x^.next[2]:=Nil;

Zap(x,0);

Max:=x;

Min:=x;

writeln;

grDriver := Detect;

InitGraph(grDriver, grMode,'c:\tp7\bgi\');

SetFillStyle(solidfill,15);

SetColor(15);

Wiv(x,1,320,50);

Delay(5000);

until KeyPressed;

End.

Задание. Поэкспериментируйте над предложенной программой, внося свои изменения. Результат покажите учителю.

Занятие 2. Представление деревьев. Основные операции над деревом.

Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

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

Type

TreeLink = ^Tree;

Tree = Record

Data : <тип данных>;

Left, Right : TreeLink;

End;

Корень дерева опишем в разделе описания переменных:

Var

kd : TreeLink;

К основным операциям над деревьями относятся:

• занесение элемента в дерево;

• обход дерева;

• удаление элемента из дерева.

Рассмотрим вставку и обход дерева на примере следующей задачи.

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

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

Procedure InsTree(n : integer; Var t : TreeLink);

Begin

if t=nil

then

begin

new(t);

with t^ do

begin

Left := nil;

Right := nil;

Data := n;

end;

end;

else

if n<=t^.data

then

InsTree(n, t^.Left)

else

InsTree(n, t^.Right)

End;

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

• вывод числа, хранящегося в узле;

• обход левого поддерева;

• обход правого поддерева.

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

• прямой вывод (сверху вниз);

• обратный вывод (слева направо);

• концевой вывод (снизу вверх).

Процедура обратного вывода дерева имеет следующий вид:

Procedure PrintTree(t : TreeLink);

Begin

if t<>Nil

then

begin

PrintTree(t^.Left);

Write(t^.Data:3);

PrintTree(t^.Right);

end;

End;

Задание. Написать процедуры прямого и концевого вывода значений элементов дерева.

Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.

Begin

writeln('Вводите вершины дерева. Окончание ввода – 0');

kd := nil;

read(Digit);

while Digit <> 0 do

begin

InsTree(Digit, kd);

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

read(Digit);

end;

PrintTree(kd);

End.

Задание. Напишите программу создания и вывода на экран двоичного дерева, используя свою процедуру вывода. Протестируйте программу и представьте учителю файл и листинг для оценки.

Занятие 3. Самостоятельное решение задач.

Выберите с учителем одну из предложенных задач.

1. Создайте программой числовое двоичное дерево. Опишите рекурсивную логическую функцию, проверяющую наличие заданного числа в сформированном дереве. В программе используйте подпрограммы.

2. Создайте программой числовое двоичное дерево. Опишите рекурсивную числовую функцию, подсчитывающую сумму элементов дерева. В программе используйте подпрограммы.

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

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

5. Напишите программу, содержащую процедуру, которая каждый элемент дерева возводит в квадрат.

6. Создайте программой символьное двоичное дерево. Опишите функцию, возвращающую строку, сформированную на базе этих символов. В программе используйте подпрограммы.

7. Создайте программой символьное двоичное дерево. Опишите логическую функцию, проверяющую, есть ли в непустом дереве хотя бы два одинаковых символа. В программе используйте подпрограммы.

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

9. Создайте двоичное дерево записей. Проверьте выбранное поле записей на равенство. В программе используйте подпрограммы.

10. Создайте программой два числовых двоичных дерева. Опишите рекурсивно и нерекурсивно логическую функцию, входными параметрами которой являются два дерева, проверяющую на равенство эти деревья. В программе используйте подпрограммы.

Занятие 4. Идеально сбалансированное дерево.

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

Использование деревьев поиска значительно сокращает время решения задачи.

Правильно организованным деревом считается идеально сбалансированное дерево, то есть для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.

Сформируем идеально сбалансированное дерево, элементами которого являются N чисел, вводимых с клавиатуры.

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

• Взять один узел в качестве корня.

• Построить левое поддерево с числом узлов n1=N div 2 тем же способом.

• Построить правое поддерево с числом узлов n2=N-n1-1 тем же способом.

Program BalansTree;

Uses

Crt;

Type

Pt = ^Node;

Node = record

Data : integer;

Left, Right : Pt;

end;

Var

n : integer;

kd : Pt;

f : text;

Function Tree(n : integer) : Pt;

Var

NewNode : Pt;

x, n1, n2 : integer;

Begin

if n=0

then

Tree := Nil

else

begin

n1 := n Div 2;

n2 := n–n1–1;

read(f, x);

new(NewNode);

with NewNode^ do

begin

Data := x;

Left := Tree(n1);

Right := Tree(n1);

end;

Tree := NewNode;

end;

End;

Procedure PrintTree(t : Pt; h : integer);

Var

i : integer;

Begin

if t<>nil

then

with t^ do

begin

PrintTree(Left, h+1);

for i := 1 to h do

write(' ');

writeln(Data:6);

PrintTree(Right, h+1);

end;

End;

Begin

ClrScr;

assign(f, 'c:\f. pas');

reset(f);

write('n=');

readln(n);

kd := Tree(n);

PrintTree(kd, 0);

readln;

End.

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.

Поиск и включение элемента в дерево.

Задача. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательности.

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

Program Poisk;

Uses

Crt;

Type

Words = ^WordTree;

WordTree = record

Data : string;

k : integer;

Left, Right : Words;

end;

Var

n : integer;

kd : Words;

x : string;

f : text;

Procedure Tree(x : string; Var p : Words);

Begin

if p=nil

then

begin

new(p);

with p^ do

begin

k := 1;

Data := x;

Left := Nil;

Right := Nil;

end;

end;

else

if x>p^.Data

then

Tree(x. p^.Left)

else

if x<p^.Data

then

Tree(x. p^.Right)

else

Inc(p^.k);

End;

Procedure PrintTree(t : Words; h : integer);

Var

i : integer;

Begin

if t <> Nil

then

with t^ do

begin

PrintTree(Left, h+1);

for i := 1 to h do

write(' ');

writeln(Data, ',(', k, ')');

PrintTree(Right, h+1);

end;

End;

Begin

ClrScr;

assign(f, 'c:\f. dan');

reset(f);

write('n=');

readln(n);

kd := Nil;

while n>0 do

begin

readln(f, x);

Tree(x, kd);

Dec(n);

end;

close(f);

PrintTree(kd, 0);

readln;

End.

Эта задача называется задачей поиска по дереву с включением.

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