template < class T>
class TTree
{
private:
TTreeNode<T>* Root;
public:
TTree();
TTreeNode<T>* Add(TTreeNode<T>* Node, T Data);
TTreeNode<T>* Insert(TTreeNode<T>* Node, int Index,
T Data);
void Delete(TTreeNode<T>* Node, int Index);
TTreeNode<T>* AddChild(TTreeNode<T>* Node, T Data);
TTreeNode<T>* InsertChild(TTreeNode<T>* Node, int Index,
T Data);
void DeleteChild(TTreeNode<T>* Node, int Index);
void Clear();
~TTree();
};
Класс TTree содержит только поле Root для хранения указателя на корень дерева. Конструктор устанавливает корень дерева в NULL. Методы Add, Insert, Delete добавляют, вставляют и удаляют дочерние узлы в списке дочерних узлов родителя переданного узла, а методы AddChild, InsertChild, DeleteChild добавляют, вставляют и удаляют дочерние узлы в список дочерних узлов самого переданного узла. Метод Clear удаляет все узлы из дерева, устанавливая корень дерева в NULL, а деструктор класса не только удаляет все его дочерние узлы, но и освобождает память от самого объекта.
В модуле с данным классом можно определить класс исключительных ситуаций ETreeError для обработки ошибок, которые могут возникать при работе с деревом.
#define ETreeError Exception
Чтобы использовать эти классы, в заголовочном разделе модуля с расширением h необходимо подключить модуль SysUtils.hpp, в котором хранить базовый класс исключительных ситуаций Exception.
После объявления класса TTreeNode необходимо определить все его методы в заголовочном разделе модуля с расширением h в соответствии с ADT – форматом.
template < class T>
TTree<T>::TTree()
{
Root = NULL;
}
template < class T>
TTreeNode<T>* TTree<T>::Add(TTreeNode<T>* Node, T Data)
{
if (Node == NULL)
{
if (Root!= NULL)
throw ETreeError("Корень дерева уже существует");
return Root = new TTreeNode<T>(NULL, Data);
}
Else
return Node->FParent->AddChild(Data);
}
template < class T>
TTreeNode<T>* TTree<T>::Insert(TTreeNode<T>* Node,
int Index, T Data)
{
if (Node == NULL)
{
if (Root!= NULL)
throw ETreeError("Корень дерева уже существует");
return Root = new TTreeNode<T>(NULL, Data);
}
Else
{
if (Node == Root)
throw ETreeError("У кореня дерева братьев не бывает");
Return
Node->FParent->InsertChild(Index, Data);
}
}
template <class T>
void TTree<T>::Delete(TTreeNode<T>* Node, int Index)
{
if (Node == NULL)
throw ETreeError("Узел уже удален");
if (Node==Root)
{
delete Root;
Root = NULL;
}
Else
Node->FParent->DeleteChild(Index);
}
template <class T>
TTreeNode<T>* TTree<T>::AddChild(TTreeNode<T>* Node, T Data)
{
if (Node == NULL)
{
if (Root!= NULL)
throw ETreeError("Корень дерева уже существует");
return Root = new TTreeNode<T>(NULL, Data);
}
Else
return Node->AddChild(Data);
}
template < class T>
TTreeNode<T>* TTree<T>::InsertChild(TTreeNode<T>* Node, int Index, T Data)
{
if (Node == NULL)
{
if (Root!= NULL)
throw ETreeError("Корень дерева уже существует");
return Root = new TTreeNode<T>(NULL, Data);
}
Else
return Node->InsertChild(Index, Data);
}
template < class T>
void TTree<T>::DeleteChild(TTreeNode<T>* Node, int Index)
{
if (Node == NULL)
throw ETreeError("Узел уже удален");
Node->DeleteChild(Index);
}
template < class T>
void TTree<T>::DeleteChild(TTreeNode<T>* Node, int Index)
{
if (Node == NULL)
throw ETreeError("Узел уже удален");
Node->DeleteChild(Index);
}
template < class T>
void TTree<T>::Clear()
{
delete Root;
Root = NULL;
}
template < class T>
TTree<T>::~TTree()
{
delete Root;
}
После того, как определен класс TTree, его можно использовать в любом месте программы, подключив соответствующие модули с классами TTreeNode и TTree, следующим образом:
void __fastcall TForm1::Button1Click(TObject *Sender)
{
TTreeNode<char> *a, *b;
TTree<char> Tree;
a = Tree.Add(NULL, 'T');
b = Tree.AddChild(a,'R');
Tree.AddChild(a, 'E');
Tree.AddChild(b, 'E');
}
Для вывода узлов дерева или выполнения дополнительных действий с узлами необходимо в класс 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.
Дерево, как стек или очередь, является одной из широко используемых структур данных во всех языках программирования. С ее помощью организуется файловая структура в любой операционной системе. Она применяется для хранения и представления больших объемов информации в иерархическом виде, а пирамидальная сортировка, основанная на деревьях, является одним из самых быстродействующих и устойчивых алгоритмов сортировки данных.