Бінарне дерево пошуку. Клас BinaryTree. Цілі числа. Числа можуть повторюватись

У даній роботі наведено приклад розробки класу, який реалізує дерево бінарного пошуку для цілих чисел (int). За подібним зразком можна розробляти інші класи, які реалізують дерево бінарного пошуку.

Зміст

Пошук на інших ресурсах:

1. Умова задачі

Розробити клас дерева бінарного пошуку, який містить наступні методи (API класу):

BinaryTree() – конструктор – створює пусте дерево;
void ShowSorted(string msg) – відображає елементи дерева у посортованому вигляді;
void Put(int value) – додає елемент до дерева;
~BinaryTree() – деструктор (звільняє пам’ять);
int Get(int value) – повертає к-сть входжень елемента в дерево. Якщо елементу немає, повертається 0;
int Size() – повертає кількість елементів у дереві;
int* ToSortedArray() – конвертує дерево в посортований масив;
void Show(string msg) – вивести дерево у довільному порядку;
BinaryTree(const BinaryTree& obj) – конструктор копіювання;
BinaryTree& operator=(const BinaryTree& obj) – оператор копіювання.

⇑

2. Розв’язок. Текст програми

Для розв’язку задачі вибрано спосіб рекурсивного виклику базових методів класу.

2.1. Оголошення класу BinaryTree

На початку оголошується пустий клас BinaryTree

#include <iostream>
using namespace std;

// Дерево бінарного пошуку
class BinaryTree
{

};

⇑

2.2. Структура Node

Вузол дерева описується структурою, яка зображена на рисунку 1.

Рисунок 1. Схематичне зображення вузла дерева бінарного пошуку

Програмний код вузла Node наступний

class BinaryTree
{
private:
  struct Node
  {
    int value;
    int count;
    Node* left;
    Node* right;
  };
};

⇑

2.3. Ввід внутрішніх полів класу

Дерево бінарного пошуку починається з кореня. У програмі цьому кореню відповідає змінна з іменем root.

Також програма містить метод конвертування дерева в посортований масив. Тому для збереження масиву вводяться дві додаткові змінні: масив та його розмір.

class BinaryTree
{
private:

  ...

  Node* root; // корінь дерева
  int* A;     // дерево у вигляді посортованого масиву
  int size;   // розмір масиву

  ...

};

⇑

2.4. Конструктор BinaryTree()

У конструкторі створюється дерево, яке не містить ніяких елементів.

class BinaryTree
{
  ...

  public:
    // Конструктор - створює пусте дерево
    BinaryTree()
    {
      root = nullptr;
      A = nullptr;
      size = 0;
    }
};

⇑

2.5. Метод Put(Node*, int)

У методі Put() реалізується додавання нового елементу до дерева. Метод має дві перевантажені реалізації

private:
  Node* Put(Node* x, int value);

public:
  void Put(int value);

Перша реалізація у розділі private – це безпосереднє додавання елементу шляхом рекурсивного виклику функції Put(). Друга реалізація у розділі public є доступною для клієнтського коду і звертається до першої реалізації.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  Node* Put(Node* x, int value)
  {
    if (x == nullptr)
    {
      // Створити вузол і повернути його
      Node* p = new Node;
      p->value = value;
      p->count = 1;
      p->left = nullptr;
      p->right = nullptr;
      return p;
    }

    if (value == x->value)
    {
      x->count++;
      return x;
    }

    if (value < x->value)
    {
      x->left = Put(x->left, value);
      return x;
    }

    if (value > x->value)
    {
      x->right = Put(x->right, value);
      return x;
    }
  }

public:
  // Додає елемент до дерева
  void Put(int value)
  {
    // Викликати рекурсивну функцію
    if (root == nullptr)
      root = Put(root, value);
    else
      Put(root, value);
  }
};

⇑

2.6. Метод ShowSorted(Node*)

Метод ShowSorted() має приховану (private) та загальнодоступну (public) реалізацію

private:
  void ShowSorted(Node* x);

public:
  void ShowSorted(string msg)

Текст реалізацій методу наступний:

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  // Відображення дерева в посортованому вигляді
  void ShowSorted(Node* x)
  {
    if (x == nullptr) return;
    if (x->left != nullptr)
      ShowSorted(x->left);

    cout << x->value << ":" << x->count << "  ";

    if (x->right != nullptr)
      ShowSorted(x->right);
  }

public:

  ...

  void ShowSorted(string msg)
  {
    cout << msg << " => ";
    ShowSorted(root);
    cout << endl;
  }
};

⇑

2.7. Метод Free(Node*)

