Выбор, размещение и задание свойств компонентов.

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

    Сохраните модуль главной формы под именем 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)+" нет!");

}

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

Тестирование и использование приложения

1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.

2.Выполните тестирование по рис.8.5. Разница между заданным и фактическим количеством узлов в дереве объясняется тем, что узлы для последующих равных чисел не создаются.

3.Выполните тестирование по рис.8.6. Здесь вначале используется автоматический режим формирования дерева, а затем – ручной.

4.Создать дерево, а затем – копию этого дерева. Деревья вывести в окно.

5.Создать два дерева, а затем одно дерево присвоить другому. Правильность действий подтвердить выводом в окно.

6.Реализовать вертикальный вывод дерева в окно.

7.Реализовать сохранение дерева в файле.

8.Написать обработчики соответствующих событий по п.4…п.7 и дополнить интерфейс.

9.Полученные результаты продемонстрировать преподавателю.

Рис.8.5 – формирование дерева в автоматическом режиме

Рис.8.6 - формирование дерева в автоматическом и ручном режимах

Контрольные вопросы

1.Расскажите о назначении и содержании класса TreeNode.

2.Как выделяется и инициализируется память для узла дерева?

3.Укажите в коде использование функций Left() и Right(). Почему они объявлены константными?

4.Как выполняются конструктор и деструктор класса TreeNode?

5.Расскажите о назначении и содержании класса BinSTree.

6.С какой целью класс BinSTree объявлен другом класса TreeNode?

7.Как выполняются конструктор и деструктор класса BinSTree?

8.Как осуществляется поиск узла по ключу?

9.Как выполняется функция Find?

10.Как добавляется узел в дерево?

11.Как создать дерево в автоматическом режиме?

12.Как создать дерево в ручном режиме?

13.Как выводится дерево в окно?

14.Поясните назначение и выполнение функции FindNode.

15.Почему нужен указатель на родителя удаляемого узла?

16.Как находят заменяющий узел, когда удаляемый узел имеет оба поддерева?

17.Как происходит замена удаляемого узла, если заменяющий узел не является его сыном?

18.При выполнении какого условия заменяют корень?

19.Расскажите о назначении и выполнении функций Delete, DeleteTree, ClearTree, CopyTree, Depth, CountLeaf.

20.Как сохранить дерево в файле?

21.Как вывести дерево из файла?

22.Как выполняется перегруженная операция присваивания?

23.Как создать новое дерево – копию другого дерева?

24.Как присвоить одно дерево другому?

25.Как реализовать вертикальный вывод дерева?

Задания

1.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести дерево и все его ветви на экран.

2.Массив из целых чисел представить в виде идеально сбалансированного бинарного дерева. Вывести дерево и слой с заданным ключом на экран.

3.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и все ветви слоя с заданным ключом.

4.Массив из чисел представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и ту половину дерева, где находится заданный ключ - с вершины, а другую половину - с корня.

5.Последовательность букв представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и все слои дерева, начиная с вершины, а затем - с корня.

6.Массив из букв представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и номер того слоя, где находится заданная буква.

7.Массив из чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и все его ветви, исходящие из слоя с заданным ключом.

8.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и слой с минимальным ключом.

9.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и ветви, сумма ключей в которых превышает заданное число.

10.Последовательность букв представить в виде идеально сбалансированного дерева. Вывести на экран дерево и ветви с гласными буквами.

11.Массив строк представить в виде упорядоченного бинарного дерева. Вывести дерево и слои со строками одинаковой длины на экран.

12.Массив строк представить в виде идеально сбалансированного дерева. Вывести дерево, слой и ветвь со строкой максимальной длины на экран.

13.Два бинарных дерева зеркально подобны, если либо оба они пусты, либо оба непусты, и при этом левое поддерево одного из них подобно правому поддереву другого и наоборот. Определить, являются ли два дерева зеркально подобными.

14. Два бинарных дерева подобны, если либо оба они пусты, либо оба непусты, и при этом их левые и правые поддеревья подобны. Определить, являются ли два дерева подобными.

