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

В бинарном дереве, содержащем N узлов, на каждый узел, кроме корня указывает ровно одна связь. Всего связей 2*N; непустых - N-1, следовательно, N+1 связь пуста. Пустые связи существуют только для того, чтобы обозначить, что дальше в этом направлении пути нет, для чего достаточно одного бита. Возникает вопрос: а нельзя ли более рационально использовать пространство, занимаемое пустыми связями. Прошитые деревья используют место, занимаемое пустыми связями для хранения указателей, упрощающих прохождение дерева. Эти дополнительные связи называют нитями, откуда и появился термин прошитые. Введем обозначения:

- *P – предшественник узла P в обратном порядке,

- P* - последователь узла P в обратном порядке,

- ⁺P – предшественник в прямом порядке,

- P^{+ -} последователь в прямом порядке.

Дерево может быть прошито для обхода в одном из порядков. Сопоставим обычное дерево и дерево, прошитое для обхода в обратном порядке. Вместо пустых левых связей будем хранить указатель на предшественника в обратном порядке, вместо пустых правых связей – указатель на последователя. Эти связи будем называть "нитями" в отличие от основных связей, которые такие же, как в обычном дереве. Для того, чтобы отличать основные связи от нитей, в каждом узле заведем два поля L и R, которые будут иметь значения THREAD, если связь – нить и MAINLINK, если связь – основная (THREADи MAINLINK –константы). Таким образом, структура узла прошитого дерева имеет вид:

const int THREAD=0;

const int MAINLINK=1;

struct NODE{

<поля данных>;

NODE *Left, *Right;