Удаление из дерева.
Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной или из нее выходит только одно ребро. Для этого нужно изменить соответствующую ссылку у предшествующей вершины.
Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины.
| |
|
Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая.
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;
Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип удаления элемента из дерева.
Дата добавления: 2015-05-16; просмотров: 1088;