Деревья
Определение дерева имеет исключительно рекурсивную природу. Элемент этой структуры данных называется вершиной. Дерево представляет собой либо отдельную вершину, либо вершину, имеющую ограниченное число указателей другие деревья (ветвей). Нижележащие деревья для текущей вершины называются поддеревьями, а их вершины -потомками. По отношению к потомкам текущая вершина называется предком.
Вершину дерева можно определить таким образом:
struct tree
{
int val; // Значение элемента
tree *child[4]; // Указатели на потомков
};
Из определения элемента дерева следует только тот факт, что он имеет ограниченное число указателей на подобные элементы. Как и во всех динамических структурах данных характер связей между элементами определяется функциями, которые их устанавливают. В данном случае рекурсивное определение дерева требует и рекурсивного характера функций, работающих со связями. Простейшей функцией является функция обхода всех вершин дерева:
//------------------------------------------------------bk55-02.cpp
//------Рекурсивный обход дерева
void ScanTree(tree *p)
{
int i;
if (p == NULL) return; // следующей вершины нет
for (i=0; i< 4; i++) // рекурсивный обход
ScanTree(p->child[i]); // потомков с передачей
} // указателей на них
Само дерево обычно задается в программе указателем на его главную вершину. Часто обход дерева используется для получения информации, которая затем возвращается через результат рекурсивной функции. Так работает, например, функция определения максимальной глубины дерева:
//------------------------------------------------------bk55-03.cpp
//------Минимальная длина ветвей дерева
int M inDepth(tree *p)
{ int i, m in, nn;
if (p == NULL) return 0; // следующей вершины нет
for (min = MinDepth(p->child[0], i=1; i< 4; i++)
{ // обход потомков
nn = MinDepth(p->child[i]);
if (nn > max) max = nn;
} // возвращается глубина с
return min + 1; // учетом текущей вершины
}
Другой достаточно тривиальной процедурой является включение нового элемента в дерево.
Для примера рассмотрим функцию включения нового элемента в качестве потомка к вершине, максимально близкой к началу. Здесь есть проблема, общая для всех деревьев и рекурсивных алгоритмов. Войдя в поддерево, невозможно производит какие-либо действия для вершин, расположенных на том же уровне, но в других поддеревьях. Поэтому задача решается так : используется функция включения с просмотром дерева на заданную глубину, а сама глубина просмотра, в свою очередь, задается равной длине минимальной ветви дерева.
//------------------------------------------------------bk55-04.cpp
//------Включение вершины в дерево на заданную глубину
int Insert(tree *ph, int v, int d)
// результат логический - вершина включена
// ph - указателя на текущую вершину
// d - текущая глубина включения
{
if (d == 0) return 0; // Ниже не просматривать
for ( int i=0; i< 4; i++)
if (ph- >child[i] == NULL)
{
tree *pn=new tree;
ph->child[i]=pn;
pn->val=v;
for (i=0; i< 4; i++) p n->child[i]=NULL;
return 1;
}
else
if (Insert(ph->child[i], v , d-1)) return 1;
return 0;
}
void main()
{
tree PH={ 1,{NULL,NULL,NULL,NULL}}; // пример вызова функции
Insert( &PH, 5, MinDepth( &PH));
}
Здесь впервые всплывает на поверхность свойство дерева, ради которого оно, собственно говоря, и используется. Оно соответствует пословице " Дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогрессии. Отсюда следует, как можно эффективно использовать деревья для поиска данных : если включать в вершины дерева данные таким образом, что наиболее часто используемые будут располагаться ближе к корню, и при этом анализ текущий вершин позволит сделать вывод о том, стоит ли " опускаться" в поддеревья. Рассмотрим пример. Допустим, дерево, каждая вершина которого содержит строку, организовано так, что самая короткая строка в поддереве находится в корневой вершине. Тогда при поиске слова в дереве будет соблюдаться принцип - чем оно короче, тем меньше вершин будет просмотрено.
//------------------------------------------------------bk55-05.cpp
struct tree1
{
char *key; // Ключевое слово
char *data; // Искомая информация
tree1 *child[4]; // Потомки
};
char *find(tree1 *ph, char *keystr)
{ char *s;
if (ph==NULL) return NULL;
if (strcmp(ph->key,keystr)==0) return ph->data;
// Вершина найдена
if (strlen(keystr)<strlen(ph->key)) return NULL;
// Короткие строки - ближе к корню
for (int i=0; i< 4; i++)
if ((s=find(ph->child[i],keystr))!=NULL) return s;
return NULL;
}
Функция включения в такое дерево ради сохранения свойств дерева при включении новой строки должна " вытеснять" более длинные строки из текущих вершин в поддеревья и заменять их на новые, более короткие.
