lab 6

#pragma once
using namespace std;

class ExTree {
public:
    string problem;
    ExTree(string str):problem(str) {};
};


template <class T>
class SearchTree
{
public:
    T data;                                   //ключ типа Т
    SearchTree* left;                         //указатель на левого потомка
    SearchTree* right;                        //указатель на правого потомка
    SearchTree* parent;                       //указатель на родителя
    SearchTree(T);                            //конструктор
    ~SearchTree();                            //деструктор
    void deleteSearchTree() { delete this; }  //удалить дерево
    void printSearchTree(int);                //горизонтальная печать дерева
    void inOrder(SearchTree<T>*);             //симметричный обход дерева
    void setData(T dt) { data = dt; }         //установить данные для узла
    SearchTree<T>* next();                    //найти следующий элемент
    SearchTree<T>* prev();                    //найти предыдущий элемент
    void insertNode(T);                       //добавить узел
    void deleteNode(T);                       //удалить узел
    SearchTree<T>* findElement(T);            //найти элемент
    SearchTree<T>* findMax();                 //найти максимальный элемент
    SearchTree<T>* findMin();                 //найти минимальный элемент

    void treeprint(SearchTree<T>*);           //печать
    SearchTree() {};
};

template <class T>//мой код
SearchTree<T>::SearchTree(T val)
{
    //parent->data = val;
    //parent=nullptr;
    /*if (parent == nullptr)
    {
        left = nullptr;
        right = nullptr;
        return;
    }
    parent->data = val;*/
    parent = this;
    parent->data = val;

}

template <class T>//мой код
SearchTree<T>::~SearchTree()
{
    deleteSearchTree();
}

template <class T>
SearchTree<T>* SearchTree<T>::findElement(T data)
{
    if ((this == NULL) || (data == this->data))//если ключ узла равен NULL или совпал с
        return this;                           //заданным ключом, то функция завершается,
                                               //возвращая заданный узел дерева
    if (data < this->data)
        return this->left->findElement(data);  //если заданный ключ меньше текущего
                                               //ключа, то функция вызывается рекурсивно,
                                               //но уже для левого поддерева заданного
    else return this->right->findElement(data);//узла, в противном случае элемент ищется
                                               //в правом поддереве заданного узла,
}  //до срабатывания начального if

template <class T>
SearchTree<T>* SearchTree<T>::findMin()     //поиск минимального элемента
{
    if (this->left == NULL) return this; //если указатель на узел слева равен NULL,
                                            //значит текущий элемент является минимальным
    return this->left->findMin();        //иначе рекурсивно вызывая функцию,
                                         //двигаемся по левым поддеревьям до тех пор,
                                         //пока указатель на узел слева не равен NULL
}

template <class T>
SearchTree<T>* SearchTree<T>::findMax()     //поиск максимального элемента
{
    if (this->right == NULL) return this;//если указатель на узел справа равен NULL,
                                            //значит текущий элемент является максимальн.
    return this->right->findMax();       //двигаемся по правым  поддеревьям до тех
                                      //пор, пока указатель на узел справа
                                            //не станет равным NULL
}

template <class T>
SearchTree<T>* SearchTree<T>::next()     //поиск следующего элемента
{
    SearchTree* tree = this;          //заданный узел запоминается во вспомогательный,
                                         //чтобы не перемещать его при поиске
    if (tree->right != NULL)          //если правое поддерево заданного узла сущ.,
        return tree->right->findMin();//то ищется минимальный элемент в этом
                        //правом поддереве (он и будет следующим
                                         //для заданного)
    SearchTree<T>* t = tree->parent;  //в противном случае, нужно двигаться
                                         //вверх до тех пор,
                                         //пока не встретится узел, для которого заданный
                                         //является левым дочерним узлом
    while ((t != NULL) && (tree == t->right))//пока узел является правым дочерним для своего
                             //родителя и родитель существует, выполняем цикл
    {
        tree = t;                   //запоминаем текущий узел
        t = t->parent;              //переходим к его родителю
    }
    return t;
}

template <class T>
SearchTree<T>* SearchTree<T>::prev()     //поиск предыдущего элемента
{
    SearchTree* tree = this;
    if (tree->left != NULL)
        return tree->left->findMax();
    SearchTree<T>* t = tree->parent;
    while ((t != NULL) && (tree == t->left))
    {
        tree = t;
        t = t->parent;
    }
    return t;
}

template <class T>
void SearchTree<T>::insertNode(T dt)
{
    SearchTree<T>* tree = this;
    //
    if(tree->findElement(dt)!=0)
    {
        throw ExTree("This value is existed already.");
    }
    //
    while (tree != NULL)               //пока узел существует выполняется цикл
    {                                  //если ключ добавляемого элемента
        if (dt >= tree->data)       //больше или равен ключу
        {                           //текущего узла, анализируется правое поддерево
            if (tree->right != NULL)  //если узел справа существует, происходит
            {                        //переход к нему и выполнение
                tree = tree->right;//цикла начинается сначала
            }
            else                   //иначе добавляем новый элемент в узел
            {                      //справа, настроив все необходимые указатели
                SearchTree<T>* t = new SearchTree<T>(dt);//для нового элемента
                t->parent = tree;
                tree->right = t;
                break;
            }
        }
        else if (dt < tree->data)     //если ключ добавляемого элемента меньше
        {                             //ключа текущего узла, анализируется
                                            //левое поддерево
            if (tree->left != NULL) //если узел слева существует, происходит
            {                      //переход к нему и выполнение цикла начинается
                tree = tree->left;// сначала
            }
            else                                        //иначе добавляется новый
            {                                              //элемент в узел слева,
                SearchTree<T>* t = new SearchTree<T>(dt);//настраиваются все
                t->parent = tree;                      //необходимые указатели
                tree->left = t;                        //для нового элемента
                break;
            }
        }
    }
}

template <class T>
void SearchTree<T>::treeprint(SearchTree<T>* p) {
    if (p != NULL) {
        treeprint(p->left);
        cout <<p->data << endl;
        treeprint(p->right);
    }
}