15. Составить программу, которая читает произвольный C-файл и печатает в алфавитном порядке каждую группу имен переменных, совпадающих в первых N символах, но различающихся где-либо дальше. При решении задачи использовать дерево с узлами вида: struct NODE{char* word; int k; NODE* left; NODE* right;};. (Слова внутри символьных строк и комментариев не рассматривать.)

16. Формулу вида <формула>::=<цифра>|(<формула><знак><формула>) <знак>::= + | - | *   <цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9   можно представить в виде бинарного дерева по следующим правилам: а)формула из одной цифры представляется деревом из одной вершины с этой цифрой; б)формула вида f1# f2 представляется деревом, в котором корень - это знак # соответствующей операции, а левое и правое поддеревья - это представления формул f1,f2 в виде бинарных деревьев. Например, формуле 5*(3+8) соответствует дерево 

                                              *

                                           / \

                          5   +

                                 / \

                                3  8

Требуется: а)построить дерево по формуле указанного выше вида; б)вычислить как целое число значение дерева-формулы; в)по заданному дереву распечатать соответствующую формулу.

17. Составить программу, формирующую “перекрестные списки”, т.е. печатающую список слов, которые встречаются в анализируемом файле, а для каждого слова - список номеров строк, в которых это слово встречается. При решении задачи рекомендуется использовать следующие структуры данных: struct LIST //список номеров строк для данного слова

                           { int num; struct LIST* p; }

struct NODE //узел дерева с информацией об очередном слове

{ char* word; struct LIST*lines; struct NODE*left; struct NODE*right;}.

18. Распечатать слова текста, отсортированные в порядке убывания частоты их встречаемости (рядом с каждым словом выводить значение счетчика частоты его вхождений в текст). При решении задачи использовать дерево следующей структуры:

struct NODE

{char* word; int k; struct NODE* left; struct NODE* right;}.

19. В упорядоченном бинарном дереве удалить узел с указанным ключом.

20. В упорядоченном бинарном дереве удалить все листья.

21. Вывести упорядоченное бинарное дерево послойно, начиная с корня, сначала исходное, а затем – после удаления указанного слоя.

22. Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК, фамилию и инициалы автора, название, год издания, количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: а)начальное формирование данных о всех книгах в библиотеке в виде бинарного дерева; б)добавление данных о книгах, вновь поступающих в библиотеку; в)удаление данных о списываемых книгах; г)по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.

23. Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержит: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета. Программа должна обеспечивать: а)хранение всех заявок в виде бинарного дерева; б)добавление и удаление заявок; в) по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением; г)вывод всех заявок.

24. Англо-русский словарь построен как бинарное дерево. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Первоначально дерево формируется согласно английскому алфавиту. В процессе эксплуатации словаря при каждом обращении к компоненте в счетчик обращений добавляется единица. Составить программу, которая: 1)обеспечивает начальный ввод словаря с конкретными значениями счетчиков обращений; 2)формирует новое представление словаря в виде бинарного дерева по следующему алгоритму: а)в старом словаре находится компонента с наибольшим значением счетчика обращений, б)найденная компонента заносится в новый словарь и удаляется из старого, в)переход к п. ‘а)’ до исчерпания исходного словаря; 3)производит вывод исходного и нового словарей. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

25. На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как бинарное дерево. Составить программу, которая: 1)обеспечивает начальное формирование картотеки в виде бинарного дерева; 2)производит вывод всей картотеки; 3)вводит номер телефона и время разговора; 4)выводит извещение на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

26. Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные в информационной системе организованы в виде бинарного дерева. Составить программу, которая: 1)обеспечивает первоначальный ввод данных в информационную систему и формирование бинарного дерева; 2)производит вывод всего дерева; 3)вводит номер поезда и выводит все данные об этом поезде; 4)вводит название станции назначения и выводит данные обо всех поездах, следующих до этой станции. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

27. Бинарное упорядоченное дерево стереть слой за слоем, начиная с максимально дальней вершины.

28. В идеально сбалансированном бинарном дереве удалить узел с заданным ключом.

29. По исходному бинарному дереву построить подобное дерево.

30. По исходному бинарному дереву построить зеркально подобное дерево.

ЛАБОРАТОРНАЯ РАБОТА 9

