Создание бинарного дерева

Конструкторы удобно использовать для создания различных связанных структур, в том числе и бинарных деревьев. Напомним, что бинарным де­ревом называется система объектов, связанных по следующему принципу. В вершине иерархии находится один родительский объект, и каждый объ­ект структуры ссылается на два объекта того же типа. В листинге 2.1 при­веден пример программного кода с определением класса BinTree. Класс содержит конструктор, через который и реализуется процесс создания би­нарного дерева. Конструктор вызывается с аргументом целого типа. При этом аргумент конструктора определяет «глубину» (т.е. количество уров­ней) бинарного дерева.

Листинг 2.1. Создание бинарного дерева

#include <iostream>

using namespace std;

class BinTree{

public:

static int Count;

int m;

BinTree *pl;

BinTree *p2;

BinTree(int n){

if(n==l){

pi=NULL; p2=NULL;}

else {

pl=new BinTree(n-1); p2=new BinTree(n-1);}

m=++Count;

cout<<"Object created: "<<this<<" : "<<m; cout«" -> Number of objects: "<<Count<<endl; }

~BinTree () {

delete p1;

delete p2;

Count--;

cout<<"Object deleted: "«this«" : "«m; cout«^,” -> Number of objects: "<<Count<<endl; }

};

int BinTree::Count;

int main(){

BinTree::Count=0;

BinTree objl(3);

BinTree *p;

p=new BinTree(2);

delete p;

return 0;}

При создании и удалении объектов выполняется их автоматический под­счет. Реализуется это через статическое целочисленное поле Count класса BinTree. Кроме этого, в классе объявляется целочисленное поле m для ну­мерации объектов. Класс также содержит в качестве полей два указателя pi и р2 на объекты класса BinTree. Поля используются для связи объ­екта с двумя другими объектами того же класса. Через эти поля-указатели реализуется вся структура бинарного дерева. Вся функциональность класса BinTree реализуется через конструктор и деструктор.

Конструктору передается целочисленный аргумент. Если аргумент равен единице, полям pi и р2 создаваемого объекта присваиваются значения NULL (нулевые указатели). В противном случае динамически создается два объекта класса BinTree, при этом аргумент для конструктора создаваемых объектов уменьшается на единицу.

При создании нового объекта класса BinTree значение статической пере­менной Count увеличивается на единицу, и это значение присваивается полю т. Соответствующая команда в конструкторе имеет вид m=++Count. Также создание объекта сопровождается выводом соответствующего сооб­щения с указанием адреса выделенной под объект памяти, значения поля m и общего количества созданных объектов.

В деструкторе освобождается место памяти, выделенное для объектов, на которые указывают поля p1 и р2 удаляемого объекта, уменьшается на еди­ницу значение статического поля Count, а также выводится сообщение с указанием адреса удаляемого объекта, значения его поля ш, равно как и ко­личество объектов, оставшихся в работе.

В главном методе программы статическое поле Count инициализируется с начальным нулевым значением, а также создается два объекта (точнее, два бинарных дерева) класса BinTree - один статически, один динамически. Ре­зультат выполнения программы может выглядеть так, как показано ниже:

Object created: 003210С8 : 1 -> Number of objects: 1

Object created: 00321180 : 2 -> Number of objects: 2

Object created: 00321090 : 3 -> Number of objects: 3

Object created: 003211F0 : 4 -> Number of objects: 4

Object created: 00322850 : 5 -> Number of objects: 5

Object created: 003211B8 : 6 -> Number of objects: 6

Object created: 0012FF68 : 7 -> Number of objects: 7

Object created: 003228C0 : 8 -> Number of objects: 8

Object created: 003228F8 : 9 -> Number of objects: 9

Object created: 00322888 : 10 -> Number of objects: 10

Object deleted: 003228C0 : 8 -> Number of objects: 9

Object deleted: 003228F8 : 9 -> Number of objects: 8

Object deleted: 00322888 : 10 -> Number of objects: 7

Object deleted: 003210C8 : 1 -> Number of objects: 6

Object deleted: 00321180 : 2 -> Number of objects: 5

Object deleted: 00321090 : 3 -> Number of objects: 4

Object deleted: 003211F0 : 4 -> Number of objects: 3

Object deleted: 00322850 : 5 -> Number of objects: 2

Object deleted: 003211B8 : 6 -> Number of objects: 1

Object deleted: 0012FF68 : 7 -> Number of objects: 0

Сначала создаются десять объектов (семь в результате выполнения команды BinTree obj 1 (3) - дерево из трех уровней содержит 2³—1=7 элементов, и три в результате динамического создания объекта командой p=new BinTree (2) - создается 2²—1 = 3 объектов). Затем динамиче­ский объект удаляется, в результате чего удаляются все три объекта (с номе­рами 10, 9 и 8), входящие в соответствующее бинарное дерево. Статический объект со всей связанной с ним структурой (объекты со значениями поля m от 1 до 7) удаляется при завершении работы программы автоматически.

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

Ряд для экспоненты

В следующем примере реализуется вычисление экспоненты, правда, не­сколько необычным образом. Для этих целей создается класс, у которого имеется поле - динамический массив. Элементами массива являются сла­гаемые ряда, через который вычисляется экспонента. Массив заполняется при создании соответствующего объекта. Аргументами конструктору пере­даются верхний индекс ряда int п и аргумент экспоненты double х. Про­граммный код приведен в листинге 2.2.

Листинг 2.2. Ряд для экспоненты

#include <iostream>

using namespace std;

class MyExp{

public:

int n;

double *p;

MyExp(xnt i,double x){

n=i;

p=new double[n+1];

P[0]=1;

for(int k=l;k<=n;k++) p[k]=p[k-1]*x/k;

}

~MyExp(){

delete [] p;}

} ;

int main(){

int n,i;

double x,s=0;

cout«"enter n= “;

cin»n;

cout«"enter x= ";

cin>>x;

MyExp obj(n,x);

for(1=0;i<=n;i++) s+=obj.p[i];

cout<<"exp ( "«x«") = "«s«endl;

return 0;}

Результат выполнения программы может иметь следующий вид (жирным шрифтом выделен ввод пользователя):

enter n= 100

enter х= 1

exp (1)= 2.71828

Пользователем вводятся значения для верхней границы ряда и аргумент экспоненты (переменные int пи double х в главном методе программы). Эти аргументы передаются конструктору при создании объекта командой MyExp obj (n, х). Конструктором первый аргумент присваивается в ка­честве значения полю п объекта obj. Это же значение используется при выделении памяти под динамический массив, указатель на первый элемент которого присваивается в качестве значения полю р объекта obj. После выделения места под массив выполняется заполнение элементов массива. В качестве значения элементу с нулевым индексом присваивается единица, а прочие элементы заполняются на основе предыдущего значения: преды­дущий элемент умножается на х и делится на индексную переменную к.

В деструкторе выполняется очистка памяти, выделенной под динамиче­ский массив.

Поле-объект

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

Листинг 2.3. Поле-объект

#include <iostream>

using namespace std;

//"Внутренний" класс:

class Inner{

public:

int n;

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

Inner(){

n=0;

cout«"Inner-object created with n="«n«endl; }

//Деструктор:

~Inner () {

cout«"Inner-object destroyed with n="<<n<<endl; }

} ;

//"Внешний" класс:

class Outer{

public:

int m;

//Поле-объект:

Inner obj;

//Перегруженный конструктор:

Outer (int i) {

m=i ;

cout«"Outer-object created with m="«m<<endl; }

Outer(int i,int j){

m=i;

obj.n=j;

cout«"Outer-object created with m="«m«endl; }

//Деструктор:

~Outer(){

cout<<"Outer-object destroyed with m="<<m«endl; }

};

int main(){

int i=l0,j=20,k=30;

Outer a(i);

Outer b(j,k);

cout«"a.m: "«a.m<<" a.obj.n: "«a . ob j . n<<endl;

cout«"b.m: "<<b.m<<" b.obj.n: "«b . ob j . n<<endl;

return 0;}

В программе объявляется класс Inner, имеющий целочисленное поле n, конструктор (без аргументов) и деструктор. При создании и уничтожении объекта выводится соответствующее сообщение с указанием значения поля п создаваемого или уничтожаемого объекта.

В классе Outer описано целочисленное поле т, а также поле obj, являю­щееся объектом класса Inner. У класса Outer также есть перегруженный конструктор (с одним аргументом и с двумя), равно как и деструктор.

В главном методе программы создается два объекта класса Outer. Объект а создается посредством конструктора с одним аргументом, а объект b - с помощью конструктора с двумя аргументами. Значения полей объектов выводятся на экран. Результат выполнения программы имеет вид:

Inner-object created with n=0

Outer-object created with m=10

Inner-object created with n=0

Outer-object created with m=20

a.m: 10 a.obj.n: 0

b.m: 20 b.obj.n: 30

Outer-object destroyed with m=20

Inner-object destroyed with n=30

Outer-object destroyed with m=10

Inner-object destroyed with n=0

Обращаем внимание, что при создании объекта класса Outer, кроме со­общения о создании этого объекта, предварительно выводится сообще­ние о создании объекта Inner - это создается поле obj — объект класса Inner, причем создается он с помощью конструктора «по умолчанию» (конструктор без аргументов) класса Inner, поэтому поле п этого объекта получает нулевое значение. Кроме того, специфично выглядит обращение к полю п объекта obj, являющегося полем объекта класса Outer: напри­мер, а.obj.n или b.obj.n.

Поле-массив объектов

Несколько белее сложная ситуация имеет место, когда полем класса явля­ется массив объектов другого класса. Такой случай рассматривается в про­граммном коде листинга 2.4.

Листинг 2.4. Поле-массив объектов

#include <iostream>

using namespace std;

//Размер поля-массива:

const int n=10;

//"Внутренний" класс:

class Inner{

public:

int m;

int number;

//Метод для отображения полей:

void show () {

if(m!=l) (this-1)->show();

cout«number«” “;}

};

//"Внешний" класс:

class Outer{

public:

//Поле-массив объектов:

Inner obj{n];

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

Outer (){

int i;

obj[0].m=l; obj[0].number=l;

obj [1] . m=2; obj[1].number=l;

for (i=2;i<n;i++) {

obj[i].m=i+l;

obj [i] .number=obj[i — 1] .number+obj[i-2] .number;}

}

} ;

int main(){

Outer a;

a.obj[n/2].show();

cout«endl;

a.obj[n-1].show();

cout«endl ;

return 0;}

В программе реализуется последовательность чисел Фибоначчи - правда, довольно экзотическим способом. В программе описывается класс Inner, у которого два целочисленных поля m и number. Последовательность чисел Фибоначчи реализуется посредством объектов класса Inner - в полет за­носится порядковый номер числа, в поле number записывается непосред­ственно число, а сами объекты организуются в массив, который является полем класса Outer.

В классе Outer объявлен в качестве поля массив объектов класса Inner. Размер массива ранее определен в виде целочисленной константы. В кон­структоре класса Outer выполняется заполнение полей объектов класса

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

Но самое ужасное происходит в методе show () класса Inner. Методом выводится значение поля number объекта, но предварительно, если поле m объекта, из которого вызывается метод, не равняется единице, вызывается метод show () «предыдущего» объекта. Для определения «предыдущего» объекта используется адресная арифметика в виде инструкции this-1. Эта ссылка означает объект, размещенный в предыдущей ячейке по отношению к текущему объекту. Такая команда имеет корректный смысл, только если речь идет о массиве объектов - в противном случае результат будет весьма трагическим. Таким образом, получаем своеобразную рекурсию, а действие метода show () сводится к тому, что на экран выводятся значения полей number объектов массива, от начального до текущего, из которого вызыва­ется метод show ().

Результат выполнения программы имеет вид:

1 1 2 3 5 8

1 1 2 3 5 8 13 21 34 55

В первой строке командой a.obj [n/2].show() выводятся 6 чисел последовательности Фибоначчи (в массиве 10 элементов, метод вызывается из объекта с индексом 5, что соответствует 6-ти числам в последовательно­сти). Второй командой а.obj[ n-1 ].show() выводятся значения из всего массива.