Алгоритм построения идеально сбалансированного дерева
Идея алгоритма: Построим и выведем на экран бинарное дерево минимальной глубины из n узлов, вычислим его глубину. Значениями узлов будут целые числа, вводимые с клавиатуры. Для получения минимальной глубины при заданном числе узлов надо располагать максимально возможное число узлов на всех уровнях, кроме самого последнего. Это достигается распределением всех поступающих узлов поровну слева и справа от каждого узла. Реализует эту идею рекурсивный алгоритм:
1. Взять один узел в качестве корня;
2. Построить левое поддерево с количеством узлов nL = n div 2 тем же способом;
3. Построить правое поддерево с количеством узлов nR = n-nL-1 тем же способом.
В программе этот алгоритм реализован рекурсивной функцией Tree.
program BinTree; {Построение идеально сбалансированного дерева,
вывод его на экран, вычисление глубины дерева}
type ref = ^Node;
Node= record
Inf: integer;
Left,Right: ref
end;
var Root: ref; {Указатель на корень дерева}
H: integer; {Высота дерева}
n: integer; {Количество узлов}
function Tree(n: integer):ref; {Рекурсивная функция построения дерева из n узлов}
var t: ref; x,nL,nR: integer;
begin
If (n=0) then Tree:=nil
else begin
nL:=n div 2; {Половина узлов – в левом поддереве}
nR:=n-nL-1; {Половина узлов минус корень – в правом поддереве}
read(x);
new(t); {Выделение динамической памяти для узла}
t^.Inf:= x; {Итак, на рекурсивном спуске }
t^.Left :=Tree(nL); {Построение левого поддерева}
t^.Right:=Tree(nR); {Построение правого поддерева}
Tree:= t
end
end; { конец функции Tree }
procedure PrintTree (t: ref; h: integer); {Вывод дерева. Обход дерева справа налево.
t – указатель на поддерево; h – уровень узла поддерева, используется для отступа от левого края экрана}
const blank=' '; {пробелы для отступа каждого уровня}
var i : integer;
begin
if (t<>nil) then begin
PrintTree (t^.Right, h+1);
for i:=1 to h do write(blank); {Отступ на уровень h}
writeln(t^.Inf);
PrintTree (t^.Left, h+1) end
end;
function Height(t:ref):integer; {Определение высоты дерева. Обход дерева снизу вверх}
var hL, hR: integer;
begin
if (t=nil) then Height:= -1 {Если дерево пустое, функция выдает значение –1}
else begin
hL:=Height(t^.Left); {Определение высоты левого поддерева}
hR:=Height(t^.Right); {Определение высоты правого поддерева}
if (hL>hR) then Height:=hL + 1
else Height:=hR + 1
end
end; { конец функции Height}
begin {основная программа}
write('n='); readln(n);
Root:= Tree(n);
PrintTree(Root, 0); {Корень дерева печатается на уровне 0, без отступа от края экрана}
H:=Height(Root); writeln('Высота H=', H)
End.
Если ввести n=7 и значения узлов 1, 2, 3, 4, 5, 6, 7, то получим на экране изображение дерева:
| 7 5 6 1 4 2 3 | Уровень узла: h=2 h=1 h=2 h=0 h=2 h=1 h=2 | |
| Высота H=2 |
Способы обхода дерева
Обходом дерева называется последовательное обращение ко всем узлам. Существует четыре принципа упорядоченного обхода дерева, которые вытекают из его структуры. Как и саму древовидную структуру, их удобно выразить с помощью рекурсии.
Для иллюстрации обхода возьмем дерево, построенное для арифметического выражения
a*b + c/d с двухместными операциями. Замечание: для произвольного дерева обходы будут выполняться точно так же, но будут иметь другую интерпретацию.
|
В этом дереве каждая операция изображается узлом
с операндами в качестве поддеревьев.
Обозначим через Root корень дерева, а через L и R – левое и правое поддеревья.
Различные принципы обхода дают различные формы записи выражения.
1) Прямой обход, или обход сверху вниз (Root, L, R – посетить корень, затем левое и правое поддерево)
дает префиксную форму записи выражения, когда знак операции находится перед операндами:
+*ab/cd
2) Обратный обход, или обходснизу вверх (L, R, Root – посетить левое и правое поддерево, затем корень)
дает постфиксную форму записи выражения, когда знак операции находится после операндов:
ab*cd/+
Постфиксная нотация – форма записи математических выражений, в которой операнды расположены перед операторами.
3) Синтаксический обход, или обходслева направо (L, Root, R – посетить левое поддерево, затем корень и правое поддерево)
дает привычную инфиксную форму записи выражения, когда знак операции находится между операндами, к которым эта операция применяется: a*b + c/d
4) Обход справа налево (R, Root, L – посетить правое поддерево, затем корень и левое поддерево) используется для печати дерева.
Опишем обходы в виде рекурсивных процедур с параметром t, означающим ссылку на узел дерева, в частности, корень дерева. Ссылка t передается по значению, так как никаких изменений структуры дерева не происходит. Процедуры обхода вызывают некоторую процедуру OP для выполнения действий в каждом узле, например, печать узла, проверка узла на максимум и т.п.
Способы обхода дерева отличаются:
· порядком просмотра поддеревьев (левое, затем правое или правое, затем левое);
· выполнением операции над текущим узлом (на рекурсивном спуске или на рекурсивном возврате).
| procedure Prefix (t: ref); {Обход сверху вниз Root, L, R} begin {дает префиксную запись выражения} if (t<>nil) then begin OP(t); {Выполняется в текущем узле на рекурсивном спуске} Prefix(t^.Left); {Переход в левое поддерево} Prefix(t^.Right) {Переход в правое поддерево} end end; | procedure Postfix(t: ref); {Обход снизу вверх L, R Root} begin {дает постфиксную запись выражения} if (t<>nil) then begin Postfix(t^.Left);{Переход в левое поддерево} Postfix(t^.Right);{Переход в правое поддерево} OP(t) {Выполняется в текущем узле на рекурсивном возврате} end end; | |
| procedure Infix(t: ref); {Обход слева направо L, Root< R} begin {дает инфиксную, обычную запись} if (t<>nil) then begin Infix(t^.Left);{Переход в левое поддерево} OP(t); {Выполняется в текущем узле на рекурсивном возврате из левого поддерева перед рекурсивным спуском в правое поддерево} Infix(t^.Right) {Переход в правое поддерево} end end; | ||
Деревья поиска
Двоичные деревья часто используются для представления наборов данных, элементы которого ищутся по уникальному, только им присущему ключу.
Деревом поиска называется такое бинарное дерево, в котором для ключа каждого узла все ключи его левого поддерева меньше ключа узла, а все ключи его правого поддерева больше ключа узла.
| Деревья поиска можно использовать для сортировки. Например, для сортировки массива надо построить дерево поиска по значениям элементов массива, а затем обойти дерево слева направо (синтаксический обход), записывая значения узлов дерева в результирующий массив. Скорость поиска в деревьях поиска примерно такая же, что и в отсортированных массивах: O(C×log2n), в худшем случае O(n). | 
|
Построение дерева поиска
При построении дерева поиска и при последующем поиске узла по его ключу место каждого ключа можно найти, двигаясь, начиная от корня, и переходя на левое или правое поддерево каждого узла в зависимости от значения ключа.
Начиная с пустого дерева, очередное число ищется в дереве:
- Если число найдено, увеличивается его счетчик появления.
- Если нет, число вставляется в дерево с начальным значением счетчика=1.
Поскольку определение двоичного дерева рекурсивно, то все операции над деревом могут быть реализованы в виде рекурсивных подпрограмм. Замечание: использование рекурсии замедляет работу программы и расходует лишнюю память при её выполнении.
program TreeSearch; {Дерево поиска}
type ref=^node;
node=record
key:integer;
count:integer;
left,right:ref
end;
var Root:ref; k:integer;
procedure Gen(x:integer; var t:ref);{Генерация нового узла}
begin
new(t);
t^.key:=x; t^.count:=1;
t^.left:=nil; t^.right:=nil
end;
procedure Search (x:integer; var t:ref);{Поиск х в дереве t}
begin
if t=nil
then Gen(x,t) {Добавление узла в дерево, т.к. числа x в дереве нет}
else if (x = t^.key)
then t^.count:=t^.count+1 {Число x есть в дереве}
else if (x < t^.key)
then Search(x, t^.left) {Поиск в левом поддереве}
else Search(x, t^.right) {Поиск в правом поддереве}
end;
procedure PrintTree(t:ref; h:integer);{Вывод дерева. Обход дерева справа налево}
var i:integer;
begin
if t<>nil then
begin
PrintTree(t^.right,h+1);
for i:=1 to h do write(' ');
writeln(t^.key, ’_', t^.count);
PrintTree(t^.left, h+1);
end
end;
procedure Infix(t: ref);{Обход дерева слева направо. Дает вывод в отсортированном порядке}
begin
if (t<>nil)
then begin
Infix(t^.Left); {Переход в левое поддерево}
write(t^.key:3);
Infix(t^.Right) {Переход в правое поддерево}
end
end;
Begin
Root:=nil; {Создание пустого дерева}
write('='); readln(k);
while (k<>0) do {При k=0 построение дерева завершается}
begin
Search(k, Root);
write('='); readln(k);
end;
PrintTree(Root,0);{Вывод дерева}
Infix(Root); {Вывод листьев дерева в отсортированном порядке}
End.