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


Двоичное дерево - часть 2


То есть, в отличие от списка, где this обозначал объект-заголовок, а для объектов - элементов списка в том же методе использовался другой указатель, в дереве для всех объектов - вершин используется один (но каждый раз свой) this .


int size()
{
if (data==NULL) return 0;
int n=1;
if (l!=NULL) n+=l-&#62size();
if (r!=NULL) n+=r-&#62size();
return n; }


void *btree::find(void *key, int(*cmp)(void*,void*))
{
if (data==NULL) return NULL;
int n=(*cmp)(key,data);
if (n==0) return data;
if (n &#60 0)
{
if (l!=NULL) return l-&#62find(key,cmp);
else return NULL;
}
else
{
if (r!=NULL) return r-&#62find(key,cmp);
else return NULL;
}
}

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


void * btree::operator[](int &#38n)
{
void *q;
if (data==NULL) return NULL;
if (l!=NULL) { q=(*l)[n]; if (q!=NULL) return q; }
if (n-- = 0) return data;
if (r!=NULL) { q=(*r)[n]; if (q!=NULL) return q; }
return NULL;
}

В приведенном фрагменте интересно выглядит рекурсивный вызов переопределенного оператора [ ]. Для этого нужно в синтаксисе вызова указать объект - потомок для текущего - это будет ( *l ) и для него выполнить указанную операцию [ ], то есть ( *l ) [n]. .

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




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