Реализация

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

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

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 – Вариант визуального представления динамической организации двоичного дерева

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