Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




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

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

 

 

 

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

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;

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






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных