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

Реализация класса дерева бинарного поиска

Реализация класса дерева бинарного поиска

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

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

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

type

TtdBinarySearchTree = class {класс дерева бинарного поиска}

private

FBinTree : TtdBinaryTree;

FCompare : TtdCompareFunc;

FCount : integer;

FName : TtdNameString;

protected

procedure bstError(aErrorCode : integer;

const aMethodName : TtdNameString);

function bstFindItem(aItem : pointer; var aNode : PtdBinTreeNode;

var aChild : TtdChildType): boolean;

function bstFindNodeToDelete(aItem : pointer): PtdBinTreeNode;

function bstInsertPrim(aItem : pointer; var aChildType : TtdChildType): PtdBinTreeNode;

public

constructor Create( aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Clear;

procedure Delete(aItem : pointer); virtual;

function Find(aKeyItem : pointer): pointer; virtual;

procedure Insert(aItem : pointer); virtual;

function Traverse( aMode : TtdTraversalMode;

aAction : TtdVisitProc; aExtraData : pointer;

aUseRecursion : boolean): pointer;

property BinaryTree : TtdBinaryTree read FBinTree;

property Count : integer read FCount;

property Name : TtdNameString read FName write FName;

end;

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

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

Оглавление книги