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

Итак, продолжим..

Вторая статья про Бинарные деревья поиска. Будем реализовывать метод для вставки элементов в дерево, то есть, создание самого дерева.

Чуть-чуть за саму вставку. Деревья - это не списки, хотя чуть похожи. Поэтому и вставка будет кардинально отличатся от добавления элемента в простой список.

Добавление первого элемента в дерево простое. При добавлении же второго элемента мы должны посмотреть на значение корня: если же добавляемое значение меньше, чем значение корня, то добавляем вставляемый элемент в левое поддерево(то есть присваиваем левому указателю корня новый обьект структуры). Если же второй вставляемый элемент больше, чем значение корня, то добавляем узел в правое поддерево.




 Использовать будем конечно же шаблоны, а также рекурсию. Ниже листинг 2х методов :

//главная функция добавления элементов в дерево

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::InsertElement(const TypeOfTree& dataToInsert) {

       //если корня, тоисть дерева нет)

       if (rootOfTree == nullptr)

             //..то создаем его

             rootOfTree = new BinaryTree<TypeOfTree>(dataToInsert);

       else

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

             _InsertElement(rootOfTree, dataToInsert);

}

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

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::_InsertElement(BinaryTree<TypeOfTree>* element, const TypeOfTree& dataToInsert) {

       //если добавляемый элемент меньше поля соответствующего корня..

       if (element->field > dataToInsert)

             if (element->leftPointer == nullptr)

                           element->leftPointer = new BinaryTree<TypeOfTree>(dataToInsert);

             else

                    _InsertElement(element->leftPointer, dataToInsert);

       else

             if (element->rightPointer == nullptr)

                    element->rightPointer = new BinaryTree<TypeOfTree>(dataToInsert);

             else

                    _InsertElement(element->rightPointer, dataToInsert);

}

Ясное дело, нам нужно вывести на экран результаты своих трудов=) Я предпочёл самый простой способ - скобочную запись дерева. Ниже листинг:

//Листинг функции вывода в скобочном виде

template <typename TypeOfTree>

std::string MainBinaryTree<TypeOfTree>::ParenthesisREC() const {

        #ifdef DEBUG

         cout << "true";

     #endif

       return _ParenthesisREC(rootOfTree);

}

template <typename TypeOfTree>

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

       if (element) {

             std::ostringstream ss;

             ss << element->field;

             if (!element->leftPointer && !element->rightPointer)

                    return ss.str();

             else

                    return ss.str() + "(" + _ParenthesisREC(element->leftPointer) +_ParenthesisREC(element->rightPointer) + ")";

       }

       else

             return "_";

}

Для набора значений 22 14 31 7 17 9 скобочная запись будет выглядеть так: 

 22(14(7(_9)17)31), где корень 22, а листья - 9, 17 и 31