1

Тема: Сортування та пошук по бінарному дереву

І знову бінарне дерево "Телефонний довідник" . Завдання - пошук записів за телефонним номером та фамілією.
Ще раз нагадаю. Є структура:

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 () (за номером). Але якось так виходить, що  перший запис в нове дерево записується, а інші - ні...

По другому варіанту в загалі не розумію як зупинити рекурсію та повернути потрібний знайдений елемент :/

Ось таке питаннячко. І ще, взагалі, я правильно розмірковую? Чи може вирішення цього питання лежить зовсім в другій площині, про яку я поки що не здогадуюсь?

Заздалегідь дякую  *DRINK*

2 Востаннє редагувалося koala (29.07.2014 15:16:38)

Re: Сортування та пошук по бінарному дереву

1. 1. Користуйтеся спойлерами. Наприклад,

void Tree::Insert(Subscriber * z)

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;
}

значно красивіше за ваше.

2. Ось вам пошук з рекурсією:

Subscriber * Tree::Search(Subscriber * Node, char * k)
{
  if( Node == 0 )
    return 0;
  if( strcmp(k, Node->Number) == 0 )
    return Node;
  Subscriber      
    *result = Search( Node->left , k );
  if( result == 0 )
     result = Search( Node->right, k );
  return result;
}

Звісно, це можна структурувати і скоротити, але так ніби найочевидніше, що воно робить.

Подякували: Faltfromoss1

3

Re: Сортування та пошук по бінарному дереву

koala написав:

Звісно, це можна структурувати і скоротити, але так ніби найочевидніше, що воно робить.

Дійсно, працює. Все так просто... Я щось перемудрив із сортуванням... В черговий раз дякую  *YES*

4

Re: Сортування та пошук по бінарному дереву

Ще одне невеличке питання. В класі Tree є метод для редагування даних абонента:

int Tree::ChangeData (Subscriber * z, int flag)

int Tree::ChangeData (Subscriber * z, int flag)
{
    Subscriber * New = new Subscriber;
    Copy (New, z);        // копируем данные из переданной структуры в новую 
    Del (z);            // и удаляем z из дерева. Далее работаем с новой структурой, которую в конце импортируем в дерево
    char buffer [1024];
    int temp;
    switch (flag)
    {
    case '1':
        system ("cls");
        cout<<endl<<"\t\t\tИзменение данных абонента"<<endl<<"\t\t\t\""<<New->FIO<<"\""<<endl<<endl;
        cout<<"\tВведите фамилию, имя, отчество абонента:"<<endl<<endl<<"\t\t";
        gets_s (buffer);
        if (strlen (buffer) >= sizeof (New->FIO))  // проверка введенной строки, не превышает ли предел массива структуры
        {
            Insert(New);
            return 1;
        } 
        strcpy (New->FIO, buffer);
        cout<<endl<<"\tВведите год рождения абонента: ";
        cin>>temp;
        if (temp < 0 || temp > 2014)
        {
            Insert(New);
            return 2;
        }
        New->YearOfBirth = temp;
        cin.ignore(cin.rdbuf()->in_avail());    //очистка буфера после cin>>
        cout<<endl<<"\tВведите город проживания абонента: ";
        gets_s (buffer);
        if (strlen (buffer) >= sizeof (New->Town))
        {
            Insert(New);
            return 1;
        }
        strcpy (New->Town, buffer);
        cout<<endl<<"\tВведите номер телефона абонента: ";
        gets_s (buffer);
        if (strlen (buffer) >= sizeof (New->Number))
        {
            Insert(New);
            return 1;
        }
        strcpy (New->Number, buffer);
        Insert(New);
        return 0;
    case '2':
        system ("cls");
        cout<<endl<<"\t\t\tИзменение ФИО абонента"<<endl<<"\t\t"<<New->FIO<<endl<<endl;
        cout<<endl<<endl<<"\tВведите фамилию, имя, отчество абонента:"<<endl<<"\t";
        gets_s (buffer);
        if (strlen (buffer) >= sizeof (New->FIO))
        {
            Insert(New);
            return 1;
        }
        strcpy (New->FIO, buffer);
        Insert(New);
        return 0;
    case '3':
        system ("cls");
        cout<<endl<<"\t\t\tИзменение года рождения абонента"<<endl<<"\t\t"<<New->FIO<<endl<<endl;
        cout<<endl<<"\tВведите год рождения абонента: ";
        cin>>temp;
        if (temp < 0 || temp > 2014)
        {
            Insert(New);
            return 2;
        }
        New->YearOfBirth = temp;
        cin.ignore(cin.rdbuf()->in_avail());
        Insert(New);
        return 0;
    case '4':
        system ("cls");
        cout<<endl<<"\t\t\tИзменение города проживания абонента"<<endl<<"\t\t"<<New->FIO<<endl<<endl;
        cout<<endl<<"\tВведите город проживания абонента: ";
        gets_s (buffer);
        if (strlen (buffer) >= sizeof (New->Town))
        {
            Insert(New);
            return 1;
        }
        strcpy (New->Town, buffer);
        Insert(New);
        return 0;
    case '5':
        system ("cls");
        cout<<endl<<"\t\t\tИзменение номера телефона абонента"<<endl<<"\t\t"<<New->FIO<<endl<<endl;
        cout<<endl<<"\tВведите номер телефона абонента: ";
        gets_s (buffer);
        if (strlen (buffer) >= sizeof (New->Number))
        {
            Insert(New);
            return 1;
        }
        strcpy (New->Number, buffer);
        Insert(New);
        return 0;
    }
}

При побудові вирішення, компілятор видає попередження

warning C4715: Tree::ChangeData: значение возвращается не при всех путях выполнения

Я вже все передивився, ретурни стоять де тільки можна, що йому ще треба не можу зрозуміти.

5 Востаннє редагувалося koala (29.07.2014 16:22:25)

Re: Сортування та пошук по бінарному дереву

Підказка: а якщо flag буде дорівнювати 0, що поверне функція?
І взагалі - пишіть структурні програми. Якщо треба вийти в певному сенсі надзвичайній ситуації - знайдено складношуканий результат чи сталася помилка - тоді так, ставте return. А у вас все заплутано.
Крім того, перед (майже?) усіма return у вас Insert(New). Це - яскравий приклад порушення принципу DRY.

6

Re: Сортування та пошук по бінарному дереву

koala написав:

Підказка: а якщо flag буде дорівнювати 0, що поверне функція?

Це ви, мабуть, на відсутність default натякали. Справді, його не вистачало, тепер компілятор не свариться.

І взагалі - пишіть структурні програми. Якщо треба вийти в певному сенсі надзвичайній ситуації - знайдено складношуканий результат чи сталася помилка - тоді так, ставте return. А у вас все заплутано.
Крім того, перед (майже?) усіма return у вас Insert(New). Це - яскравий приклад порушення принципу DRY.

Ну ідея така - за першим кейсом змінюються одразу всі дані, за іншими - по кожному полю окремо.

А Insert я використовую при кожній зміні для того, щоб змінений елемент став на своє нове місце в дереві, а не залишився на старому. Бо так порушиться структура бінарного дерева.

І що таке принцип DRY я, нажаль, не знаю  *DONT_KNOW*

7 Востаннє редагувалося koala (29.07.2014 16:49:39)

Re: Сортування та пошук по бінарному дереву

Базові принципи якісного програмування: DRY, KISS та YAGNI.
Вам буде краще тут ввести додаткову зміну, типу errorCode, і в гілках виставляти її значення, а наприкінці функції зробити

Insert(New);
return errorCode;