Рекурсивний метод Free() викликається з деструктора та оператора присвоєння копіюванням.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  // Метод, що звільняє пам'ять, виділену під масив
  void Free(Node* x)
  {
    if (x == nullptr)
      return;
    if (x->left != nullptr)
      Free(x->left);
    if (x->right != nullptr)
      Free(x->right);
    delete x;
  }
};

⇑

2.8. Деструктор

// Дерево бінарного пошуку
class BinaryTree
{

  ...

public:
  // Деструктор
  ~BinaryTree()
  {
    // Звільнити дерево
    Free(root);

    // Звільнити масив A, якщо він існує
    if (size > 0)
      delete[] A;
  }
};

⇑

2.9. Метод Get(int)

Метод Get() призначений для визначення кількості входжень елементу в дереві. Якщо метод повертає 0, то це означає, що елементу в дереві немає. Як і всі інші подібні методи класу, метод перевантажений двома реалізаціями: загальнодоступною (public) та прихованою (private). Прихована реалізація визначає елемент шляхом рекурсивного виклику методу.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  Node* Get(Node* x, int value)
  {
    if (x == nullptr)
      return nullptr;
    if (value < x->value)
      return Get(x->left, value);
    else
    if (value > x->value)
      return Get(x->right, value);
    else
      return x;
  }

public:

...

  // Повертає к-сть входжень елементу в дереві
  int Get(int value)
  {
    Node* p = Get(root, value);
    if (p == nullptr)
      return 0;
    return p->count;
  }
};

⇑

2.10. Метод ToSortedArray()

Метод ToSortedArray() призначений для конвертування дерева в посортований масив. Масив створюється в динамічній пам’яті з допомогою оператора new. Внутрішнє поле класу з іменем A є покажчиком на масив. Розмір масиву визначає поле size.

Метод ToSortedArray() має дві перевантажені реалізації відповідно у розділах private та public.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  // Перетворення з бінарного дерева в посортований масив
  void ToSortedArray(Node* x, int* current)
  {
    if (x == nullptr)
      return;

    if (x->left != nullptr)
      ToSortedArray(x->left, current);

    // Врахувати count
    for (int i = 0; i < x->count; i++)
    {
      A[*current] = x->value;
      (*current)++;
    }

    if (x->right != nullptr)
      ToSortedArray(x->right, current);
  }

public:
  // Конвертує дерево в посортований масив
  const int* ToSortedArray()
  {
    // 1. Отримати розмір масиву і виділити пам'ять
    size = Size();
    A = new int[size];
    size = 0;
    ToSortedArray(root, &size);
    return A;
  }
};

⇑

2.11. Метод Copy(Node**, Node*)

Однією з операцій над деревом є отримання копії цього дерева. З цією метою, в клас вводиться спеціальний метод Copy(). Цей метод є внутрішнім і викликається з конструткора копіювання та оператора присвоєння копіюванням.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  // Функція копіювання *x_copy <= x
  void Copy(Node** x_copy, Node* x)
  {
    if (x == nullptr)
      return;

    // Зробити копію комірки
    *x_copy = new Node;
    (*x_copy)->value = x->value;
    (*x_copy)->count = x->count;
    (*x_copy)->left = nullptr;
    (*x_copy)->right = nullptr;

    // Перейти на наступні рівні
    Copy(&(*x_copy)->left, x->left);
    Copy(&(*x_copy)->right, x->right);
  }

  ...
};

⇑

2.12. Конструктор копіювання BinaryTree(const BinaryTree&)

Конструктор копіювання є технічною складовою класу і необхідний у випадках, коли потрібно отримати копію об’єкту коли він ініціалізацується значенням іншого об’єкту.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

public:

  ...

  // Конструктор копіювання
  BinaryTree(const BinaryTree& obj)
  {
    Copy(&root, obj.root);
  }

  ...

};

⇑

2.13. Оператор копіювання operator=(const BinaryTree& obj)

Оператор копіювання виконує ту ж функцію що і конструктор копіювання. Тільки в цьому випадку приймаючий об’єкт вже існує і він перевизначається іншим об’єктом.

// Дерево бінарного пошуку
class BinaryTree
{
  ...

public:

  ...

  // Оператор копіювання
  BinaryTree& operator=(const BinaryTree& obj)
  {
    if (this != &obj) // чи немає присвоєння самому собі
    {
      // Звільнити попередньо виділену пам'ять
      Free(root);

      // Скопіювати дані
      Copy(&root, obj.root);
    }
    return *this;
  }
};

⇑

2.14. Метод Show(). Вивести елементи дерева у довільному порядку

Особливим випадком виведення дерева, є його вивід у тому порядку як в ньому сформовані елементи в напрямку зверху вниз. Це є довільний порядок, який визначений вхідною послідовністю, яка формує дерево.

