Коды классов, функций и обработчиков событий

Сохраните модуль главной формы под именем LR_8, а проект – под именем PR_LR_8.

Для размещения классов в проекте использованы модули, не связанные с формой. Класс для узла дерева объявлен и определен в файле f_8_1, а класс для бинарного дерева – в модуле f_8_2. Ниже приведены заголовочные файлы и файлы реализации этих модулей.

Заголовочный файлf_8_1.h модуля f_8_1 (без формы)

//---------------------------------------------------------------------------

#ifndef f_8_1H

#define f_8_1H

#include <iostream.h> // для константы NULL

//---------------------------------------------------------------------------

//BinSTree зависит от TreeNode

class BinSTree;

// объявление класса для узла бинарного дерева

class TreeNode

{

// сделать класс BinSTree дружественным,

// поскольку функциям-элементам класса BinSTree

// необходим доступ к полям left и right класса TreeNode

friend class BinSTree;

public:

// открытый элемент

int data;

// конструктор

TreeNode(const int& item, TreeNode *lptr=NULL,

TreeNode *rptr=NULL);

// функции-элементы доступа к полям указателей

TreeNode* Left() const{return left;}

TreeNode* Right() const{return right;}

private:

// указатели левого и правого дочерних узлов

TreeNode *left;

TreeNode *right;

};

#endif

Файл реализацииf_8_1.cpp модуля f_8_1 (без формы)

//---------------------------------------------------------------------------

#pragma hdrstop

#include "f_8_1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

// конструктор инициализирует поля данных и указателей

// значение NULL соответствует пустому поддереву

TreeNode::TreeNode(const int& item, TreeNode *lptr,

TreeNode *rptr):data(item), left(lptr), right(rptr)

{}

Заголовочный файлf_8_2.h модуля f_8_2 (без формы)

//---------------------------------------------------------------------------

#ifndef f_8_2H

#define f_8_2H

#include "f_8_1.h"

//------------------------------------------------------------------------

// класс - бинарное дерево

class BinSTree

{

public:

// конструкторы и деструктор

BinSTree();

BinSTree(const BinSTree& tree);

~BinSTree();

// оператор присваивания

BinSTree& operator=(const BinSTree& rhs);

// функции-элементы обработки данных

int Find(int& item); // есть или нет узла с item

void Insert(const int& item); // вставить узел с item

void Delete(const int& item); // удалить узел с item

void ClearTree(); // уничтожить дерево

TreeNode *CopyTree(TreeNode *t); // копировать дерево

int Depth(TreeNode *t); // получить глубину дерева

// получить количество листьев в дереве

void CountLeaf(TreeNode *t,int& count);

// получить корень дерева

TreeNode *GetRoot() const {return root;}

// получить количество узлов в дереве

int GetSize() const {return size;}

private:

// указатель на корень

TreeNode *root;

// количество узлов в дереве

int size;

// выделить память под узел дерева

TreeNode *GetTreeNode(const int& item,

TreeNode *lptr, TreeNode *rptr);

// удалить все узлы дерева

void DeleteTree(TreeNode* t);

// получить указатели - на узел с item и его родителя

TreeNode *FindNode(const int& item,

TreeNode* &parent)const;

};

#endif

Файл реализацииf_8_2.cpp модуля f_8_2 (без формы)

//---------------------------------------------------------------------------

#pragma hdrstop

#include <iostream.h> // для константы NULL

#include "f_8_2.h"

#include "LR_8.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

//---------------------------------------------------------------------------

// конструктор

BinSTree::BinSTree()

{

root=NULL;

size=0;

}

//---------------------------------------------------------------------------

// конструктор копирования

BinSTree::BinSTree(const BinSTree& tree)

{

// скопировать дерево в создаваемое дерево

root=CopyTree(tree.root);

// скопировать размер дерева

size=tree.size;

}

//---------------------------------------------------------------------------

// деструктор

BinSTree::~BinSTree()

{

ClearTree();

size=0;

}

//---------------------------------------------------------------------------

// оператор присваивания

BinSTree& BinSTree::operator = (const BinSTree& rhs)

{

// нельзя копировать дерево в самоё себя

if(this == &rhs)

return *this;

// очистить текущее дерево, скопировать новое дерево в текущий

// объект

ClearTree();

root=CopyTree(rhs.root);

// задать размер дерева

size=rhs.size;

// возвратить ссылку на текущий объект

return *this;

}

//----------------------------------------------------------------------

// искать элемент данных на дереве; если найден, возвратить адрес

