Тема: Сортування та пошук по бінарному дереву
І знову бінарне дерево "Телефонний довідник" . Завдання - пошук записів за телефонним номером та фамілією.
Ще раз нагадаю. Є структура:
struct Subscriber
{
char FIO [50];
int YearOfBirth;
char Town [20];
char Number [15];
Subscriber * left, * right, * parent;
};
В класі Tree є функція, яка додає елемент до списку у визначеному порядку:
void Tree::Insert(Subscriber * z)
{
z->left = NULL;
z->right = NULL;
Subscriber * y = NULL;
Subscriber * Node = root;
while(Node != 0)
{
y = Node;
if(strcmp(z->FIO, Node->FIO) < 0)
Node = Node->left;
else
Node = Node->right;
}
z->parent = y;
if(y == 0)
root = z;
else if(strcmp(z->FIO, y->FIO) < 0)
y->left = z;
else
y->right = z;
}
А саме у алфавітному порядку за ФІО абонентів.
А також є функція пошуку:
Subscriber * Tree::Search(Subscriber * Node, char * k)
{
int n = strlen (k);
while(Node != 0 && strnicmp(k, Node->FIO, n) != 0)
{
if(strnicmp(k, Node->FIO, n) < 0)
Node = Node->left;
else
Node = Node->right;
}
return Node;
}
Пошук також реалізований за полем FIO, як і будувалося дерево. Тут питань немає, все знаходить, все працює.
Але в мене виникає питання, як в цьому дереві тепер організувати пошук за іншими полями? Як, неприклад, в завданні - за номером телефону? Адже дерево відсортовано за полем FIO і тепер якшо просто в функції Search () змінити параметри пошуку, то працювати належним чином вона не буде:
Subscriber * Tree::Search(Subscriber * Node, char * k)
{
while(Node != 0 && strcmp(k, Node->Number) != 0)
{
if(strcmp(k, Node->Number) < 0)
Node = Node->left;
else
Node = Node->right;
}
return Node;
}
В мене з'явилося дві ідеї
1) Відсортувати дерево спочатку за тим полем, за яким треба виконати пошук, і потім знайти запис
2) За допомогою рекурсії обійти все дерево із пошуком портібного значення.
По першому варіанту спробував зробити функцію сортування накшталт такої:
void Tree::Sort (Subscriber * Node, Tree & t)
{
if(Node != 0)
{
Sort(Node->left, t);
t.InsertNumber (Node);
Sort(Node->right, t);
}
}
Де аргумент, переданий у функцію Tree & t це тимчасово створене дерево, куди будуть записуватись відсортовані дані за допомогою функції InsertNumber () (за номером). Але якось так виходить, що перший запис в нове дерево записується, а інші - ні...
По другому варіанту в загалі не розумію як зупинити рекурсію та повернути потрібний знайдений елемент
Ось таке питаннячко. І ще, взагалі, я правильно розмірковую? Чи може вирішення цього питання лежить зовсім в другій площині, про яку я поки що не здогадуюсь?
Заздалегідь дякую