Удаление из дерева.

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

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

Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая.

1. Удаляемая вершина имеет два поддерева. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка.

2. Удаляемая вершина имеет не более одного поддерева (0 или 1).

3. Удаляемой вершины в дереве нет.

Просмотрите рекурсивную процедуру DelTree, которая отыскивает элемент с заданным ключом и удаляет его. В процедуре DelTree описана процедура d1, которая работает только в первом из трех перечисленных случаев.

Вспомогательная процедура d1 "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.

Type

Pt = ^Node;

Node = Record

Data : integer;

Left, Right : Pt;

End;

Procedure DelTree(x : integer; Var p : Pt);

Var

q : Pt;

Procedure D1(Var r : Pt);

Begin

if r^.Right <> Nil

then

d1(r^.Right)

else

begin

q^.Data := r^.Data;

q := r;

r := r^.Left;

Dispose(q);

end;

End;

Begin

if p=nil

then

writeln('Элемента с ключом ', x, 'в дереве нет.')

else

if x<p^.Data

then

DelTree(x, p^.Left)

else

if x>p^.Data

then

DelTree(x, p^.Right)

else

begin

q := p;

if q^.Right = Nil

then

begin

p := q^.Left;

dispose(q);

end;

else

if q^.Left = Nil

then

begin

p := q^.Right;

dispose(q);

end;

else

D1(q^.Left)

end;

End;

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип удаления элемента из дерева.