Синтаксис объявления класса TBinTree
template <class T>
class TBinTree
{
private:
TBinTreeNode<T>* Root;
public:
TBinTree();
TBinTreeNode<T>* AddLeftChild(T Data, TBinTreeNode<T>* Node);
TBinTreeNode<T>* AddRightChild(T Data, TBinTreeNode<T>* Node);
void Delete(TBinTreeNode<T>* Node);
void Clear();
~TBinTree();
};
Класс TTree содержит только поле Root для хранения указателя на корень дерева. Конструктор устанавливает корень дерева в NULL. Методы Add, Insert, Delete добавляют, вставляют и удаляют дочерние узлы в списке дочерних узлов родителя переданного узла, а методы AddChild, InsertChild, DeleteChild добавляют, вставляют и удаляют дочерние узлы в список дочерних узлов самого переданного узла. Метод Clear удаляет все узлы из дерева, устанавливая корень дерева в NULL, а деструктор класса не только удаляет все его дочерние узлы, но и освобождает память от самого объекта.
В модуле с данным классом можно определить класс исключительных ситуаций ETreeError для обработки ошибок, которые могут возникать при работе с деревом.
#define EBinTreeError Exception
Чтобы использовать эти классы, в заголовочном разделе модуля с расширением h необходимо подключить модуль SysUtils.hpp, в котором хранить базовый класс исключительных ситуаций Exception.
После объявления класса TTreeNode необходимо определить все его методы в заголовочном разделе модуля с расширением h в соответствии с ADT – форматом.
template <class T>
TBinTree<T>::TBinTree()
{
Root = NULL;
}
template <class T>
TBinTreeNode<T>* TBinTree<T>::AddLeftChild(T Data, TBinTreeNode<T>* Node)
{
if (Node == NULL)
{
if (Root != NULL)
throw EBinTreeError("Корень дерева уже существует");
Root = new TBinTreeNode<T>(Data, NULL);
return Root;
}
else{
Node->SetLeftNode(new TBinTreeNode<T>(Data, Node));
returnNode->FLeft;
}
}
template <class T>
TBinTreeNode<T>* TBinTree<T>::AddRightChild(T Data, TBinTreeNode<T>* Node)
{
if (Node == NULL)
{
if (Root != NULL)
throw EBinTreeError("Корень дерева уже существует");
Root = new TBinTreeNode<T>(Data, NULL);
return Root;
}
else{
Node->SetRightNode(new TBinTreeNode<T>(Data, Node));
returnNode->FRight;
}
}
template <class T>
void TBinTree<T>::Delete(TBinTreeNode<T>* Node)
{
if (Node == NULL)
throw EBinTreeError("Узел уже удален");
if (Node==Root)
{
delete Root;
Root = NULL;
}
else {
if (Node->Parent()->FLeft == Node)
Node->Parent()->SetLeftNode(NULL);
Else
Node->Parent()->SetRightNode(NULL);
}
}
template <class T>
void TBinTree<T>::Clear()
{
if (Root!=NULL)
{
delete Root;
Root = NULL;
}
}
template <class T>
TBinTree<T>::~TBinTree()
{
if (Root!=NULL) delete Root;
}
После того, как определен класс TBinTree, его можно использовать в любом месте программы, подключив соответствующие модули с классами TTreeNode и TTree.
void __fastcall TForm1::Button1Click(TObject *Sender)
{
TBinTreeNode<char> *a, *b;
TBinTree<char> BinTree;
a = BinTree.AddLeftChild('T', NULL);
b = BinTree.AddLeftChild('R', a);
BinTree.AddRightChild('E', a);
BinTree.AddLeftChild('E', b);
}
Для вывода узлов дерева или выполнения дополнительных действий с узлами необходимо в класс TTree добавить методы прохода деревьев. Например, рекурсивный способ прямого прохода дерева можно организовать следующим образом:
template <class T>
void TTree<T>::Forward(TTreeNode<T>* Node, void DoSomething(T Data))
{
DoSomething(Node->FData);
for (int i = 0; i < Node->FCount; i++)
Forward(Node->Items[i], DoSomething);
}
Метод DoSomething предназначен для выполнения каких-либо действий с данными очередного узла. Этот метод, первоначально, необходимо определить в зависимости от того, какие действия он должен выполнять.
template <class T>
void DoSomething(T Data)
{
// Выполняемые действия
}
Для обращения пользователя к этим методам в открытом разделе классе TTree можно определить интерфейсный метод соответствующего прохода.
template <class T>
void TTree<T>::ForwardScan()
{
Forward(Root, DoSomething);
}
Вместо метода DoSomething, можно использовать любой параметр, передаваемый по ссылке, и возвращать его значение в методе ForwardScan.
Дерево, как стек или очередь, является одной из широко используемых структур данных во всех языках программирования. С ее помощью организуется файловая структура в любой операционной системе. Она применяется для хранения и представления больших объемов информации в иерархическом виде, а пирамидальная сортировка, основанная на деревьях, является одним из самых быстродействующих и устойчивых алгоритмов сортировки данных.