По аналогичной схеме дерево обходится и при поиске элемента, первого в дереве удовлетворяющего заданному условию. В качестве условия используется функция типа bool, указатель на которую передаётся функции обхода дерева.
Функциональное описание
- Рекурсивная функция определения высоты поддерева
int depth (tree *node)
Конец рекурсивного спуска происходит, когда текущий узел не имеет сыновей. Приэтом условии функция возвращает 1. Если сыновья есть - идёт вызов функции для каждого, при этом если у какого-то поддерева высота оказалась больше остальных, она запоминается. Возвращается максимальная высота среди поддеревьев + 1.
- Рекурсивная функция вставки в дерево
void insert (tree* node, void *data)
Если у текущего узла находится NULL среди указателей на поддеревья, то указатель перенаправляется на вновь создаваемый узел. У нового узла все указатели на поддеревья приравниваются NULL, а указатель на данные приравнивается аргументу функции data. Если у текущего узла все поддеревья непустые, находится высота каждого из них, и вставка рекурсивно спускается в то поддерево, высота которого минимальна.
- Нажатие на кнопку "Вставить"
void __fastcall TForm1::Button1Click(TObject *Sender)
Происходит проверка - не пусто ли дерево. Если это так, создаётся корень дерева, указатель на него заносится в глобальную переменную-указатель на дерево. Все поддеревья корня помечаются как пустые (NULL), а указатель на данные перенаправляется на динамически созданную копию введённой строки. Если дерево не пусто, также в области динамической памяти создаётся копия введённой строки, указатель на которую передаётся функции вставки. Вставка вызывается для корня дерева.
- Рекурсивная функция вывода содержимого дерева
void print (tree *node)
Для текущего узла происходит вывод данных (строки) в поле вывода. После этого для каждого непустого поддерева рекурсивно вызывается та же функция.
- Нажатие на кнопку "Вывод дерева"
void __fastcall TForm1::Button3Click(TObject *Sender)
Поле вывода очищается, и, если дерево не пусто, вызывается функция вывода для корня дерева.
- Проверка длины строки
bool moren (void *in)
Переданный указатель рассматривается как указатель строки; если длина этой строки не меньше 10, возвращается true, иначе - false.
- Итератор FirstThat - поиск в дереве первого удовлетворяющего условию узла
void *firstthat (tree *node, bool (*condi)(void *))
Переданной с помощью указателя функции проверки выполнения условия передаётся строка из текущего узла. Если условие выполнено, функция возвращает эту строку. Если нет - происходит рекурсивный вызов функции для каждого из непустых поддеревьев. Первый найденный узел, удовлетворяющий заданному условию порождает цепочку рекурсивных возвратов, функция возвращает строку, найденную в поддереве. Если строка, удовлетворяющая условию не найдена, возвращается NULL.
- Нажатие на кнопку "Поиск 1-го"
void __fastcall TForm1::Button2Click(TObject *Sender)
Для корня вызывается итератор FirstThat, результат сохраняется во вспомогательную переменную. Если результат - строка, она выводится, если NULL - выводится сообщение о неудаче.
Работа с контрольным примером, вывод
- Поочерёдно вводятся строки:
"1", "22", "333", "xxxxxxxxxxxxx", "4444", "qqqqqqqqqqqqq", "55555", "4444", "7777777"
- Вывод содержимого дерева даёт следующий результат:
1
22
qqqqqqqqqqqqq
333
55555
xxxxxxxxxxxxx
4444
4444
7777777
- Поиск первой строки, содержащей не менее 10 символов даёт:
qqqqqqqqqqqqq
Использование указателей на функции очень удобно при реализации универсальных программ хранения и обработки данных - каждая функция (вывод, сортировка, поиск) реализуется один раз в общем виде, для каждого типа данных дописываются специфичные функции (сравнение, …). Использованная в этой программе структура данных удобна для программирования, так как имеет рекурсивную природу, экономична (минимизирует высоту дерева), вставка не перестраивает дерево, однако не позволяет эффективно реализовать такие важные функции как поиск, сортировка.
Исходный код
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
// Структура дерева
struct tree
{
void *data; // Указатель на данные
struct tree *son[4]; // Массив указателей на поддеревья
} *T;
__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { }
// Рекурсивная функция определения высоты поддерева
int depth (tree *node)
{
int cur, max = 0;
if (!node->son[0] && !node->son[1] && !node->son[2] && !node->son[3])
return 1; // Если нет сыновей, высота = 1
for (int i = 0; i < 4; i++) // Если есть - проход по сыновьям
if (node->son[i]) // с определением их высот
{ // и запоминанием максимальной
cur = depth(node->son[i]);
if (cur > max)
max = cur;
}
return max + 1; // Высота больше высоты сына
}
// Рекурсивная функция вставки в дерево
void insert (tree* node, void *data)
{
tree *next; // Сюда будем вставлять
for (int i = 0; i < 4; i++) // Если есть "пустой" сын,
{ // Вставляем на это место
if (!node->son[i])
{
node->son[i] = new tree; // Cоздание нового узла
for (int j = 0; j < 4; j++) // У него нет сыновей
node->son[i]->son[j] = NULL;
node->son[i]->data = data; // Запись данных
return;
}
}
next = node->son[0]; // Начинаем поиск с первого сына
for (int i = 1; i < 4; i++)
{
if (depth(node->son[i]) < depth(next))
next = node->son[i]; // Выбираем сына с наименьшей высотой
}
insert(next, data); // Рекурсивный спуск в выбранного сына
}
// Нажатие на кнопку "Вставить"
void __fastcall TForm1::Button1Click(TObject *Sender)
{
if(!T) // Если дерево ещё не создано
{ // Оно создаётся,
T = new tree;
for(int i = 0; i < 4; i++) // Новое дерево не имеет сыновей
T->son[i] = NULL;
char *str = new char[strlen(Edit1->Text.c_str())+1];
strcpy(str, Edit1->Text.c_str());
T->data = str; // Запись данных
return;
}
char *str = new char[strlen(Edit1->Text.c_str())+1];
strcpy(str, Edit1->Text.c_str()); // Выделение памяти и запись строки
insert(T, (void *) str);// Если дерево есть - вставка в него указателя
}
// Рекурсивная функция вывода содержимого дерева
void print (tree *node)
{
Form1->Memo1->Lines->Add((char *) node->data); // Вывод строки
for (int i = 0; i < 4 && node->son[i]; i++) // Проход по сыновьям
print(node->son[i]); // Рекурсивный спуск - вывод сыновей
}
// Нажатие на кнопку "Вывод дерева"
void __fastcall TForm1::Button3Click(TObject *Sender)
{
Memo1->Clear(); // Очистка поля вывода
if (T) // Если дерево не пусто,
print(T); // Вывод, начиная с корня
}
// Проверка: длина строки >= len?
bool moren (void *in) // На входе - указатель на строку
{
if (strlen((char *) in) >= 10) // Длина строки - больше 10,
return true; // возврат true
else
return false; // иначе - false
}
// Итератор FirstThat - поиск в дереве первого удовлетворяющего условию узла
// На входе - указатель на узел дерева и указатель на функцию-условие
void *firstthat (tree *node, bool (*condi)(void *))
{
void *first = NULL; // Временное хранение результата
if ((*condi)(node->data)) // Проверка условия
return node->data; // При выполнении - вызврат данных
for (int i = 0; i < 4 && node->son[i]; i++)
{ // Иначе - проход по сыновьям
first = firstthat(node->son[i], condi);
if (first) // Если для одного из сыновей условие
return first; // выполнено - возврат данных
}
return NULL; // Условие не выполнено ни в одном узле
}
// Нажатие на кнопку "Поиск 1-го"
void __fastcall TForm1::Button2Click(TObject *Sender)
{
void *first = firstthat(T, &moren); // Поиск с помощью итератора
if (first) // Если узел найден -
ShowMessage((char *) first); // вывод данных
else // Иначе - сообщение о неудаче
ShowMessage("Строка длиной не менее 10 символов не найдена.");
}
Курсовые 
RSS
