Удаление в бинарном дереве поиска

#pragma once
#include <iostream>
using namespace std;
template <class T>
class BinarySearchTree
{
private:
    // Описание структуры узла со ссылками на детей
    class Node {
    public:
        T key_; 
        Node* left_; 
        Node* right_;
        Node* p_;
        //_________________________ Конструктор узла
        Node(const T& key, Node* left = nullptr, Node* right = nullptr,
            Node* p = nullptr) :
            key_(key), left_(left), right_(right), p_(p)
        { }
    };
    // Дерево реализовано в виде указателя на корневой узел.
    Node* root_;
public:
    // Конструктор "по умолчанию" создает пустое дерево
    BinarySearchTree() : root_(nullptr)
    {}
    // Деструктор освобождает память, занятую узлами дерева
    virtual ~BinarySearchTree()
    {
        deleteSubtree(root_);
    }
    // Печать строкового изображения дерева в выходной поток out
    void print(ostream& out) const
    {
        printNode(out, root_);
        out << endl;
    }
    // Функция поиска по ключу в бинарном дереве поиска
    bool iterativeSearch(const T& key) const
    {
        return (iterativeSearchNode(key) != nullptr);
    }
    // Вставка нового элемента в дерево, не нарушающая порядка
    // элементов. Вставка производится в лист дерева
    void insert(const T& key)
    {
        if (root_ == nullptr)
        {
            root_ = new Node(key);
            return;
        }
        Node* prev, * current;
        current = root_;
        prev = current;
        while (current != nullptr)
        {
            prev = current;
            if (key < current->key_)
            {
                current = current->left_;
            }
            else if (key > current->key_)
            {
                current = current->right_;
            }
            else
            {
                return;
            }
        }
        Node* newNode = new Node(key);
        if (key < prev->key_)
        {
            prev->left_ = newNode;
            return;
        }
        else
        {
            prev->right_ = newNode;
            return;
        }
 
    }
    void insertRec(const T& key)
    {
        insertNodeRec(this->root_, key);
    }
    // Удаление элемента из дерева, не нарушающее порядка элементов
    void deleteKey(const T& key)
    {
        Node* current = this->iterativeSearchNode(key);
        Node* prev = this->parentSearch(key);
        //элемент не имеет наследников
        if (current->left_ == nullptr && current->right_ == nullptr)
        {
 
            if (prev->key_ > current->key_)
                prev->left_ = nullptr;
            else
                prev->right_ = nullptr;
            delete current;
        }
        //элемент имеет одного наследника
        else if (current->left_ != nullptr && current->right_ == nullptr)
        {
            Node* temp = current->left_;
            if (prev->key_ > current->key_)
                prev->left_ = temp;
            else
                prev->right_ = temp;
            delete current;
        }
        else if (current->right_ != nullptr && current->left_ == nullptr)
        {
            Node* temp = current->right_;
            if (prev->key_ > current->key_)
                prev->left_ = temp;
            else
                prev->right_ = temp;
            delete current;
        }
        //если элемент имеет двух наследников
        else if (current->left_ != nullptr && current->right_ != nullptr)
        {
            Node* keyNode = current;
            prev = current;
            current = current->right_;
            while (current->left_ != nullptr)
            {
                prev = current;
                current = current->left_;
            }
            if (current->right_ != nullptr)
                prev->left_ = current->right_;
            else
                prev->left_ = nullptr;
            T min = current->key_;
            keyNode->Node::key_ = min;
            delete current;
        }
    }
    // Определение количества узлов дерева
    int getCount() const
    {
        return getCountSubTree(this->root_);
    }
    // Определение высоты дерева
    int getHeight() const
    {
        return getHeightSubTree(this->root_);
    }
    // Вывод информации узла с заданным номером (индексом) в случае представления дерева как упорядоченного массива
    T getNode(const int index) const
    {
        Node* current = this->root_;
        while (current->left_ != nullptr)
        {
            current = current->left_;
        }
        for (int i = 1; i <= index; i++)
        {
            current = findTheFollowingNode(current->key_);
        }
        return current->key_;
    }
    // поиск элемента, следующего за указанным (наименьший из наибольших)
    T findTheFollowing(const T& key) const
    {
        return findTheFollowingNode(key)->key_;
    }
private:
    Node* findTheFollowingNode(const T& key) const
    {
        if (iterativeSearch(key) == 1)
        {
            Node* current = iterativeSearchNode(key);
            Node* prev = parentSearch(key);
            if (current->right_ == nullptr && prev->left_ == current)
                return prev;
            else
            {
                Node* result = current->right_;
                while (result->left_ != nullptr)
                {
                    result = result->left_;
                }
                return result;
            }
        }
        else
        {
            return root_;
        }
    }
    // Функция поиска адреса узла по ключу в бинарном дереве поиска
    Node* iterativeSearchNode(const T& key) const
    {
        if (root_ == nullptr)
            return root_;
        Node* current = root_;
        while (current != nullptr)
        {
            if (key < current->key_)
            {
                current = current->left_;
            }
            else if (key > current->key_)
            {
                current = current->right_;
            }
            if (current == nullptr || current->key_ == key)
            {
                return current;
            }
        }
    }
    //поиск родителя
    Node* parentSearch(const T& key) const
    {
        if (root_ == nullptr)
            return nullptr;
        Node* current = root_;
        Node* prev = current;
        while (current != nullptr)
        {
            if (key < current->key_)
            {
                prev = current;
                current = current->left_;
 
            }
            else if (key > current->key_)
            {
                prev = current;
                current = current->right_;
 
            }
            if (current == nullptr || current->key_ == key)
            {
                return prev;
            }
        }
    }
 
