Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Помогите с программой на С++. Под ОС Windows XP, Borland Builder 6 и Visual Studio 2005. Ответ нужен срочно .
Написать программу для работы по запросам оператора с упорядоченной таблицей,
реализованной в виде двоичного дерева поиска.

Ключ - целое число.Информация - строка произвольной длины.

Узел дерева содержит ключ,указатели на правое и левое поддеревья и указатель на информационное поле.

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

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


Примечания:
1.Программа должна содержать несколько функций;функция main должна выполнять: вывод меню, ввод и анализ ответа,вызов на исполнение требуемой функции;
2.В программе нужно предусмотреть проверку правильности ввода данных.
3.Оценить сложность реализованных алгоритмов.
4.(*) Для целей отладки реализовать форматированный вывод таблицы в виде дерева.
5.(*) Для целей отладки реализовать загрузку таблицы из файла в формате

- Ключ1
- Информация1
- Ключ2



Приложение:
похожая программа но тут

#include <iostream>

using namespace std;

typedef struct
{
char * key;
char * info;
void * pLeft;
void * pRight;
void * pParent;
} NODE;

typedef struct
{
NODE * pRoot;
} TREE;

char * message[] = { "1. Add new item", // включение нового элемента в таблицу без нарушения свойств упорядоченности
"2. Remove item", // удаление из таблицы элемента,заданного своим ключом,без нарушения свойств упорядоченности таблицы
"3. Find item by key", // поиск информации по заданному ключу
"4. View", // вывод всего содержимого таблицы в прямом порядке следования ключей,превышающих заданное значение ключа.если ключ не указан,то всей таблицы
"5. Find item by part of key", // поиск элемента соответствующего значению ключа совпадающего с заданным по первым N символам
"6. Get max difference", // вернуть максимальную разницу высот в дереве.
"7. Exit" }; // выход

int MesCount = sizeof( message ) / sizeof( message[0] );

void AddItem( TREE & tree );
void RemoveItem( TREE & tree );
void FindAt( TREE & tree );
void View( TREE & tree );
void FindByPartOfKey( TREE & tree );
void PrintMaxDifference( TREE & tree );
void Exit( TREE & tree );

int ViewMenu();
int GetNum();

void Init( TREE & tree );

NODE * CreateNode( char * key, char * info );
NODE * GetAt( TREE tree, char * key );
NODE * GetNodeWithNextKey( NODE * pNode );
void InsertAt( TREE & tree, NODE * pNode );
void ReleaseNode( NODE * pNode );
void PrintNode( NODE * pNode, int offset );

void PrintNodeByKeyCompare( NODE * pNode, char * key );
int keycmp( char * str1, char * str2 );

void ( *func[] )( TREE & ) = { NULL, AddItem, RemoveItem, FindAt, View, FindByPartOfKey, PrintMaxDifference, Exit };

int main()
{
TREE tree;
int ret;

Init( tree );

do
{
ret = ViewMenu();
func[ret]( tree );
if ( ret == 7 )
break;
}
while ( ret );

return 0;
}

int ViewMenu()
{
int ret;
do
{
cout << "_________________________" << endl;
cout << endl << "Please, select:\n";
for ( int i = 0; i < MesCount; i++ )
cout << message[i] << endl;
cout << "_________________________" << endl;
ret = GetNum();
}
while ( ret < 1 || ret > MesCount );
return ret;
}

int GetNum()
{
int a;
cin >> a;
while ( !( cin.good() || cin.eof() ) || ( a < 0 ) )
{
cout << "Wrong value!" << endl;
cin.clear();
cin.ignore();
cin >> a;
}
return a;
}

// Функция добавления элемента.
void AddItem( TREE & tree )
{
NODE * pNode;
char key[256];
char info[256];
cout << "Please, enter the key: ";
cin >> key;
if ( GetAt( tree, key ) )
{
cout << "Error: Key collision!" << endl;
return;
}
cout << "please, enter the information: ";
cin >> info;
pNode = CreateNode( key, info );
InsertAt( tree, pNode );
}

