Представление бинарных деревьев

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отношение старше-младше (левее-правее). Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.

 

Пример

На рис. 9.11 приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев.

Таким образом, достаточно рассмотреть представление в компьютере бинарных деревьев.

 

Замечание

Из данного представления следует, что множество бинарных деревьев взаимнооднозначно соответствует множеству упорядоченных лесов упорядоченных деревьев.

Обозначим через n(p) объем памяти, занимаемой представлением бинарного дерева, где - число узлов. Наиболее часто используются следующие представления бинарных деревьев.

1. Списочные структуры: каждый узел представляется записью типа N, содержащей два поля (t и r) с указателями на левый и правый узлы и еще одно поле r для хранения указателя на информацию об узле. Дерево представляется указателем на корень. Тип N обычно определяется следующим образом:

N = record i: info; l,r: ↑ N end record

Для этого представления n(p) = 3p

 

 

 

 

Рис. 9.11. Упорядоченное и бинарное деревья

Замечание

Поскольку в бинарном дереве, как и в любом другом, q = р - 1, то из 2р указателей, отводимых для хранения дуг, р+1 всегда хранит значение nil, то есть половина связей не используется.

2. Упакованные массивы: все узлы располагаются в массиве, так что все узлы поддерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс узла, который является первым узлом правого поддерева данного узла. Дерево T обычно определяется следующим образом:

T: array [1..р] оf record record i: info; k+1…p end record.

Для этого представления п(р) = 2р.

3. Польская запись: аналогично, но вместо связей фиксируется «размеченная степень» каждого узла (например, 0 означает, что это лист, 1 — есть левая связь, но нет правой, 2 — есть правая связь, но нет левой, 3 — есть обе связи). Дерево T определяется следующим образом: