C++ : Алгоритмы - Бинарное дерево поиска. Часть I

Наконец-то у меня появилось время, чтобы продолжить заниматься своим блогом. На сей раз я представлю вам цикл статей, в котором буде повествоваться про одну из самых известных, ну и, я так думаю, самую простую структуру "из самых сложных" - Бинарное дерево поиска.

Деревья - это вообще интересная вещь. Если рассмотреть уже построеное дерево, то оно реально оправдывает свое название - оно реально похоже на дерево...только перевёрнутое=). Но это не мешает ему иметь корень - самую верхнюю вершину, с которой и начинается все дерево, листья - это самые  нижние вершины. Так же можно увидеть сходство и генеалогическим деревом - в нем есть родители, дети, братья etc..

Если посмотреть на это дерево, то корнем(его ещё называют root) будет узел 20, а, например, узел 38 имеет 2х детей - 37 и 43, и отца - узел 20. Братом для этого узла будет узел 7. 

Можно ещё очень долго рассуждать про генеалогическую структуру этого дерева...Но я не буду=)

Поэтому сразу переходим к реализации  на C++ с использованием шаблонов(про них тоже будет статья, но позже..)

Итак собственно структура :

template <typename TypeOfTree>

       struct BinaryTree

       {

             BinaryTree(const TypeOfTree& initData)

                :field(initData),leftPointer(nullptr),rightPointer(nullptr)

             {}

             BinaryTree<TypeOfTree>* leftPointer;

             BinaryTree<TypeOfTree>* rightPointer;

             TypeOfTree field;

            

       };

У нас есть поле с даными(с помощью шаблонов может принимать любой тип), а также указатели на левое и правое дитё. Конструктор с 1 параметром инициализирует их всех.

На основе этой структуры был создан класс для реализации методов, которые, в свою очередь, будут реализовать операции над деревом. Ниже листинг :

template <typename TypeOfTree>

class MainBinaryTree

{

public:

       MainBinaryTree(){rootOfTree = nullptr;}

       ~MainBinaryTree();

       void InsertElement(const TypeOfTree& dataToInsert);//главная функция добавления элементов в дерево

    std::string ParenthesisREC() const;

       bool FindReturnBool(const TypeOfTree& dataToInsert) const;

       BinaryTree<TypeOfTree>* FindReturnPointer(const TypeOfTree& dataToInsert) const;

       void Order(int indef);//Обходы

       void tempOrderAcess();//вывод обходов на экран

       void FindMinMax();//поиск минимального и максимального значения в дерева

       int NumberOfElements() const;//количество элементов

       int HeightOfTree() const;//высота дерева

       void DeleteNode(const TypeOfTree& dataToDelete);//удаление элемента

       bool IsEmpty();

       BinaryTree<TypeOfTree>* FindParent(const TypeOfTree& dataToFind) const;//нахождение отца узла

            

protected :

       BinaryTree<TypeOfTree>* rootOfTree;

       //Вспомагательная функция для удаления дерева

       void _MainBinaryTree(BinaryTree<TypeOfTree>* element);

       //обьявление вспомагательной функции добавления элементов

       void _InsertElement(BinaryTree<TypeOfTree>* element, const TypeOfTree& dataToInsert);

       //Вспомагательная функция для вывода дерева на консоль

       std::string _ParenthesisREC(BinaryTree<TypeOfTree>* element) const;

       //Вспомагательная функция для поиска елемента(true/false)

       bool _FindReturnBool(BinaryTree<TypeOfTree>* element,const TypeOfTree& dataToInsert) const;

       //Вспомагательная функция для поиска елемента(pointer)

       BinaryTree<TypeOfTree>* _FindReturnPointer(BinaryTree<TypeOfTree>* element, const TypeOfTree& dataToInsert) const;

       //Обходы

       std::vector<TypeOfTree> tempOrder;

       void _PreOrder(BinaryTree<TypeOfTree>* element);//прямой

       void _PostOrder(BinaryTree<TypeOfTree>* element);//обратный

       void _InOrder(BinaryTree<TypeOfTree>* element);//централизированый

       void _BreadthFirstSearch();//в ширину

       BinaryTree<TypeOfTree>* _FindParent(BinaryTree<TypeOfTree>* element, const TypeOfTree& dataToFind) const;

       int _NumberOfElements(BinaryTree<TypeOfTree>* element) const;

       int _HeightOfTree(BinaryTree<TypeOfTree>* element) const;

       void _DeleteNode(BinaryTree<TypeOfTree>* element,const TypeOfTree& dataToDelete);//

      

};

Про эти методы я расскажу позже. Пока это всё.