Основы программирования. Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы - 41 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

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

Рубрика: 

43
else if r.left=nil then // случай б)
begin
v:=r;
r:=r.right;
Dispose(v);
end
else if r.right=nil then // случай б)
begin
v:=r;
r:=r.left;
Dispose(v);
end
else FindAndDelMostRight(r.left); // случай в)
end;
Случай в) реализуется здесь локальной процедурой
FindAndDelMostRight(p), удаляющей в дереве с корнем p самый правый
элемент. Вначале эта процедура рекурсивно ищет такой элемент, опускаясь
впра-
во по ветвям дерева. Если движение вправо уже невозможно, значит, мы нашли
самый правый элемент и p является ячейкой, хранящей его адрес (она выделена
черным прямоугольником на последнем рисунке). Теперь достаточно присвоить
значение найденного элемента корневому, изменить указатель p на левое подде-
рево удаляемого элемента и удалить элемент, на который
указывает p.
4.3 Класс «Множество» на базе бинарного дерева поиска
Основные операции при работе с множеством – это добавление, удаление
элемента и проверка элемента на принадлежность к множеству. Используем деле-
гирование, реализовав множество с помощью бинарного дерева поиска, соответ-
ствующие операции для которого мы рассмотрели в предыдущем пункте.
Пусть операции с БДП целых описаны в модуле IntBST. Тогда реализация
класса множества DataSet
в модуле IntSet имеет вид:
unit IntSet;
interface
uses IntBST;
type
DataSet = class
private
root: PNode;
public
constructor Create;
destructor Destroy;
procedure Include(x: DataType); // добавить x

Страницы