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

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

Листинг 8.16. Интерфейс дерева бинарного поиска

type TtdBinarySearchTree = class {класс дерева бинарного поиска} private FBinTree : TtdBinaryTree;
FCompare : TtdCompareFunc;
FCount : integer;
FName : TtdNameString;
protected
procedure bstError(aErrorCode : integer;
const aMethodName : TtdNameString) ; function bstFindItem(altem : pointer;
var aNode : PtdBinTreeNode;
var aChild : TtdChildType) : boolean;
function bstFindNodeToDelete (altem : pointer) : PtdBinTreeNode;
function bstlnsertPr im (altem : pointer;
var aChildType : TtdChildType)
: PtdBinTreeNode;
public
constructor Create ( aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
destructor Destroy;
override; procedure Clear;
procedure Delete (altem : pointer); virtual;
function Find(aKeyltern : pointer) : pointer;
virtual; procedure Insert (altem : pointer); virtual;
function Traverse ( aMode : TtdTraversalMode;
aAction : TtdVisitProc;
aExtraData : pointer;
aUseRecursion : boolean) : pointers-property BinaryTree : TtdBinaryTree read FBinTree ; property Count : integer read FCount;
property Name : TtdNameString read FName write FName;
end;

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

Исходный код класса TtdBinarySearchTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.

Удаление из дерева бинарного поиска || Оглавление || Перекомпоновка дерева бинарного поиска


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс