А при создании дочерних квадратов элементы родительского надо распределить по дочерним или они остаются там, где были?

При создании дочерних квадратов, каждый элемент "отвечает" только за свою четверть?
Другими словами, мы добавляем четыре квадрата только если KeyX и KeyY попадают в разные четверти.
Если же надо разместить элемент в квадрат, где уже что-то есть, то тогда дробим, создаем дочерние. Так?

При создании дочерних (в родительский было записано N элементов). Элементы не распределяются в дочерние(остаются там где были). В дочерние добавляются новые элементы...То Есть каждый узел содержит элементы.

Только при переполнении родительского квадрата (записано N элементов) создаем пустые дочерние. В каждый дочерний записываются элементы в соответствии с границами X , Y. Границы расчитываются в соответствии с рисунком.

Пример: Предположим N=2, в корневой каталог записали элементы с ключами (1,2), (30,60)- он переполнен, создаются дочерние квадраты. Далее записываем ключи (0,35),(25,45) -( по рисунку они будут в крайнем левом дочернем квадрате), при этом этот квадрат переполнен, создаются дочерние для него. Далее если пишем элемент (60,60)- он будет в крайнем правом дочернем для корневого.
Большое спасибо.

Вам требуется программа именно на С++ (с классами) или устроит на чистом С?

На С будет просто отлично. Заранее большое спасибо

Заменил структуры классами, что в С++ практически одно и то же. Если нужны дополнительные комментарии - говорите.

А можно пример со структурой(которая дана в задании)?

Можно слово class заменить на struct, например. Поля данных, которые есть в задании есть и в классах. Все работает. Или условие настолько жесткое, что не приемлет вариантов?

Да, нет просто хотелось бы, чтобы без классов. Как в чистом С.

Оно можно, конечно, без классов. Только вряд ли будет удобнее для использования и сопровождения. Да и логика работы будет хуже прослеживаться.

Здравствуйте!
Подправленная программа с сортировкой
[code h=200]#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

const int N=4; //Количество элементов в одном квадрате
const int M=4; //Количество квадратов
const int MAX_X=100; //Максимальное значение по Х
const int MAX_Y=100; //Максимальное значение по Y
const int COUNT=50; //Число элементов

struct element
{
int keyX; //Ключ 1
int keyY; //Ключ 2
char *info; //Информация
};

//Узел дерева
struct Node
{
int minX; //Нижняя граница X
int maxX; //Верхняя граница X
int minY; //Нижняя граница Y
int maxY; //Верхняя граница Y
Node *child[M]; //Массив указателей на поддеревья
element *inf[N]; //Массив указателей на элементы
};

//рекурентная п/п освобождения памяти, занятой деревом
//параметр - адрес узла
void TreeFree(Node * node)
{
int i;

//по всем элементам узла
for (i=0; i<N; i++)
{
//сначала проверим, есть ли элемент
if (node->inf[i])
{
//есть ли поле info
if (node->inf[i]->info)
delete [] node->inf[i]->info;
//освобождаем память элемента
delete node->inf[i];
}
}
//по всем поддеревьям
for (i=0; i<M; i++)
{
//проверим, есть ли поддерево
if (node->child[i])
//вызываем себя же с адресом поддерева
TreeFree(node->child[i]);
}
//освобождаем память узла
delete node;
}

//п/п инициализации корня дерева
//параметр - адрес адреса корня
void TreeInit(Node ** node)
{
//запрашиваем память под корень
*node = new (Node);
ZeroMemory(*node, sizeof Node) ;


//зададим максимальные значения (минимальные = 0)
(*node)->maxX = MAX_X;
(*node)->maxY = MAX_Y;
}

