Информатика и технология программирования


Двоичное дерево


Для двоичного дерева имеется аналогичная проблема в представлении объекта-заголовка дерева и объектов-вершин. Самый простой вариант состоит в том, что корневая вершина дерева является одновременно и объектом-заголовком. Но, поскольку дерево может быть и пустым, тогда следует допустить наличие в вершине дерева NULL -указателя на элемент данных. Такая вершина будет считаться "незанятой". Конструктор объекта-вершины дерева должен создавать именно такую "незанятую" вершину.

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


class btree
{
void *data;
btree *l,*r;
public:
btree(); // Конструктор - создать "пустую" вершину


~btree();
int size(); // Количество элементов


void *operator[](int&#38); // Извлечение по номеру


void *operator[](void*,int(*)(void*,void*));
// Извлечение по ключу (двоичный поиск)


void operator()(void*,int(*)(void*,void*)););
// Включение с сохранением упорядоченности


};


btree::btree()
{ r=l=data=NULL; }

Деструктор должен быть рекурсивным, поскольку при разрушении данных в вершине необходимо выполнить операцию уничтожения и освобождения памяти из под объектов - потомков, которые в свою очередь с своих деструкторах сделают то же самое для своих потомков.


btree::~btree()
{
if (l!=NULL) delete l;
if (r!=NULL) delete r;
}

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


Начало  Назад  Вперед



Книжный магазин