// Функция удаления элементам по его ключу.
void RemoveItem( TREE & tree )
{
char key[256];
NODE * pNode, * pParent, * pTemp, * pMin;
cout << "Please, enter the key: ";
cin >> key;
if ( ( pNode = GetAt( tree, key ) ) == NULL )
{
cout << "can not found element with the key = " << key << endl;
return;
}

pParent = ( NODE* ) pNode->pParent;
pTemp = NULL;

if ( !pNode->pLeft )
pTemp = ( NODE* ) pNode->pRight;
else if ( !pNode->pRight )
pTemp = ( NODE* ) pNode->pLeft;

if ( pTemp )
{
pParent = ( NODE* ) pNode->pParent;
if ( pParent )
{
if ( pParent->pLeft == pNode )
{
pParent->pLeft = pTemp;
pTemp->pParent = pParent;
}
else if ( pParent->pRight == pNode )
{
pParent->pRight = pTemp;
pTemp->pParent = pParent;
}
}
else if ( pNode == tree.pRoot )
{
tree.pRoot = pTemp;
pTemp->pParent = NULL;
}

if ( pNode->info )
delete [] pNode->info;
if ( pNode->key )
delete [] pNode->key;
delete [] pNode;
return;
}

pMin = ( NODE* ) pNode->pRight;
if ( pMin )
{
while ( pMin->pLeft )
pMin = ( NODE* ) pMin->pLeft;

pMin->pLeft = ( NODE* ) pNode->pLeft;
( ( NODE* ) pNode->pLeft )->pParent = pMin;

pTemp = ( NODE* ) pMin->pParent;

if ( pTemp != pNode )
{
if ( pTemp->pLeft == pMin )
{
pTemp->pLeft = pMin->pRight;
if ( pMin->pRight )
( ( NODE* ) pMin->pRight )->pParent = pTemp;
}
else
{
pTemp->pRight = pMin->pRight;
if ( pMin->pRight )
( ( NODE* ) pMin->pRight )->pParent = pTemp;
}
pMin->pRight = pNode->pRight;
( ( NODE* ) pNode->pRight )->pParent = pMin;
}
if ( pParent )
{
if ( pParent->pLeft == pNode )
{
pParent->pLeft = pMin;
pMin->pParent = pParent;
}
else
{
pParent->pRight = pMin;
pMin->pParent = pParent;
}
}
}
else
{
pParent = ( NODE* ) pNode->pParent;
if ( pParent )
{
if ( pParent->pRight == pNode )
pParent->pRight = NULL;
else
pParent->pLeft = NULL;
}
}
if ( pNode == tree.pRoot )
{
tree.pRoot = pMin;
if ( pMin )
pMin->pParent = NULL;
}
if ( pNode->info )
delete [] pNode->info;
if ( pNode->key )
delete [] pNode->key;
delete [] pNode;
return;
}

// Функция вывода элемента по его ключу.
void FindAt( TREE & tree )
{
NODE * pNode;
char key[256];
cout << "Please, enter the key: ";
cin >> key;
if ( ( pNode = GetAt( tree, key ) ) == NULL )
{
cout << "can not found element with the key = " << key << endl;
return;
}
cout << "information: " << pNode->info << endl;
}

// Функция отображения всех элементов дерева.
void View( TREE & tree )
{

NODE * pNode;

int ret;
do
{
cout << "View all tree - 1" << endl;
cout << "View all nodes after the key - 2" << endl;
ret = GetNum();
}while ( ret != 1 && ret != 2 );

if ( ret == 1 )
{
pNode = tree.pRoot;
if ( !pNode )
{
cout << endl << "Tree is empty!" << endl;
return;
}
while ( pNode->pLeft )
pNode = ( NODE* ) pNode->pLeft;
cout << pNode->key << " ";
}
else
{
char key[256];
cout << "Please, enter the key: ";
cin >> key;
pNode = GetAt( tree, key );
if ( !pNode )
{
cout << "can not found element with the key = " << key << endl;
return;
}
}

while ( pNode = GetNodeWithNextKey( pNode ) )
cout << pNode->key << " ";
cout << endl;

cout << endl << endl;

int offset = 0;
PrintNode( tree.pRoot, offset );
cout << endl;
}

// Функция выводит все найденные элементы, ключи которых частично совпадают с заданным.
void FindByPartOfKey( TREE & tree )
{
char key[256];
cout << "Please, enter the key: ";
cin >> key;
PrintNodeByKeyCompare( tree.pRoot, key );
cout << endl;
}

// Функция выводит максимальную разницу в уровнях между минимальным и максимальным элементами.
void PrintMaxDifference( TREE & tree )
{
NODE * pNode;
int level1 = 0, level2 = 0, delta;
pNode = tree.pRoot;
while ( pNode = ( NODE* ) pNode->pLeft )
level1++;
pNode = tree.pRoot;
while ( pNode = ( NODE* ) pNode->pRight )
level2++;
if ( level2 > level1 )
delta = level2 - level1;
else if ( level1 > level2 )
delta = level1 - level2;
else
delta = 0;
cout << "max difference is = " << delta << endl;
}

// Выход из программы.
void Exit( TREE & tree )
{
ReleaseNode( tree.pRoot );
}

