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

В бинарном дереве, содержащем 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;

BYTE L,R;

};

На рис.25 изображено прошитое дерево. Пунктиром изображены нити.

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

NODE *NextUzel(NODE *p){

NODE *q=p->Right;

if(p->R==THREAD) return q; // если это нить, то q-результат

// в противном случае спуститься до упора по левым связям

while(q->L==MAINLINK) q=q->Left;

return q;

}

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

void InverseBypass(NODE *Root){

NODE *q=Root;

// найдем первый в обратном порядке узел

// он находится в конце спуска по основным левым связям

while(q->L==MAINLINK)q=q->Left;

// проходим все узлы, используя функцию NextUzel

for(;q!=NULL;q=NextUzel(q)){

Обработка(q);

}

}