Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Однако непосредственно использовать описанную выше процедуру поиска нельзя, потому что по окончании вычисления ее значения не фиксируется тот узел, из которого была выбрана ссылка NIL.
Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого поиск прекращен (в случае неуспешного поиска). И опишем процедуру включения элемента в дерево, учитывая, что в дереве нет узла с тем же ключом, что и у включаемого элемента.
q=nil
p=tree
WHILE p<>nil DO
q=p
IF key=k (p)
THEN search=p
RETURN
END IF
IF key<k (p)
THEN p=left (p)
ELSE p=right (p)
END IF
END WHILE
{Узел с заданным ключом не найден, требуется вставка элемента. На узел предполагаемого отца указывает q.}
V=maketree (key, rec)
{Нужно выяснить, левым или правым сыном будет вставляемый элемент V.}
IF key<k (q)
THEN left (q)=V
ELSE right (q)=V
END IF
search=V
RETURN

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

Разработаем алгоритм для 3-его случая (вершина-узел имеет 2-х сыновей), вместо удаляемого узла поставим его приемника в симметричном обходе. Предшественником удаляемого узла 12 является самый правый узел левого поддерева — узел 11, а приемником или последователем при симметричном обходе (обход слева направо) является самый левый узел правого поддерева — узел 13.
Будем использовать следующие указатели :
p — рабочий указатель;
q — отстает на один шаг от p;
v — указывает приемника;
t — отстает от v на один шаг;
s — опережает v на один шаг.

1) Процедурой поиска элемента находим удаляемый элемент. Указатель p указывает на удаляемый элемент.
2) Установим указатель v на узел, который будет замещать удаляемый элемент.
IF left (p)=nil
THEN v=right (p)
ELSE IF right (p)=nil
THEN v=left (p)
ELSE t=p
v=right (p)
s=left (v)
WHILE s<>nil
t=v
v=s
s=left (v)
END WHILE
IF t<>p
THEN WRITE (v не является сыном p)
left (t)=right (v)
right (v)=right (p)
END IF
left (v)=left (p)
IF q=nil
THEN WRITE (v корень)
tree=v
RETURN
END IF
IF p=left (q)
THEN left (q)=v
ELSE right (q)=v
END IF
END IF
END IF
FREENODE (p) (процедура создает свободный узел, т.е. очищает ячейку памяти, в которой находится удаленный элемент)
RETURN

Задания

Варианты:
1.Описать процедуру или функцию, которая:

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники