Информатика и информационные технологии: конспект лекций

Function Tree(n : Byte) : TreeLink;

Var t : TreeLink; nl,nr,x : Byte;

Begin

If n = 0 then Tree := nil

Else

Begin

nl := n div 2;

nr = n – nl – 1;

writeln('Введите номер вершины ');

readln(x);

new(t);

t^.inf := x;

t^.left := Tree(nl);

t^.right := Tree(nr);

Tree := t;

End;

{Tree}

End.

2. В бинарном упорядоченном дереве найти узел с заданным значением ключевого поля. Если такого элемента в дереве нет, то добавить его в дерево.

Procedure Search(x : Byte; var t : TreeLink);

Begin

If t = nil then

Begin

New(t);

t^inf := x;

t^.left := nil;

t^.right := nil;

End

Else if x t^.inf then

Search(x, t^.left)

Else if x t^.inf then

Search(x, t^.right)

Else

Begin

{обработка найденного элемента}

…

End;

End.

3. Написать процедуры обхода дерева в прямом, симметричном и обратном порядке соответственно.

3.1. Procedure Preorder(t : TreeLink);

Begin

If t nil then

Begin

Writeln(t^.inf);

Preorder(t^.left);

Preorder(t^.right);

End;

End;

3.2. Procedure Inorder(t : TreeLink);

Begin

If t nil then

Begin

Inorder(t^.left);

Writeln(t^.inf);

Inorder(t^.right);

End;

End.

3.3. Procedure Postorder(t : TreeLink);

Begin

If t nil then

Begin

Postorder(t^.left);

Postorder(t^.right);

Writeln(t^.inf);

End;

End.

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

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

Procedure Delete1(x : Byte; var t : TreeLink);

Var p : TreeLink;

Procedure Delete2(var q : TreeLink);

Begin

If q^.right nil then Delete2(q^.right)

Else

Begin

p^.inf := q^.inf;

p := q;

q := q^.left;

End;

End;

Begin

If t = nil then

Writeln('искомого элемента нет')

Else if x t^.inf then

Delete1(x, t^.left)

Else if x t^.inf then

Delete1(x, t^.right)

Else

Begin

P := t;

If p^.left = nil then

t := p^.right

Else

If p^.right = nil then

t := p^.left

Else

Delete2(p^.left);

End;

End.

ЛЕКЦИЯ № 10. Графы

1. Понятие графа. Способы представления графа

Граф – пара G = (V,E), где V – множество объектов произвольной природы, называемых вершинами, а Е – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство Е могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и Е конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно – орграф, иначе – неориентированным. Ребра орграфа называются дугами. В дальнейшем будем считать, что термин «граф», применяемый без уточнений (ориентированный или неориентированный), обозначает неориентированный граф.

Если е = u,v, то вершины v и и называются концами ребра. При этом говорят, что ребро е является смежным (инцидентным) каждой из вершин v и и. Вершины v и и также называются смежными (инцидентными). В общем случае допускаются ребра вида е = v, v; такие ребра называются петлями.

Степень вершины графа – это число ребер, инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер: Sum(deg(vi), i=1…|V|) = 2 * |E|.

Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес, длина ребра – число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д.