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

Голова дерева.

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

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

}

}