|
Читайте также: |
Примером структуры данных, обработка которой практически невозможна без использования рекурсии, является бинарное дерево. Бинарное дерево – это структура, состоящая из одного элемента, называемого корнем, который ссылается либо на два других непересекающихся бинарных дерева, корни которых называются потомкам и данного элемента, либо не ссылается никуда. Под непересекающимися деревьями понимаются деревья, не имеющие общих элементов и связей между собой. В общем случае элемент имеет произвольное число потомков, а такая структура называется деревом [36].
Деревом, например, является организация любой файловой системы, поддерживающей каталоги. А треугольник Паскаля деревом не является, поскольку в нём два элемента могут ссылаться на один.
Для краткости рассмотрим только бинарные деревья. Из определения следует, какую структуру имеет элемент:
typedef struct BINTREE
{
void* data;
struct BINTREE* left;
struct BINTREE* right;
} bintree;
Поле data отвечает за данные, хранящиеся в элементе, а left и right – за его потомков. В них могут быть либо собственно указатели на потомков, либо NULL.
Как же пройти такую сложную структуру, с учётом того, что элемент не имеет указателя на предыдущий? С помощью рекурсии это делается элементарно:
void traversal(bintree* root)
{
/*some actions*/
if(root->left) traversal(root->left);
if(root->right) traversal(root->right);
return;
}
Этот алгоритм создан непосредственно по определению дерева: если элемент не имеет потомков, то обход текущего дерева закончен, а если имеет – обойти потомков. Например, такая функция выводит дерево на экран:
void print(bintree* root)
{
printf("%d\n", *((int*)root->data));
if(root->left) print(root->left);
if(root->right) print(root->right);
return;
}
Если её вызвать для дерева, изображённого на рисунке, то программа выведет
Эту функцию можно «украсить» следующим образом:
void print(bintree* root, int deep)
{
printf("%*d\n", deep, *((int*)root->data));
if(root->left) print((root->left), ++deep);
--deep;
if(root->right) print((root->right), ++deep);
--deep;
return;
}
При рекурсивном вызове этой функции для потомка значение переменной deep увеличивается, а при возврате – уменьшается. Таким образом, с точностью до переданного при первом вызове значения, deep равно расстоянию от текущего элемента до корня. Поэтому вывод этой функции будет выглядеть так:
Это нагляднее отражает структуру дерева.
Поскольку между корнем дерева и любым его элементом должен существовать путь, удаление элемента ведёт к удалению всех его потомков. А значит, удаление также должно быть реализовано рекурсивно. Однако непосредственно удаление элемента является невозможным из-за отсутствия связи между элементом и его предком[37]. Так что функция удаления потомков элемента будет выглядеть следующим образом:
void rmrf(bintree* root)
{
if(root->left) rmrf(root->left); else return;
if(root->right) rmrf(root->right); else return;
if(!((root->left->left)||(root->left->right)))
{
free(root->left->data);
free(root->left);
root->left=NULL;
}
if(!((root->right->left)||(root->right->right)))
{
free(root->right->data);
free(root->right);
root->right=NULL;
}
}
Логика этой функции такова: если текущий элемент потомков не имеет, то сделать с ним ничего невозможно, текущий вызов функции завершается. Если он имеет потомков, но те потомков не имеют, то их можно удалять. Если же и у потомков есть потомки, то нужно к ним переходить.
Вызов этой функции для элемента root->left рассмотренного дерева превратит его в такое:
Дата добавления: 2015-11-13; просмотров: 92 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Лекция 9: связные списки. | | | Часть 3: динамическое программирование. |