Прошитые деревья

Представление бинарных деревьев в связной памяти.

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

LP RP Data L_Son R_Son

Если мы воспользуемся прошитым бинарным деревом, то вид узла для него будет таким:

Симметричным прохождением бинарного дерева является такое прохождение, когда мы проходим сначала левое поддерево, затем посещаем корень и последним посещаем правое поддерево: A R B.

Один из возможных способов прошивки бинарного дерева заключается в том, что для каждого узла, не имеющего левого поддерева, запоминается ссылка на непосредственного предшественника, а для каждого узла, не имеющего правого поддерева,запоминается ссылка на его непосредственного преемника. Предшественников и преемников для узла определяют исходя из списка, который получается при прохождении рассматриваемого бинарного дерева в симметричном порядке. Для того, чтобы отличать ссылку на левого или правого сына (такие ссылки называют структурными связями) от ссылки на предшественника или преемника узла (такие ссылки называют “нитями”), используются индикаторные поля LP и RP.

В памяти это дерево будет выглядеть так:

Пример. Рассмотрим бинарное дерево:

Использование “прошивок” существенно убыстряет прохождение дерева, позволяет не использовать стек, но при этом усложняются алгоритмы включения / исключения узла, т.к. в прошитом дереве необходимо управлять не только структурными связями, но и “нитями”.

Дата добавления: 2014-01-07