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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

44
Далее рассмотрим алоритм получения копии бинарного дерева на
новом месте памяти.
Алгоритм С. (Копирование бинарного дерева.)
Пусть HEAD – адрес головы списка бинарного дерева Т (т.е. Т явля-
ется левым поддеревом узла по адресу HEAD; LLINK(HEAD) − указатель
на дерево). Пусть NODE(U) – узел (не дерева T) с пустым левым поддере-
вом. Рассматриваемый алгоритм копирует дерево Т, и копия становится
левым поддеревом узла NODE(U). В частности, если NODE(U) является
головой списка пустого бинарного дерева, то алгоритм превращает пус-
тое дерево в копию дерева Т.
С1. [Начальная установка.]
P ← HEAD, Q ← U. Перейти к шагу С4.
С2. [Поместить справа ?]
Если узел NODE(P) имеет непустое правое поддерево, то R ⇐ AVAIL
и присоединить узел NODE(R) справа от узла NODE(Q). (В начале ша-
га С2 правое поддерево узла NODE(Q) пусто.)
С3. [Скопировать INFO.]
INFO(Q) ← INFO(P). (Здесь INFO обозначает информацию из всех
полей узла, кроме информации из полей LLINK, RLINK, LTAG, RTAG.)
C4. [Поместить слева?]
Если узел NODE(P) имеет непустое левое поддерево, то R ⇐ AVAIL
и присоединить узел NODE(R) слева от узла NODE(Q). (В начале ша-
га С4 левое поддерево узла NODE(Q) пусто.)
С5. [Вперёд.]
P ← P*, Q ← Q*.
C6. [Конец?]
Если P = HEAD (или, что то же самое, если Q = RLINK(U), в предпо-
ложении, что узел NODE(U) имеет непустое правое поддерево), работа
алгоритма заканчивается; в противном случае вернуться к шагу С2. ■
Заметим, что этот алгоритм служит типичным примером примене-
ния процедуры прохождения деревьев. В данном случае он применим к
прошитым, непрошитым и частично прошитым деревьям. Для прошитых
деревьев включение узлов на шагах С2 и С4 осуществляется с помощью
алгоритмов I и I ’. Определение прямых преемников P* и Q* на шаге С5
в прошитом дереве может выполнить описанный ниже алгоритм, кото-
рый для заданного значения Р присваивает переменной Q значение Р*.
Если LTAG(P) = ”+”, то Q ← LLINK(P) и конец алгоритма; в против-
ном случае Q ← P и выполнять Q ← RLINK(Q) до тех пор, пока не полу-
чим RTAG(Q) = ”+” (может быть и ни разу), Q ← RLINK(Q). ■

Страницы