// совпавшего узла и указатель на его предка; иначе возвратить NULL

TreeNode *BinSTree::FindNode(const int& item,

TreeNode* &parent) const

{

// пробежать по узлам дерева, начиная с корня

TreeNode *t=root;

// у корня нет родителя

parent=NULL;

// прерваться на пустом поддереве

while (t!=NULL)

{

// остановиться по совпадению

if(item==t->data)

break;

else

{

//обновить родительский указатель и идти налево или направо

parent=t;

if(item<t->data)

t=t->left;

else

t=t->right;

}

}

// возвратить указатель на узел; NULL, если не найден

return t;

}

//----------------------------------------------------------------------

// искать item. если найден, присвоить данные узла параметру item

int BinSTree::Find(int& item)

{

// используем FindNode, который принимает параметр parent

TreeNode *parent, *current;

// искать item, назначить совпавший узел текущим

current = FindNode(item,parent);

// если найден, присвоить данные узла и возвратить true

if(current!=NULL)

{

item=current->data;

return 1;

}

else

// item не найден, возвратить false

return 0;

}

//--------------------------------------------------------------------------

// создать объект TreeNode с указательными полями lptr и rptr.

// по умолчанию указатели содержат NULL.

TreeNode *BinSTree::GetTreeNode(const int& item,

TreeNode *lptr, TreeNode *rptr)

{

TreeNode *p;

// вызвать new для создания нового узла.

// передать туда параметры lptr и rptr.

p=new TreeNode (item, lptr, rptr);

// если памяти недостаточно, завершить программу

// сообщением об ошибке

if(p==NULL)

{

MessageBox(NULL,"Недостаточно памяти!","Ошибка",0);

return NULL;

}

// вернуть указатель на выделенную память

return p;

}

//----------------------------------------------------------------------

// вставить item в дерево

void BinSTree::Insert(const int& item)

{

// t - текущий узел, parent - предыдущий узел

// newNode - новый узел

TreeNode *t=root, *parent=NULL, *newNode;

newNode = GetTreeNode(item, NULL, NULL);

// закончить на пустом поддереве

while (t!=NULL)

{

// если item равно данному в текущем узле, не вставлять

if(item==t->data) return;

// обновить указатель parent и идти налево или направо

parent=t;

if(item<t->data)

t=t->left;

else

t=t->right;

}

// если родителя нет, вставить в качестве корневого узла

if(parent==NULL)

root=newNode;

// если item меньше данного в родительском узле,

// вставить в качестве левого сына

else if(item<parent->data)

parent->left=newNode;

else

// если item больше данному в родительском узле,

// вставить в качестве правого сына

parent->right=newNode;

// увеличить size на единицу

size++;

}

//------------------------------------------------------------------------

// если элемент находится на дереве, удалить его

void BinSTree::Delete(const int& item)

{

// DNodePtr - указатель на удаляемый узел D

// PNodePtr - указатель на родительский узел P узла D

// RNodePtr - указатель на узел R, замещающий узел D

TreeNode *DNodePtr, *PNodePtr, *RNodePtr;

// найти узел, данные в котором совпадают с item.

// получить его адрес и адрес его родителя

if((DNodePtr=FindNode(item,PNodePtr))==NULL)

return;

// если узел D имеет NULL-указатель, то заменяющим

// узлом является тот, что находится на другой ветви

if(DNodePtr->right==NULL)

RNodePtr=DNodePtr->left;

else if(DNodePtr->left==NULL)

RNodePtr=DNodePtr->right;

// узел D имеет двух сыновей

else

{

// найти и отсоединить заменяющий узел R для узла D.

// в левом поддереве узла D найти узел с максимальным данным

// из всех узлов с меньшими данными, чем в узле D.

// отсоединить этот узел от дерева.

// PofRNodePtr - указатель на родителя заменяющего узла

TreeNode *PofRNodePtr=DNodePtr;

// первой возможной заменой является левый сын узла D

RNodePtr=DNodePtr->left;

// спуститься вниз по правому поддереву левого сына узла D,

// сохраняя записи текущего узла и его родителя.

// остановившись, будем иметь заменяющий узел

while (RNodePtr->right!=NULL)

{

PofRNodePtr=RNodePtr;

RNodePtr=RNodePtr->right;

}

if(PofRNodePtr==DNodePtr)

// левый сын удаляемого узла является заменяющим

// присоединить правое поддерево узла D к узлу R

RNodePtr->right=DNodePtr->right;

else

{

// спустились вниз по правой ветви как минимум на один узел.

// удалить заменяющий узел из дерева,

// присоединив его левую ветвь к его родительскому узлу

PofRNodePtr->right=RNodePtr->left;

// присоединить правую и левую ветви удаляемого узла

// к правой и левой ветвям соответственно заменяющего узла

RNodePtr->right=DNodePtr->right;

RNodePtr->left=DNodePtr->left;

}

}

// завершить присоединение заменяющего узла к родительскому узлу.

// удалить корневой узел. назначить новый корень.

if(PNodePtr==NULL)

root=RNodePtr;

// присоединить узел R к узлу P с правильной стороны

else

if(DNodePtr->data<PNodePtr->data)

PNodePtr->left=RNodePtr;

else

PNodePtr->right=RNodePtr;

// удалить узел из памяти и уменьшить размер дерева

delete DNodePtr;

DNodePtr=NULL;

size--;

}

