Информатика и информационные технологии: конспект лекций
Шрифт:
Можно поступить таким образом: поменять удаляемый узел местами с узлом, имеющем самое большое значение ключа в левом поддереве, или с узлом, имеющем самое малое значение ключа в правом поддереве, а затем удалить искомый узел как лист.
При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.
Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного
TYPE TreeLink = ^Tree;
Tree = record;
Inf : <тип данных>;
Left, Right : TreeLink;
End.
3. Примеры реализации операций
1. Построить дерево из n узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).
Рекурсивный алгоритм построения:
1) первый узел берется в качестве корня дерева.
2) тем же способом строится левое поддерево из nl узлов.
3) тем же способом строится правое поддерево из nr узлов;
nr = n – nl – 1. В качестве информационного поля будем брать номера узлов, вводимые с клавиатуры. Рекурсивная функция, реализующая данное построение, будет выглядеть следующим образом:
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|.
Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес, длина ребра – число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д.
Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг – в орграфе) вида v0, (v0,v1), v1…, (vn – 1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин – простой цепью. Путь может быть замкнутым (v0 = vn). Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) – простым циклом.
Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным – в противном случае. Несвязный граф состоит из нескольких связных компонент (связных подграфов).
Существуют различные способы представления графов. Рассмотрим каждый из них в отдельности.
1. Матрица инцидентности.
Это прямоугольная матрица размерности n х щ, где n – количество вершин, am – количество ребер. Значения элементов матрицы определяются следующим образом: если ребро xi и вершина vj инцидентны, то значение соотвествующего элемента матрицы равно единице, в противном случае значение равно нулю. Для ориентированных графов матрица инцидентности строится по следующему принципу: значение элемента равно – 1, если ребро xi исходит из вершины vj, равно 1, если ребро xi заходит в вершину vj, и равно О в противном случае.