Синтаксис объявления класса TFindTree
template <class T>
class TFindTree
{
private:
TFindTreeNode<T>* Root;
TFindTreeNode<T>* FindNode(T Data, TFindTreeNode<T>* Parent);
public:
TFindTree();
TFindTreeNode<T>* Insert(T Data);
TFindTreeNode<T>* Find(T Data);
void Delete(T Data);
void Clear();
~TFindTree(){};
};
Класс TTree содержит только поле Root для хранения указателя на корень дерева. Конструктор устанавливает корень дерева в NULL. Методы Add, Insert, Delete добавляют, вставляют и удаляют дочерние узлы в списке дочерних узлов родителя переданного узла, а методы AddChild, InsertChild, DeleteChild добавляют, вставляют и удаляют дочерние узлы в список дочерних узлов самого переданного узла. Метод Clear удаляет все узлы из дерева, устанавливая корень дерева в NULL, а деструктор класса не только удаляет все его дочерние узлы, но и освобождает память от самого объекта.
В модуле с данным классом можно определить класс исключительных ситуаций ETreeError для обработки ошибок, которые могут возникать при работе с деревом.
#define ETreeError Exception
Чтобы использовать эти классы, в заголовочном разделе модуля с расширением h необходимо подключить модуль SysUtils.hpp, в котором хранить базовый класс исключительных ситуаций Exception.
После объявления класса TTreeNode необходимо определить все его методы в заголовочном разделе модуля с расширением h в соответствии с ADT – форматом.
1. Конструктор класса
template <class T>
TFindTree<T>::TFindTree()
{
Root = NULL;
}
2. Метод поиска узла в структуре «дерево»
template <class T>
TFindTreeNode<T>* TFindTree<T>::FindNode(T Data, TFindTreeNode<T>* Parent)
{
TFindTreeNode<T>* Node = Root;
Parent = NULL;
while (Node != NULL && Node->FData != Data)
{
Parent=Node;
if (Data<Node->FData)
Node=Node->FLeft;
Else
Node=Node->FRight;
};
return Node;
}
3. Метод поиска узла
template <class T>
TFindTreeNode<T>* TFindTree<T>::Find(T Data)
{
TFindTreeNode<T>* Parent;
return FindNode(Data, Parent);
}
4. Метод вставки узла
template <class T>
TFindTreeNode<T>* TFindTree<T>::Insert(T Data)
{
TFindTreeNode<T> *Node=root;
TFindTreeNode<T> *Parent=NULL,
TFindTreeNode<T> *NewNode=new TFindTreeNode<T>(Data);
while (Node != NULL)
{
Parent=Node;
if (Node->FData > Data)
Node = Node->FLeft;
Else
Node = Node->FRight;
};
if (Parent==NULL)
root=newNode;
else if (Data < Parent->FData)
Parent->FLeft = NewNode;
Else
Parent->Fright = NewNode;
return NewNode;
}
5. Метод удаления узла
template <class T>
void TFindTree<T>::Delete(T Data)
{
TFindTreeNode<T> *DeleteNode, *ParentNode, *ReplaceNode;
ParentNode = NULL;
DeleteNode=FindNode(Data, ParentNode);
if (DeleteNode != NULL)
{
ReplaceNode = NULL;
if (DeleteNode->FRight == NULL)
ReplaceNode = DeleteNode->FLeft;
else if (DeleteNode->FLeft == NULL)
ReplaceNode = DeleteNode->FRight;
else {
TFindTreeNode<T> *PReplaceNode, *Node;
PReplaceNode = DeleteNode;
ReplaceNode = DeleteNode->FLeft;
Node = ReplaceNode->FRight;
while ((Node != NULL))
{
PReplaceNode = ReplaceNode;
ReplaceNode = Node;
Node = Node->FRight;
};
if (PReplaceNode!=DeleteNode)
{
PReplaceNode->Right = ReplaceNode->FLeft;
ReplaceNode = NULL;
};
};
delete DeleteNode;
};
}
6. Метод очистки дерева поиска
template <class T>
void TFindTree<T>::Clear()
{
delete Root;
Root = NULL;
}
7. Деструктор класса дерева поиска
template <class T>
TFindTree<T>::~TFindTree()
{
delete Root;
}
После того, как определен класс TFindTree, его можно использовать в любом месте программы, подключив соответствующие модули с классами TFindTreeNode и TFindTree.
void __fastcall TForm1::Button1Click(TObject *Sender)
{
TFindTree<char> FindTree;
FindTree.Insert('Д');
FindTree.Insert('Е');
FindTree.Insert('Р');
FindTree.Insert('E');
FindTree.Insert('В');
FindTree.Insert('О');
Edit1.Text = FindTree.Find('О').Data();
}
Для вывода узлов дерева или выполнения дополнительных действий с узлами необходимо в класс 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.
Дерево, как стек или очередь, является одной из широко используемых структур данных во всех языках программирования. С ее помощью организуется файловая структура в любой операционной системе. Она применяется для хранения и представления больших объемов информации в иерархическом виде, а пирамидальная сортировка, основанная на деревьях, является одним из самых быстродействующих и устойчивых алгоритмов сортировки данных.