Бинарное дерево поиска. Класс 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.

Также приложение содержит метод конвертирования дерева в отсортированный массив. Поэтому для сохранения массива вводятся две дополнительные переменные: массив и их размер.

Дерево бинарного поиска начинается с корня. В программе этому корню соответствует переменная с именем 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()
{
  ...
}

⇑

Связанные темы

⇑