Представление бинарных деревьевВсякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отношение старше-младше (левее-правее). Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.
Пример На рис. 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 определяется следующим образом:
|