Метод має дві реалізації. Перша – прихована реалізація, яка реалізує безпосередньо вивід. Друга реалізація є загальнодоступною і може бути викликана з клієнтського коду.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  // Функція, що виводить дерево у довільному порядку
  void Show(Node* x)
  {
    if (x == nullptr)
      return;

    // Вивести елемент
    cout << x->value << ":" << x->count << "  ";

    // Перейти на наступні вузли
    Show(x->left);
    Show(x->right);
  }

public:

  ...

  // Вивести дерево у довільному порядку
  void Show(string msg)
  {
    cout << msg << " => ";
    Show(root);
  }
};

⇑

2.15. Метод Size(). Розмір дерева

Метод Size() повертає кількість елементів у дереві. Як і всі попередні методи, цей метод має приховану та загальнодоступну реалізацію.

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  int Size(Node* x)
  {
    if (x == nullptr) return 0;
    int count = 0;
    if (x->left != nullptr)
      count = count + Size(x->left);
    if (x->right != nullptr)
      count = count + Size(x->right);
    return count + x->count;
  }

public:

  ...

  // Повертає к-сть елементів у дереві
  int Size()
  {
    return Size(root);
  }
};

// Дерево бінарного пошуку
class BinaryTree
{
private:

  ...

  int Size(Node* x)
  {
    if (x == nullptr) return 0;
    int count = 0;
    if (x->left != nullptr)
      count = count + Size(x->left);
    if (x->right != nullptr)
      count = count + Size(x->right);
    return count + x->count;
}

⇑

3. Тест. Функція main()

У функції main() можна проводити тест роботи дерева.

void main()
{
  // Створити дерево без елементів
  BinaryTree BT;

  // Додати до дерева елементи
  BT.Put(10);
  BT.Put(8);
  BT.Put(8);
  BT.Put(17);
  BT.Put(11);
  BT.Put(11);
  BT.Put(11);
  BT.Put(23);
  BT.Put(5);
  BT.Put(12);

  // Вивести дерево у посортованому вигляді
  BT.ShowSorted("BT");

  // Тест конструктора копіювання
  BinaryTree BT2 = BT;
  BT2.ShowSorted("BT2");

  // Тест оператора копіювання
  BinaryTree BT3;
  BT3 = BT2;
  BT3.Show("BT3");

  // Конвертувати дерево в масив
  const int* A = BT3.ToSortedArray();

  // Вивести посортований масив
  cout << endl;
  for (int i = 0; i < BT3.Size(); i++)
    cout << A[i] << "  ";
  cout << endl;
}

⇑

4. Скорочений код програми

Нижче наведено скорочений код всіх функцій класу з їх оголошеннями без реалізації.

#include <iostream>
using namespace std;

// Дерево бінарного пошуку
class BinaryTree
{
private:
  struct Node
  {
    ...
  };

  Node* root; // корінь дерева
  int* A;     // дерево у вигляді посортованого масиву
  int size;   // розмір масиву

  Node* Put(Node* x, int value)
  {
    ...
  }

  // Відображення дерева в посортованому вигляді
  void ShowSorted(Node* x)
  {
    ...
  }

  // Метод, що звільняє пам'ять, виділену під масив
  void Free(Node* x)
  {
    ...
  }

  Node* Get(Node* x, int value)
  {
    ...
  }

  int Size(Node* x)
  {
    ...
  }

  // Перетворення з бінарного дерева в посортований масив
  void ToSortedArray(Node* x, int* current)
  {
    ...
  }

  // Функція копіювання *x_copy <= x
  void Copy(Node** x_copy, Node* x)
  {
    ...
  }

  // Функція, що виводить дерево у довільному порядку
  void Show(Node* x)
  {
    ...
  }

public:
  // Конструктор - створює пусте дерево
  BinaryTree()
  {
    ...
  }

  void ShowSorted(string msg)
  {
    ...
  }

  // Додає елемент до дерева
  void Put(int value)
  {
    ...
  }

  // Деструктор
  ~BinaryTree()
  {
    ...
  }

  // Повертає к-сть входжень елементу в дереві
  int Get(int value)
  {
    ...
  }

  // Конвертує дерево в посортований масив
  const int* ToSortedArray()
  {
    ...
  }

  // Повертає к-сть елементів у дереві
  int Size()
  {
    ...
  }

  // Вивести дерево у довільному порядку
  void Show(string msg)
  {
    ...
  }

  // Конструктор копіювання
  BinaryTree(const BinaryTree& obj)
  {
    ...
  }

  // Оператор копіювання
  BinaryTree& operator=(const BinaryTree& obj)
  {
    ...
  }
};

void main()
{
  ...
}