ИЕРАРХИЯ: ТОЧКА, КРУГ, ЦИЛИНДР

Введение

        Наследование и полиморфизм являются наиболее важными особенностями объектно-ориентированного программирования и позволяют эффективно преодолевать сложности программного обеспечения. Полиморфизм позволяет создавать программы, обрабатыващие широкий круг как существующих, так и еще даже не описанных родственных классов.

Наследование

    Наследование – это способ повторного использования программного обеспечения, при котором новые классы создаются из уже существующих классов путем использования их атрибутов и функций. При создании нового класса можно указать, что он является наследником данных-элементов и функций-элементов ранее определенного базового класса. Новый класс называют производным классом. Он также может быть базовым для будущих производных классов. При простом наследовании класс порождается одним базовым классом.

Базовый класс может наследоваться как public (открытый), protected (защищенный) или private(закрытый). Защищенное и закрытое наследования встречаются редко. В случае public открытые элементы базового класса становятся открытыми элементами производного класса, а защищенные элементы базового класса становятся защищенными элементами производного класса. Закрытые элементы базового класса никогда не бывают доступны для производного класса. Элементы базового класса, которые не должны быть доступны производному классу через наследование, объявляются в базовом классе закрытыми.

Базовый класс может быть прямым или косвенным базовым классом производного класса. Прямой базовый класс явно перечисляется в заголовке при объявлении производного класса, а косвенный – наследуется через два или более уровней иерархии.        

Производный класс обычно добавляет свои собственные данные-элементы и функции-элементы, так что производный класс в общем случае больше своего базового класса. Производный класс более специфичен по своему назначению, более узок, чем его базовый класс, и представляет меньшую группу объектов. При простом наследовании предполагается, что производный класс будет выполнять примерно те же функции, что и базовый класс.

    Каждый объект производного класса при открытом наследовании является также объектом соответствующего базового класса, но не наоборот.

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

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

Виртуальные функции и полиморфизм

    Виртуальные функции и полиморфное программирование позволяют автоматически выполнять логику, аналогичную логике оператора switch.

    Виртуальная функция объявляется с помощью ключевого слова virtual, предшествующего прототипу функции в базовом классе, например, virtual float getX()const;. Функция может быть чистой виртуальной, тогда virtual float getX()const=0;. Несмотря на то, что некоторые функции могут быть неявно виртуальными, поскольку они были объявлены такими на более высоком уровне иерархии, рекомендуется явно объявлять функции виртуальными на каждом уровне иерархии, чтобы обеспечить ясность программы.

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

    Если виртуальная функция вызывается обращением к объекту по имени и при этом используется операция доступа точка, то эта ссылка обрабатывается во время компиляции (это называется статическим связыванием) и в качестве вызываемой определяется функция класса данного объекта (или наследуемая этим классом).

    Использование виртуальных функций делает целесообразным определять в иерархии абстрактный базовый класс, который содержит хотя бы одну чистую вуртуальную функцию. В отличие от конкретных классов, абстрактные классы не могут порождать объекты. Однако указатель на абстрактный базовый класс может быть объявлен. Если класс является производным от класса с чистой виртуальной функцией и если эта чистая виртуальная функция не определена в производном классе, то функция остается чистой виртуальной и в производном классе. Тогда производный класс также является абстрактным классом.

    Переопределенная в производном классе виртуальная функция должна иметь тот же самый тип возвращаемого значения и ту же сигнатуру, что и виртуальная функция базового класса.

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

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

    Когда вызов виртуальной функции осуществляется по указателю, вызываемая виртуальная функция будет установлена для вызванного объекта во время выполнения программы, т.е. при помощи динамического (позднего) связывания.

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

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

    В класс с виртуальными функциями рекомендуется включать виртуальный деструктор. Это приведет к тому, что все деструкторы производных классов станут виртуальными, даже если они имеют имена, отличные от имени деструктора базового класса. В этом случае, если объект в иерархии уничтожен явным использованием операции delete, примененной к указателю базового класса на объект производного класса, то будет вызван деструктор соответствующего класса.

    Конструкторы не могут быть виртуальными.

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

Проектирование приложения.