Реализация бинарных деревьев.
Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева. Остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются левым и правым поддеревьями исходного множества. Каждый элемент бинарного дерева называется узлом дерева.
Если a – корень бинарного, а b – корень его правого или левого поддеревьев, то b называется потомком, или сыном, a. Тогда a – это предок, или отец, b. Узел, не имеющий потомков, называется листом. Два узла называются братьями, если они сыновья одного и того же отца. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые или левые поддеревья, то дерево называется строго бинарным деревом.
В бинарном дереве можно выделить уровни узлов. Уровень узла может быть определён следующим образом: корень – это нулевой узел; уровень любого другого узла на единицу больше уровня своего отца. Глубина бинарного дерева – это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева.
Типы данных, которые представляют бинарные деревья, можно определить следующим образом:
type TED = …;
root = ^tree;
tree = record
elem: TED;
left, right: root;
end;
var t: root;
Дерево называется идеально сбалансированным, если число вершин в правом и левом поддеревьях отличается не более, чем на единицу. Рассмотрим, как построить идеально сбалансированное дерево. Элементами дерева будут являться целые числа, которые поступают из стандартного входного потока. Для построения идеально сбалансированного дерева используется рекурсивный алгоритм. Заключается он в следующем:
1) Взять одну вершину в качестве корня.
2) Построить тем же способом левое поддерево с nl = (n div 2) вершинами.
3) Построить тем же способом правое поддерево с nr = (n – nl – 1) вершинами.
Функция построения идеально сбалансированного дерева с n вершинами.
function maketree(n: integer): root;
var newroot: root;
x, nl, nr: integer;
begin
if n = 0 then newroot := nil else begin
nl := n div 2;
nr := n – nl – 1;
readln(x);
new(newroot);
with newroot^ do begin
elem := x;
left := maketree(nl);
right := maketree(nr);
end;
end;
maketree := newroot;
end;
Пример:
t := maketree(7);
Вводимые числа: 8, 9, 11, 15, 19, 20, 21.
|
_8_
/ \
9 19
/ \ / \
11 15 20 21
Бинарные деревья часто используются для представления множества данных, среди которых идёт поиск элементов по уникальному ключу. Если дерево организовано так, что для каждой вершины ti справедливо утверждение, что все ключи левого поддерева меньше ключа ti, а все ключи правого поддерева больше ключа ti, то такое дерево называется деревом поиска.
Процедура построения дерева поиска.
procedure treesearch(x: TED; var p: root);
begin
if p = nil then begin
new(p);
with p^ do begin
elem := x;
left := nil;
right := nil;
end;
end else
if x < p^.elem then treesearch(x, p^.left) else treesearch(x, p^,right);
end;
Если надо построить дерево из нескольких вершин:
begin
writeln(‘Введите число вершин: ‘);
readln(n);
t := nil;
while n > 0 do begin o
readln(x); /[]\
treesearch(x, t); / \
n := n – 1;
end;
…
Параметр p (указатель на корень) передаётся по ссылке. Это необходимо, чтобы его изменения при выполнении очередного рекурсивного вызова были доступны в предыдущем вызове, иначе связанных ссылок не получим.
Процедура поиска по дереву.
procedure search(x: TED; p: root; var px: root);
{p – указатель на узел дерева, а px – указатель на найденный элемент}
begin
if p = nil then px := nil
else if x < p^.elem then search(x, p^.left, p)
else if x > p^.elem then search(x, p^.right, p);
else px := p;
end;
После окончания процедуры px будет содержать указатель на найденный элемент или nil, если указатель не найден.
Одной из важных операций при работе с деревьями является прохождение дерева, то есть надо просмотреть всё дерево, побывав в каждой вершине один раз.
R – корень дерева, A и B – левое и правое поддеревья.
1 способ – просмотр в прямом порядке (просмотр в глубину, просмотр сверху вниз):
1) Попасть в корень.
2) Пройти в прямом порядке левое поддерево.
3) Пройти в прямом порядке правое поддерево.
2 способ – просмотр в симметричном порядке (просмотр слева направо):
1) Пройти в симметричном порядке левое поддерево.
2) Попасть в корень.
3) Пройти в симметричном порядке правое поддерево.
3 способ – прохождение дерева в обратном порядке (прохождение снизу вверх):
1) Пройти в обратном порядке левое поддерево.
2) Пройти в обратном порядке правое поддерево.
3) Попасть в корень.
Пример:
1) ABDGCEHIF
2) DGBAHEICF
3) GDBHIEFCA
Ответы к дереву из д/з:
1) ABCEIFJDGHKL
2) EICFJBGDKHLA
3) IEJFCGKLHDBA
Рассмотрим три процедуры, реализующие три способа прохождения деревьев. Все они рекурсивные.
procedure preorder(t: root);
begin
if t <> nil then begin
p(t); {некая процедура, выполняющая необходимые действия над узлом}
preorder(t^.left);
preorder(t^.right);
end;
end;
procedure inorder(t: root);
begin
if t <> nil then begin
inorder(t^.left);
p(t);
inorder(t^.right);
end;
end;
procedure postorder(t: root);
begin
if t <> nil then begin
postorder(t^.left);
postorder(t^.right);
p(t);
end;
end;
С помощью построения дерева поиска и его прохода в симметричном порядке можно отсортировать массив. Для этого:
1) Элементы массива располагаются в бинарном дереве поиска.
2) Дерево поиска проходится в симметричном порядке.
Пример: массив 14, 5, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5.
Прохождение: 3, 4, 4, 5, 5, 7, 9, 9, 14, 14, 15, 16, 17, 18, 20.
Ещё одной важной операцией работы с деревьями есть функция исключения (удаления) из дерева. Исключение элемента из дерева – более сложная операция, чем включение в дерево. Просто исключить элемент, если он является листом или узлом с одним потомком. Трудность возникает, если нужно удалить элемент с двумя потомками, поскольку с помощью одной ссылки нельзя указать сразу два направления. В этом случае удаляемый элемент надо заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева, причём они должны иметь не более одного потомка. Рассмотрим процедуру, исключающую элементы из дерева поиска. В качестве параметров процедуре передаётся ключ x (элемент с этим значением надо удалить) и указатель на дерево. В процедуре различаются три случая:
1) элемента с ключом, равным x, нет;
2) элемент с ключом x имеет не более одного потомка;
3) элемент с ключом x имеет двух потомков.
procedure delete(x: TED; var p: root);
var q: root;
procedure del(var r: root);
begin
if r^.right <> nil then del(r^.right) else begin
q^.elem := r^.elem;
q := r;
r := r^.left;
end;
end;
begin
if p = nil then writeln(‘Слова в дереве нет.’) else
if x < p^.elem then delete(x, p^.left) else
if x > p^.elem then delete(x, p^.right) else begin
q := p;
if q^.right = nil then p := q^.left else
if q^.left = nil then p := q^.right else
del(q^.left);
dispose(q);
end;
end;
Вспомогательная рекурсивная функция del начинает работать только в случае 3. Она спускается вдоль правой ветви левого поддерева элемента, который надо исключить (указатель q), и заменяет этот элемент на соответствующее значение из самого правого узла левого поддерева.