//---------------------------------------------------------------------

// эта функция при обходе дерева подсчитывает его листья.

// функция использует обратный метод обхода дерева.

// во время посещения узла проверяется, является ли он листом.

void BinSTree::CountLeaf(TreeNode *t,int& count)

{

// использовать обратный метод прохождения

if(t!=NULL)

{

CountLeaf(t->left, count); // пройти левое поддерево

CountLeaf(t->right, count); // пройти правое поддерево

// проверить, является ли данный узел листом.

// если да, то произвести приращение переменной count

if( t->left==NULL && t->right==NULL)

count++;

}

}

//----------------------------------------------------------------------

// эта функция использует обратный метод обхода дерева для

// вычисления глубины левого и правого поддеревьев узла и

// возвращает результирующее

// значение глубины, равное 1+max(depthLeft,depthRight).

// глубина пустого дерева равна -1

int BinSTree::Depth(TreeNode *t)

{

int depthLeft, depthRight, depthval;

if(t==NULL)

depthval=-1;

else

{

depthLeft=Depth(t->left);

depthRight=Depth(t->right);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

return depthval;

}

//-----------------------------------------------------------------------

// создать дубликат нового дерева t и возвратить корень нового дерева

TreeNode *BinSTree::CopyTree(TreeNode *t)

{

// переменная newnode указывает на новый узел, создаваемый

// посредством вызова GetTreeNode и присоединяемый в дальнейшем

// к новому дереву. указатели newlptr и newrptr адресуют сыновей

// нового узла и передаются в качестве параметров в GetTreeNode

TreeNode *newlptr, *newrptr, *newnode;

// остановить рекурсивное прохождение при достижении пустого дерева

if(t==NULL)

return NULL;

// CopyTree строит новое дерево в процессе прохождения узлов дерева t.

// в каждом узле этого дерева функция CopyTree проверяет наличие

// левого сына.

// если он есть, создается его копия. в противном случае возвращается

// NULL.

// CopyTree создает копию узла с помощью GetTreeNode

// и подвешивает к нему копии сыновей

if(t->Left()!=NULL)

newlptr=CopyTree(t->left);

else

newlptr=NULL;

if(t->Right()!=NULL)

newrptr=CopyTree(t->right);

else

newrptr=NULL;

// построить новое дерево снизу вверх, сначала создавая

// двух сыновей, а затем их родителя

newnode=GetTreeNode(t->data, newlptr, newrptr);

// вернуть указатель на вновь созданное дерево

return newnode;

}

//------------------------------------------------------------------------

// использовать обратный алгоритм для прохождения узлов дерева

// и удалить каждый узел при его посещении

void BinSTree::DeleteTree(TreeNode* t)

{

if(t)

{

DeleteTree(t->left);

DeleteTree(t->right);

delete t;

size--;

}

}

//--------------------------------------------------------------------------

// вызвать функцию DeleteTree для удаления узлов дерева.

// затем сбросить указатель на его корень в NULL

void BinSTree::ClearTree()

{

DeleteTree(root);

root=NULL;

// теперь корень пуст, дерево уничтожено

}

//------------------------------------------------------------------------

Достаточно полную информацию для размещения компонентов на форме и задания их свойств можно получить из представленных ниже рис.8.3, рис.8.4 и заголовочного файла модуля LR_8.

Рис.8.3 – форма по окончании проектирования

Рис.8.4 – меню

Заголовочный файл LR_8.hмодуля LR_8

//---------------------------------------------------------------------------

#ifndef LR_8H

#define LR_8H

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include "CSPIN.h"

#include <ComCtrls.hpp>

#include <ActnCtrls.hpp>

#include <ActnList.hpp>

#include <ActnMan.hpp>

#include <ActnMenus.hpp>

#include <ImgList.hpp>

#include <ToolWin.hpp>

#include <ExtCtrls.hpp>

#include <Buttons.hpp>

//---------------------------------------------------------------------------

class TForm1 : public TForm

{

__published: // IDE-managed Components

TMemo *Memo1;

TLabel *Label1;

TImageList *ImageList1;

TActionManager *ActionManager1;

TAction *SaveFileAs;

TAction *SaveFile;

TAction *OpenFile;

TAction *OutMemo;

TAction *Depth;

TAction *CountLeaf;

TAction *Find;

TAction *ClearTree;

TAction *Exit;

TGroupBox *GroupBox1;

TRadioButton *RadioButton2;

TRadioButton *RadioButton1;

TCSpinEdit *CSpinEdit1;

TButton *Button1;

TButton *Button2;

TLabeledEdit *LabeledEdit1;

TAction *Insert;

TAction *Delete;

TBitBtn *BitBtn1;

TActionMainMenuBar *ActionMainMenuBar1;

TActionToolBar *ActionToolBar1;

TAction *ClearMemo;

TLabeledEdit *LabeledEdit2;

TLabel *Label2;

void __fastcall RadioButton2Click(TObject *Sender);

void __fastcall RadioButton1Click(TObject *Sender);

void __fastcall ExitExecute(TObject *Sender);

void __fastcall OutMemoExecute(TObject *Sender);

void __fastcall InsertExecute(TObject *Sender);

void __fastcall BitBtn1Click(TObject *Sender);

void __fastcall ClearMemoExecute(TObject *Sender);

void __fastcall ClearTreeExecute(TObject *Sender);

void __fastcall CountLeafExecute(TObject *Sender);

void __fastcall DepthExecute(TObject *Sender);

void __fastcall FindExecute(TObject *Sender);

void __fastcall DeleteExecute(TObject *Sender);

private: // User declarations

public: // User declarations

__fastcall TForm1(TComponent* Owner);

};

//---------------------------------------------------------------------------

extern PACKAGE TForm1 *Form1;

//---------------------------------------------------------------------------

#endif

Перенесем на форму компоненты и зададим их свойствам значения. Со страницы Дополнительно – LabeledEdit1 (EditLabel->Caption – Ключ, Text- 10), диспетчер действий ActionManager1и полосу главного меню ActionMainMenuBar1. По умолчанию полоса главного меню ActionMainMenuBar1расположится вверху, на всю ширину формы. Задайте её свойство Align = alNone, чтобы придать ей нужные размеры и расположить в нужном месте.

Затем со страницы Win32 перенесите на форму ImageList1, со страницы Стандарт - Label1(Caption – ДЕРЕВО), Memo1, GroupBox1(Caption – Формирование дерева). На панель GroupBox1 перенесите: со страницы Стандарт - две радиокнопки – RadioButton1(Caption - вручную,Checked – true, Enabled - true) и RadioButton2 (Caption - автоматически,Checked – false,Enabled - true), Label2(Caption – количество узлов), Button1 (Caption – Добавить узел), Button2 (Caption – Удалить узел ), со страницы Примеры – CSpinEdit1 (MaxValue -100, MinValue – 1, Value – 10), со страницы Дополнительно – BitBtn1 (Caption – ПУСК), LabeledEdit2 (EditLabel->Caption – целое число, Text- 10).

Загрузите в компонент ImageList1 пиктограммы из файлов fldropen, filesave, floppy, find, insert, clear, delete, arrow2d, erase, dooropen, directry. В компоненте ActionManager1 установим свойство Images равным ImageList1, связав тем самым диспетчер действий со списком изображений.

Добавьте на форму с помощью диспетчера действий ActionManager1 инструментальную панель ActionTollBar1, задайте для нее Align = alNone, Constraints->MaxHeight =230, Constraints->MinHeight =230 и расположите ее на форме согласно рис.8.3.

В диспетчере действий ActionManager1 создайте три категории действий: Файл, Дерево, Выход.

По категориям объектам действий даны следующие надписи (Caption) - имена (Name): Файл: Сохранить как - FileSaveAs, Сохранить - FileSave, Открыть - FileOpen; Дерево: Уничтожить дерево - ClearTree, Поиск узла по ключу - Find, Кол-во листьев - CountLeaf, Глубина дерева - Depth, Вывести дерево в окно - OutMemo, Удалить узел - Delete, Добавить узел - Insert, Очистить окно - ClearMemo. В свойство ImageIndexперечисленных объектов действий занесите соответствующие значения.

В свойство Action кнопок Button1 (Caption – Добавить узел) и Button2 (Caption – Удалить узел ) занесите соответственно значения Insert и Delete.

Действия по активации и инициализации компонентов и обработчики событий приведены в файле реализации LR_8.cppмодуля LR_8.

Файл реализации LR_8.cpp модуля LR_8

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "LR_8.h"

#include "f_8_2.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

Memo1->Text="";

RadioButton1->Checked=true;

RadioButton2->Checked=false;

CSpinEdit1->Enabled=false;

Label2->Enabled=false;

BitBtn1->Enabled=false;

Button1->Enabled=true;

Button2->Enabled=true;

LabeledEdit2->Enabled=true;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton2Click(TObject *Sender)

{

if(RadioButton2->Checked)

{

Label2->Enabled=true;

CSpinEdit1->Enabled=true;

LabeledEdit2->Enabled=false;

BitBtn1->Enabled=true;

Button1->Enabled=false;

Button2->Enabled=false;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton1Click(TObject *Sender)

{

if(RadioButton1->Checked)

{

Label2->Enabled=false;

CSpinEdit1->Enabled=false;

BitBtn1->Enabled=false;

LabeledEdit2->Enabled=true;

Button1->Enabled=true;

Button2->Enabled=true;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ExitExecute(TObject *Sender)

{

Close();

}

//---------------------------------------------------------------------------

// вывод дерева в окно с обходом справа-налево

void PrintTree(TreeNode *t, int level)

{

AnsiString s="";

// обходить дерево справа-налево, пока t!=NULL

if(t!=NULL)

{

// обходить правое поддерево узла t

PrintTree(t->Right(), level+1);

// вывести данное в узле t

for(int i=0; i<level; i++) s += "****";

s += IntToStr(t->data);

Form1->Memo1->Lines->Add(s);

// обходить левое поддерево узла t

PrintTree(t->Left(), level+1);

}

}

//-------------------------------------------------------------------------

// создать объект класса - бинарное дерево

BinSTree AI;

//-------------------------------------------------------------------------

void __fastcall TForm1::OutMemoExecute(TObject *Sender)

{

TreeNode *t= AI.GetRoot();

if(t==NULL)

{

MessageBox(NULL,"Дерево пусто!","",0);

return;

}

Form1->Memo1->Lines->Add("");

PrintTree(t,0);

Form1->Memo1->Lines->Add("Количество узлов - " +

IntToStr(AI.GetSize()));

Form1->Memo1->Lines->Add("");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::InsertExecute(TObject *Sender)

{

AI.Insert(StrToInt(LabeledEdit2->Text));

Form1->Memo1->Lines->Add("Узел "+LabeledEdit2->Text+" добавлен!");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::BitBtn1Click(TObject *Sender)

{

AI.ClearTree();

for(int i=0; i<CSpinEdit1->Value; i++)

AI.Insert(random(101)-random(101));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ClearMemoExecute(TObject *Sender)

{

Memo1->Clear();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ClearTreeExecute(TObject *Sender)

{

if(AI.GetRoot()==NULL)

{

MessageBox(NULL,"Дерево пусто!","",0);

return;

}

AI.ClearTree();

if(AI.GetRoot()==NULL)

MessageBox(NULL,"Дерево уничтожено!","",0);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::CountLeafExecute(TObject *Sender)

{

TreeNode* t=AI.GetRoot();

int count=0;

AI.CountLeaf(t, count);

Form1->Memo1->Lines->Add("Количество листьев - "+IntToStr(count));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::DepthExecute(TObject *Sender)

{

TreeNode* t=AI.GetRoot();

int d=AI.Depth(t);

Form1->Memo1->Lines->Add("Глубина дерева - "+IntToStr(d));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FindExecute(TObject *Sender)

{

int key = StrToInt(LabeledEdit1->Text);

if(AI.Find(key))

Form1->Memo1->Lines->Add("Узел с ключом "+IntToStr(key)+" есть!");

else

Form1->Memo1->Lines->Add("Узла с ключом "+IntToStr(key)+" нет!");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::DeleteExecute(TObject *Sender)

{

int k = StrToInt(LabeledEdit2->Text);

if(AI.Find(k))

{

AI.Delete(k);

Form1->Memo1->Lines->Add("Узел "+IntToStr(k)+" удален!");

}

else

Form1->Memo1->Lines->Add("Узла "+IntToStr(k)+" нет!");

}

//---------------------------------------------------------------------------