Шрифт:
Можно поступить таким образом: поменять удаляемый узел местами с узлом, имеющем самое большое значение ключа в левом поддереве, или с узлом, имеющем самое малое значение ключа в правом поддереве, а затем удалить искомый узел как лист.
При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.
Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссьшкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом:
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|.