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

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

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

:

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

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

	При его симметричном прохождении получаем следующий список вершин: c, b, a, d, g, e, f.

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