Методы программирования. Громов Ю.Ю - 41 стр.

UptoLike

Составители:

Рубрика:

ломаные линии обозначают обычные связи или связи-нити, ведущие к

другим узлам дерева.

Рис. 17. Схемы проведения левых связей-нитей

Рис. 18. Схемы проведения правых связей-нитей

Таким образом, каждая связь-нить указывает непосредственно на

предшественника или на преемника данного узла в дереве при обратном

(симметричном) порядке прохождения.

Большое преимущество прошитых деревьев состоит в том, что уп-

рощаются алгоритмы их прохождения. Рассмотрим алгоритм, который

определяет Р$ при заданном Р.

Алгоритм S. (Обратный (симметричный) преемник в прошитом

бинарном дереве.)

Если Р указывает на узел бинарного дерева, то этот алгоритм пере-

менной Q присваивает значение Р$.

S1. [RLINK(P) − нить?] Q ← RLINK(P). Если RTAG(P) = ”−”, то за-

кончить алгоритм.