Двоичные деревья

Спецификация двоичных деревьев

Как уже говорилось выше, двоичные (бинарные) деревья – это деревья со степенью не более двух.

По степени вершин двоичные деревья бывают:

1) Строгие – вершины дерева имеют степень ноль (листья) или два (узлы);

2) Нестрогие – вершины дерева имеют степень ноль (листья), один или два (узлы).

В общем случае на k -м уровне двоичного дерева может быть до 2 ^{k -1} вершин.

Двоичное дерево, содержащее только полностью заполненные уровни (то есть 2 ^{k -1} вершин на каждом k -м уровне), называется полным.

Рисунок 3.11 – Двоичные деревья

Реализация

Двоичное дерево можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде списка.

Списочное представление двоичных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков. При таком способе представления дерева обязательно следует сохранять указатель на узел, являющийся корнем дерева.

type

PTree = ^TTree;

TTree = record

Data: TypeElement; {поле данных}

Left, Right: PTree; {указатели на левого и правого потомков}

end;

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

type

Tree: array[1..N] of TypeElement

Адрес любой вершины в массиве вычисляется как:

адрес = 2^k-1+i-1,

где k – номер уровня вершины, i – номер на уровне k в полном двоичном дереве. Адрес корня будет равен единице. Для любой вершины, имеющей индекс j в массиве, можно вычислить адреса левого и правого потомков

адрес_левого = 2*j

адрес_правого = 2*j+1

Рисунок 3.12 – Организация двоичного дерева

Рисунок 3.13 – Вариант визуального представления динамической организации двоичного дерева

Главным недостатком статического способа представления двоичного дерева является то, что массив имеет фиксированную длину. Размер массива выбирается исходя из максимально возможного количества уровней двоичного дерева, и чем менее полным является дерево, тем менее рационально используется память. Кроме того, недостатком являются большие накладные расходы при изменении структуры дерева (например, при обмене местами двух поддеревьев).

Обходы двоичных деревьев

Далее будет рассмотрена операция прямого обхода двоичного дерева в рекурсивной и нерекурсивной форме. Реализации обратного и симметричного обхода аналогична.

procedure PreOrder_BinTree(Node: PTree);

{Рекурсивный обход двоичного дерева в прямом порядке}

begin

writeln(Node^.Data);

if Node^.Left <> nil then PreOrder_BinTree(Node^.Left);

if Node^.Right <> nil then PreOrder_BinTree(Node^.Right);

end;

Листинг 3.22 – Обход двоичного дерева в прямом порядке на языке Pascal

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

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

procedure NR_PreOrder_BinTree(Tree: PTree);

{Нерекурсивный обход двоичного дерева в прямом порядке}

var

Node: Ptree; {Указатель на текущую вершину}

S: ^TypeElement; {Стек указателей вершин}

begin

{Инициализация}

ClearStack(S);

Node:= Tree;

while true do

if Node <> nil then begin

writeln(Node^.Data);

PushStack(Node, S);

{Исследование левого потомка вершины Node}

Node:= Node^.Left;

end else begin

{Завершена исследование пути, содержащегося в стеке}

if EmptyStack(S) then return;

{Исследование правого потомка вершины Node}

PopStack(Node, S);

Node:= Node^.Right;

end;

end;

Листинг 3.23 – Нерекурсивный обход двоичного дерева в прямом порядке