//п/п добавления M пустых поддеревьев
//параметр - адрес узла
void TreeNodesInsert(Node * node)
{
//запрашиваем память сразу под все M=4 поддерева
for (int i=0; i<M; i++)
{
node->child[i] = new Node;
ZeroMemory(node->child[i], sizeof Node) ;
}

//пропишем минимальные и максимальные значения
node->child[0]->minX = node->child[2]->minX = node->minX;
node->child[1]->minX = node->child[3]->minX =
node->child[0]->maxX = node->child[2]->maxX = (node->maxX + node->minX)/2;
node->child[1]->maxX = node->child[3]->maxX = node->maxX;

node->child[0]->minY = node->child[1]->minY = node->minY;
node->child[2]->minY = node->child[3]->minY =
node->child[0]->maxY = node->child[1]->maxY = (node->maxY + node->minY)/2;
node->child[2]->maxY = node->child[3]->maxY = node->maxY;
}

//рекурентная п/п вставки нового элемента в дерево
//параметры: адрес узла и значения x, y, info для нового элемента
void TreeInsert(Node * node, int NewKeyX, int NewKeyY, char *NewInfo)
{
int i;
char sBuf[32];

//просмотрим, есть ли место, куда записать в элементы текущего узла
//по всем элементам узла
for (i=0; i<N; i++)
{
//пустое ли место
if (NULL == node->inf[i])
{
//запросим память под элемент
node->inf[i] = new (element);
//заполним информацией
node->inf[i]->keyX = NewKeyX;
node->inf[i]->keyY = NewKeyY;
//под строку надо на 1 больше, чем длина (под 0)
node->inf[i]->info = new char[strlen(NewInfo)+1];
strcpy(node->inf[i]->info, NewInfo);
//задача выполнена - выходим
return;
}
else
{ //сравним
if ((NewKeyX < node->inf[i]->keyX) ||
((NewKeyX == node->inf[i]->keyX) && (NewKeyY < node->inf[i]->keyY)))
{ //меньше текущего - меняем местами
//x
NewKeyX ^= node->inf[i]->keyX;
node->inf[i]->keyX ^= NewKeyX;
NewKeyX ^= node->inf[i]->keyX;

//y
NewKeyY ^= node->inf[i]->keyY;
node->inf[i]->keyY ^= NewKeyY;
NewKeyY ^= node->inf[i]->keyY;

//строки
strcpy(sBuf, node->inf[i]->info); //сохраним старую
delete [] node->inf[i]->info; //удаляем старую
node->inf[i]->info = new char [strlen(NewInfo)+1]; //создаем строку
strcpy(node->inf[i]->info, NewInfo);//копируем новую
strcpy(NewInfo, sBuf); //старую на место новой

//после обмена ищем, куда вставлять уже взятую из базы...
}
}

}

//все уже заполнено
//проверим, есть ли поддеревья на данном уровне
//достаточно проверить только 0-й квадрат (или все, или ни одного)
if (NULL == node->child[0])
//добавляем поддеревья
TreeNodesInsert(node);

//самый интересный момент :)
//вычислим тндекс поддерева, как выражение (Y выше середины)*2 + (X правее середины),
//где (Y выше середины) и (X правее середины) - логические величины, равные 0 или 1
i = (NewKeyY >= (node->maxY + node->minY)/2)*2 +
(NewKeyX >= (node->maxX + node->minX)/2);

//вызываем себя же, чтобы вставить элемент в поддерево
TreeInsert(node->child[i], NewKeyX, NewKeyY, NewInfo);
}