    int iterativeIndexSeacrh(const int index) const
    {
        int i = 0;
        if (root_ == nullptr)
            return 0;
        Node* current = root_;
        while (current->left_ != nullptr)
        {
            current = current->left_;
        }
 
    }
    // Рекурсивные функции, представляющие рекурсивные тела основных интерфейсных методов
    //
    // Рекурсивная функция для освобождения памяти
    void deleteSubtree(Node* node)
    {
        if (node == nullptr)
        {
            return;
        }
        else
        {
            if (node->left_ != nullptr)
                deleteSubtree(node->left_);
            if (node->right_ != nullptr)
                deleteSubtree(node->right_);
            delete node;
        }
    }
    // Рекурсивная функция определения количества узлов дерева
    int getCountSubTree(Node* node) const
    {
        if (node == nullptr)
            return 0;
        return (1 + getCountSubTree(node->left_) +
            getCountSubTree(node->right_));
    }
    // Рекурсивная функция определения высоты дерева
    int getHeightSubTree(Node* node) const
    {
        int h1 = 0, h2 = 0;
        if (node == nullptr)
            return 0;
        if (node->left_)
            h1 = getHeightSubTree(node->left_);
        if (node->right_)
            h2 = getHeightSubTree(node->right_);
        return(std::_Max_value(h1, h2) + 1);
    }
    // Рекурсивная функция для вывода изображения дерева в выходной поток
    void printNode(ostream& out, Node* root) const
    {
        // Изображение дерева заключается в круглые скобки.
        out << '(';
        if (root) {
            // Для узлов дерева должна быть определена (или переопределена)
            // операция вывода в выходной поток <<
            out << root->key_;
            printNode(out, root->left_);
            printNode(out, root->right_);
        }
        out << ')';
    }
    // Рекурсивная функция для организации обхода узлов дерева.
    void inorderWalk(Node* node) const
    {
 
    }
    // Рекурсивная функция для вставки узла
    void insertNodeRec(Node*& node, const T& key)const
    {
        if (node == nullptr)
        {
            node = new Node(key);
        }
        else
        {
            if (key < node->key_)
                insertNodeRec(node->left_, key);
            else if (key > node->key_)
                insertNodeRec(node->right_, key);
        }
    }
};

#include <iostream>
#include <string>
#include "BinarySearchTree.h"
int main()
{
  using std::cout;
 
  BinarySearchTree <int> intTree;
  // добавление узлов
  intTree.insert(10);
  //intTree.insert(3);
  intTree.insertRec(3);
  intTree.insert(20);
  intTree.insert(15);
  intTree.insert(30);
  intTree.insert(2);
  intTree.insert(5);
  //intTree.insert(32);
  //intTree.insert(22);
  intTree.print(cout);
  intTree.deleteKey(20);
 
  // Вывод узлов дерева в выходной поток
  intTree.print(cout);
 
  return 0;