Структуры данных. Деревья - 27 стр.

UptoLike

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

Рубрика:

Упражнение 4.5. Описать нерекурсивную процедуру или функцию под-

счета числа вхождений заданного элемента в дерево поиска.

4.3 Исключение из дерева поиска

Алгоритм исключения из упорядоченного дерева должен описывать три

случая:

1) Узла с заданным значением в дереве нет.

2) Узел с заданным значением имеет не более одного потомка, т.е. удаляе-

мый узел

или терминальная вершина ( лист ), или вершина с одним

потомком.

3) Узел с заданным значением имеет двух потомков.

Трудности возникают в случае 3), так как удаляемый узел нужно заменить

либо на самый правый узел его левого поддерева, либо на самый левый узел его

правого поддерева, причем они должны иметь не более одного потомка.

Пример 4.4. Описать процедуру исключения узла с заданным значением x

из дерева поиска T .

procedure Delete(var T : Tree; x : integer);

var q : Tree;

procedure Del(var p : Tree);

begin

if p^.R <> nil then Del(p^.R)

else

begin

q^.inf:=p^.inf; q:=p;

p:=p^.L

end

end; { Del }