//рекурентная п/п вывода дерева на экран в виде:
//[квадрат,]...[квадрат,]индекс элемента x = <value>, y = <value>, xmin, xmax, ymin, ymax
//x и y выводим, как ранее сформированную строку, хранимую в поле info
//параметры: узел и строка, содержащая строку с квадратами предыдущих уровней
void TreePrint(Node * node, char * sLevel)
{
int i;
//строка для хранения строки с квадратами для последующего вызова
char sLevelCurr[128];

//проходим по всем элементам уровня
for (i=0; i<M; i++)
{
//проверим на наличие
if (node->inf[i])
//выводим
printf("%s%d\t%s,\t\t%d\t%d,\t%d\t%d\n", sLevel, i, node->inf[i]->info,
node->minX, node->maxX, node->minY, node->maxY);
}
//пробежимся по поддеревьям
//только, если они есть
if (node->child[0])
{
//по всем
for (i=0; i<N; i++)
{
//добавим к строке пройденных квадратов текущий квадрат
sprintf(sLevelCurr, "%s%d,", sLevel, i);
//вызовем себя же для вывода поддерева
TreePrint(node->child[i], sLevelCurr);
}
}
}


//рекурентная п/п поиска в дерева элемента с заданными x и y
//параметры: узел, x, y, адрес переменной, куда запишется адрес узла с найденным элементом
//и адрес переменной, куда запишется индекс в массиве элементов
//возвращается 1, если элемент найден и 0, если не найден
bool TreeSearch(Node * node, int x, int y, Node ** pNode, int * pIdx)
{
int i;

//просмотрим массив элементов текущего узла
for (i=0; i<N; i++)
{
//проверим на существование и на совпадение x и y
if ((node->inf[i]) && (node->inf[i]->keyX == x) && (node->inf[i]->keyY == y))
{
//нашли!
*pNode = node; //возвратим адрес узла
*pIdx = i; //и индекс в массиве элементов
return 1; //элемент найден
}
}
//просмотрим поддеревья
for (i=0; i<M; i++)
{
//проверим на существование
if (node->child[i])
{
//вызовем себя же для проверки поддерева
if (TreeSearch(node->child[i], x, y, pNode, pIdx))
//если найдено, то выходим
return 1;
}
}
//не найден!
return 0;
}

//основная программа
int main(void)
{
Node *Root; //корень дерева
Node *Node; //адрес узла, используется для поиска
int i; //просто переменная цикла
int x, y; //переменные для для заполнения и поиска по дереву
int idx; //переменная для индекса в массиве индексов, используется для поиска
char string[32]; //строка для формирования поля info

//будем заполнять дерево случайными элементами
//инициализация последовательности псевдослучайных чисел
srand( (unsigned)time( NULL ) );

//создаем корень дерева
TreeInit(&Root);

//заполняем дерево
//предварительно проверяем на уникальность ключей поиском по дереву
for (i=0; i<COUNT; i++)
{
do
{
x = rand()%MAX_X;
y = rand()%MAX_Y;

//если найдется, то генерим новый элемент
}while (TreeSearch(Root, x, y, &Node, &idx));

//формируем строку для info
sprintf(string, "x = %d,\ty = %d", x, y);
//заносим в дерево
TreeInsert(Root, x, y, string);
}

//выведем все элементы дерева
printf("All elements of tree:\n\n");
//начинаем с корня, вторым параметром пустая строка, потому что
//для корня будем выводить только индексы в массиве элементов
TreePrint(Root, "");

//начинаем бесконечный цикл поиска в дереве введенных элементов
//для выхода из цикла необходимо ввести x >= 100
printf("\nSearch elements (Enter x>=100 for exit)...\n");

//циклим пока x < 100 (в начале x наверняка < 100)
while(x < MAX_X)
{
//вводим x
printf("\nEnter x: ");
scanf("%d",&x);
//ищем или выходим?
if (x < MAX_X)
{
//вводим y
printf("Enter y: ");
scanf("%d",&y);
//на всякий случай, найдем остаток от деления на 100
y %= MAX_Y;
//ищем
if (TreeSearch(Root, x, y, &Node, &idx))
{
//нашли - выводим
printf("%s,\t\t%d\t%d,\t%d\t%d\n", Node->inf[idx]->info,
Node->minX, Node->maxX, Node->minY, Node->maxY);
}
else
//не нашли
printf("Element not found\n");
}
}

//освободим память
TreeFree(Root);

return 0;
}
[/code]