1.1. Определение глубины дерева

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

struct tree{

int val;

tree *p[4];

};

//---- Определение ветви минимальной длины

int MinLnt(tree *q){

if (q==NULL) return 0;

int min= MinLnt(q->p[0]);

for (int i=1; i< 4; i++){

int x=MinLnt(q->p[i]);

if (x < min) min=x;}

return min+1;}

Для отслеживания процесса " погружения" достаточно дополнительной переменной, которая уменьшает свое значение на 1 при очередном рекурсивном вызове.

//------Включение вершины в дерево на заданную глубину

int Insert(tree *ph, int v, int d) { // d - текущая глубина включения

if (d == 0) return 0; // Ниже не просматривать

for ( int i=0; i< 4; i++)

if (ph->p[i] == NULL){

tree *pn=new tree;

pn->val=v;

for (int j=0; j< 4; j++) pn ->p[j]=NULL;

ph->p[i]=pn;

return 1; }

else

if (Insert(ph->p[i], v , d-1)) return 1; // Вершина включена

return 0; }

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

void main(){ tree PH={ 1,{NULL,NULL,NULL,NULL} };

for (int i=0; i< 100; i++) Insert( & PH, rand( 20 ), MinLnt( & PH));

}

1.2. Операции поиска и включения элемента в дерево

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

//---- Поиск в дереве строки, длиной больше заданной

struct stree{

char *str;

stree *p[4];};

char *big_str(stree *q){

if (q==NULL) return NULL;

if (strlen(q->str)> 5) return q->str; // Найдена в текущей вершине

for (int i=0; i< 4; i++){

char *child=big_str(q->p[i]); // Получение строки от потомка

if (child!=NULL) return child; // Вернуть ее " от себя лично"

}

return NULL;} // Нет ни у себя, ни у потомков

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

//---- Поиск максимального в дереве

int GetMax(tree *q){

if (q==NULL) return -1;

int max=q->val;

for (int i=0; i< 4; i++){

int x=GetMax(q->p[i]);

if (x > max) max=x;}

return max;}

1.3. Оптимизация поиска в дереве

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

//--- Дерево оптимизацией : короткие ключи ближе к началу

struct dtree{

char *key; // Ключевое слово

void *data; // Искомая информация

dtree *p[4]; }; // Потомки

void *find(dtree *q, char *keystr) // Поиск по ключу

{ void *s;

if (q==NULL) return NULL;

if (strcmp(q->key,keystr)==0) return q->data; // Ключ найден

if (strlen(keystr)<strlen(q->key))

return NULL; // Короткие строки - ближе к корню

for (int i=0; i< 4; i++)

if ((s=find(q->p[i],keystr))!=NULL) return s;

return NULL; }

Функция включения в такое дерево ради сохранения свойств должна в каждой проходимой ею вершине рекурсивно " вытеснять" более длинную строку в поддерево и заменять ее на текущую (новую), более короткую.