// Функция загрузки дерева из файла "load.txt".
void Init( TREE & tree )
{
char str[256], key[256], info[256];

memset( &tree, 0x00, sizeof( TREE ) );
FILE * pFile = fopen( "../load.txt", "r" );
if ( !pFile )
{
cout << "can not open file!" << endl;
return;
}
for ( int cntr = 1; fscanf( pFile, "%s", str ) != -1; cntr++ )
{
if ( cntr % 2 != 0 )
strcpy( key, str );
else
strcpy( info, str );

if ( strlen( key ) && strlen( info ) && cntr > 1 )
{
if ( GetAt( tree, key ) == NULL )
{
NODE * pNode = CreateNode( key, info );
InsertAt( tree, pNode );
info[0] = '\0';
key[0] = '\0';
}
}
}
cout << "loading from file complete" << endl;
fclose( pFile );
}

// Функция создания нового элемента.
NODE * CreateNode( char * key, char * info )
{
NODE * pNode;

pNode = ( NODE* ) new NODE;
memset( pNode, 0x00, sizeof( NODE ) );
if ( key )
{
pNode->key = new char[strlen( key )+1];
strcpy( pNode->key, key );
}
if ( info )
{
pNode->info = new char[strlen( info )+1];
strcpy( pNode->info, info );
}
return pNode;
}

// Функция возвращает указатель на элемент по его ключу.
NODE * GetAt( TREE tree, char * key )
{
if ( !tree.pRoot )
return NULL;
NODE * pNode = tree.pRoot;
while ( pNode )
{
int res = keycmp( pNode->key, key );
if ( res < 0 )
pNode = ( NODE* ) pNode->pRight;
else if ( !res )
return pNode;
else
pNode = ( NODE* ) pNode->pLeft;
}
return NULL;
}

// Функция возвращает указатель на элемент со следующим по значению ключём.
NODE * GetNodeWithNextKey( NODE * pNode )
{
NODE * pNext;
pNode = ( NODE* ) pNode;
if ( pNode->pRight != NULL )
{
pNext = ( NODE* ) pNode->pRight;
while ( pNext->pLeft )
pNext = ( NODE* ) pNext->pLeft;
return pNext;
}
pNext = ( NODE* ) pNode->pParent;
while ( pNext && pNext->pRight == pNode )
{
pNode = pNext;
pNext = ( NODE* ) pNode->pParent;
}
return pNext;
}

// Функция добавления нового элемента.
void InsertAt( TREE & tree, NODE * pNode )
{
NODE * pTemp, * pPrev;
if ( !tree.pRoot )
{
tree.pRoot = pNode;
return;
}
pTemp = tree.pRoot;
while ( pTemp )
{
pPrev = pTemp;
int res = keycmp( pTemp->key, pNode->key );
if ( res < 0 )
pTemp = ( NODE* ) pTemp->pRight;
else if ( res > 0 )
pTemp = ( NODE* ) pTemp->pLeft;
}
int res = keycmp( pPrev->key, pNode->key );
if ( res < 0 )
pPrev->pRight = ( void* ) pNode;
else
pPrev->pLeft = ( void* ) pNode;
pNode->pParent = ( void* ) pPrev;
}

// Функция освобождения динамической памяти, занятой элементом и всему дочерними элементами.
void ReleaseNode( NODE * pNode )
{
if ( pNode )
{
if ( pNode->pRight )
ReleaseNode( ( NODE* ) pNode->pRight );
if ( pNode->pLeft )
ReleaseNode( ( NODE* ) pNode->pLeft );
if ( pNode->key )
delete [] pNode->key;
if ( pNode->info )
delete [] pNode->info;
delete [] pNode;
}
}

// Рекурсивная функция печати элемента и всех его дочерних элементов.
void PrintNode( NODE * pNode, int offset )
{
if ( pNode )
{
PrintNode( ( NODE* ) pNode->pRight, offset + 1 );
for ( int i = 0; i < offset; i++ )
cout << " ";
cout << pNode->key << endl;
PrintNode( ( NODE* ) pNode->pLeft, offset + 1 );
}
}

// Функция отображения элементов со значениями ключей совпадающими с заданным ключём по первым N символам.
void PrintNodeByKeyCompare( NODE * pNode, char * key )
{
if ( pNode )
{
PrintNodeByKeyCompare( ( NODE* ) pNode->pRight, key );
if ( pNode->key == strstr( pNode->key, key ) )
cout << pNode->key << " ";
PrintNodeByKeyCompare( ( NODE* ) pNode->pLeft, key );
}
}

// Функция сравнения двух ключей в текстовом формате.
int keycmp( char * str1, char * str2 )
{
if ( str1 && str2 )
return atoi( str1 ) - atoi( str2 );
return 0;
}