Синтаксис объявления класса tTree

template <class T>

classTTree

{

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);

voidClear();

~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)

throwETreeError("Корень дерева уже существует");

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)

throwETreeError("Корень дерева уже существует");

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)

throwETreeError("Корень дерева уже существует");

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)

throwETreeError("Корень дерева уже существует");

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>

voidTTree<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>

voidDoSomething(T Data)

{

// Выполняемые действия

}

Для обращения пользователя к этим методам в открытом разделе классе TTreeможно определить интерфейсный метод соответствующего прохода.

template<class T>

voidTTree<T>::ForwardScan()

{

Forward(Root,DoSomething);

}

Вместо метода DoSomething, можно использовать любой параметр, передаваемый по ссылке, и возвращать его значение в методеForwardScan.

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