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

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

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 ) , использует "естественный " синтаксис для рекурсивного вызова обычного метода, если известен указатель на объект - потомок. Заметим, что при каждом новом рекурсивном вызове вызываемый объект также становится текущим.