Корректный вывод бинарного дерева поиска

#include <iostream>
#include <time.h>
 
 
 
//Структура данных "дерево"(двоичное дерево поиска) КЛЮЧИ если для каждой вершины значение ключи её левом поддервы меньше значения ключа этой вершины,  а ключи в правом больше
 
// прямой -- обходим корень, левый потомок, правый потомок
// симметричный -- левый потомок, корень, правый потомок
//обратный -- левый потомок, правый, корень
bool flag = true;
struct Node {
    int key;
    int counter;
    Node* pRight;
    Node* pLeft;
}*pRoot;
 
bool isEmpty(Node* ptr)
{
    if (ptr == NULL)
        return true;
    else
        return false;
}
 
bool isFull(Node* ptr)
{
    if (ptr == NULL)
    {
        std::cout << "Не удалось выделить память!\n";
        return true;
    }
    return false;
}
 
void initialization()
{
    pRoot = NULL;
}
 
Node* search(int x)  //поиск элемента
{
    Node* pCurrent = pRoot;
    bool stop = false;
    while ((pCurrent != NULL) & (!stop))
    {
        if (x < pCurrent->key)
            pCurrent = pCurrent->pLeft;
        else
        {
            if (x > pCurrent->key)
                pCurrent = pCurrent->pRight;
            else
                stop = true;
        }
    }
    return pCurrent;
}
 
void addNodeRecursive(Node* (&pCurrent), int keyN) //добавление рекурс
{
    if (pCurrent == NULL)
    {
        pCurrent = new (std::nothrow) Node;
        if (!(isFull(pCurrent)))
        {
            pCurrent->key = keyN;
            pCurrent->pLeft = NULL;
            pCurrent->pRight = NULL;
            pCurrent->counter = 1;
        }
        else
        {
            std::cout << std::endl << "Добавление вершины невозможно! Дерево поиска заполнено!" << std::endl;
            return;
        }
    }
    else
    {
        if (keyN < pCurrent->key)
            addNodeRecursive(pCurrent->pLeft, keyN);
        else if (keyN > pCurrent->key)
            addNodeRecursive(pCurrent->pRight, keyN);
        else
            pCurrent->counter += 1;
    }
}
 
void addNodeNonRecursive(int keyN)
{
    if (pRoot == NULL)
    {
        pRoot = new (std::nothrow) Node;
        if (!(isFull(pRoot)))
        {
            pRoot->pLeft = NULL;
            pRoot->pRight = NULL;
            pRoot->key = keyN;
            pRoot->counter = 1;
        }
        else
        {
            std::cout << std::endl << "Добавление вершины невозможно! Дерево поиска заполнено!" << std::endl;
            return;
        }
    }
    else
    {
        Node* pParent = NULL;
        Node* pCurrent = pRoot;
        while (pCurrent != NULL)
        {
            pParent = pCurrent;
            if (keyN < pCurrent->key)
                pCurrent = pCurrent->pLeft;
            else if (keyN > pCurrent->key)
                pCurrent = pCurrent->pRight;
            else
            {
                pCurrent->counter += 1;
                pCurrent = NULL;
            }
        }
        if (keyN < pParent->key)
        {
            pCurrent = new (std::nothrow) Node;
            if (!(isFull(pCurrent)))
            {
                pCurrent->key = keyN;
                pCurrent->pLeft = NULL;
                pCurrent->pRight = NULL;
                pCurrent->counter = 1;
                pParent->pLeft = pCurrent;
            }
            else
            {
                std::cout << std::endl << "Добавление вершины невозможно! Дерево поиска заполнено!" << std::endl;
                return;
            }
        }
        else if (keyN > pParent->key)
        {
            pCurrent = new (std::nothrow) Node;
            if (!(isFull(pCurrent)))
            {
                pCurrent->key = keyN;
                pCurrent->pLeft = NULL;
                pCurrent->pRight = NULL;
                pCurrent->counter += 1;
                pParent->pRight = pCurrent;
            }
            else
            {
                std::cout << std::endl << "Добавление вершины невозможно! Дерево поиска заполнено!" << std::endl;
                return;
            }
 
        }
    }
}
 
void showBackSymmetric(Node* pCurrent, int level)
{
    if (!(isEmpty(pRoot)))
    {
        if (flag) {
            std::cout << pRoot->key << " !!!!!" << std::endl;
            flag = false;
        }
        if (pCurrent != NULL)
        {
            level++;
            showBackSymmetric(pCurrent->pRight, level);
 
            for (int i = 0; i < level - 1; i++)
            {
                std::cout << "     ";
            }
            if (pCurrent->pLeft)
                std::cout << char(31);
            if (pCurrent->pRight)
                std::cout << char(30);
            std::cout << pCurrent->key << std::endl;
 
            showBackSymmetric(pCurrent->pLeft, level);
        }
    }
    else
        std::cout << "Дерево поиска пусто!" << std::endl;
}
 
void showInLine(Node* pCurrent, int level)
{
    if (!(isEmpty(pRoot)))
    {
        if (pCurrent != NULL)
        {
            level++;
            showInLine(pCurrent->pLeft, level);
            std::cout << pCurrent->key << "(" << pCurrent->counter << ")  ";
            showInLine(pCurrent->pRight, level);
        }
    }
    else
        std::cout << "Дерево поиска пусто!" << std::endl;
}
 
void changer(Node*& p, Node*& pTemp)
{
    if (p->pRight != NULL)
        changer(p->pRight, pTemp);
    else
    {
        pTemp->key = p->key;
        pTemp = p;
        p = p->pLeft;
    }
}
 
void deleteNode(Node*& pCurrent, int keyD)
{
    if (pCurrent == NULL)
    {
        std::cout << std::endl << "Удаляемая вершина отсутствует в дереве!" << std::endl;
        return;
    }
    else
    {
        if (keyD < pCurrent->key)
            deleteNode(pCurrent->pLeft, keyD);
        else
        {
            if (keyD > pCurrent->key)
                deleteNode(pCurrent->pRight, keyD);
            else
            {
                Node* pTemp = pCurrent;
                if (pTemp->pRight == NULL)
                    pCurrent = pTemp->pLeft;
                else
                {
                    if (pTemp->pLeft == NULL)
                        pCurrent = pTemp->pRight;
                    else
                        changer(pCurrent->pLeft, pTemp);
                }
                delete pTemp;
            }
        }
    }
}
 
int input() {
    int in;
    while (true) {
        std::cout << ">> ";
        std::cin >> in;
        if (std::cin.fail()) {
            std::cin.clear();
            std::cin.ignore(32767, '\n');
            std::cout << "\nОшибка. Введите корректное значение.\n";
            continue;
        }
        std::cin.ignore(32767, '\n');
        if (std::cin.gcount() > 1) {
            std::cout << "\nОшибка. Введите корректное значение.\n";
            continue;
        }
        break;
    }
    return in;
}
 
 
void menu()
{
    int choice;
    while (true)
    {
        std::cout << "__________________________________________________\n";
        std::cout << "Выберите действие:" << std::endl;
        std::cout << "1. Cоздание дерева с заданным числом вершин со случайными ключами" << std::endl;
        std::cout << "2. Поиск вершины с заданным значением ключа и количетсво появлений данного ключа" << std::endl;
        std::cout << "3. Добавление новой вершины (рекурсивно)" << std::endl;
        std::cout << "4. Добавление новой вершины (нерекурсивно)" << std::endl;
        std::cout << "5. Вывод дерева в обратно-симметричном порядке" << std::endl;
        std::cout << "6. Вывод всех вершин в порядке возрастания их ключей" << std::endl;
        std::cout << "7. Удаление вершины с заданным ключом" << std::endl;
        std::cout << "0. Выход из программы" << std::endl;
        choice = input();
        int userInput;
        if (choice == 1)
        {
            std::cout << std::endl << "Введите количество вершин: " << std::endl;
            userInput = input();
            int newKey;
            for (int i = 0; i < userInput; i++)
            {
                newKey = rand() % 100;
                addNodeRecursive(pRoot, newKey);
            }
        }
        else if (choice == 2)
        {
            if (!(isEmpty(pRoot)))
            {
                std::cout << std::endl << "Введите значение ключа для поиска:" << std::endl;
                userInput = input();
                Node* pCurrent = search(userInput);
                if (pCurrent != NULL)
                    std::cout << std::endl << "Ключ найден. Счетчик числа появлений данного ключа равен " << pCurrent->counter << std::endl;
                else
                    std::cout << std::endl << "Ключ не найден" << std::endl;
            }
            else
                std::cout << std::endl << "Дерево поиска пустое!" << std::endl;
        }
        else if (choice == 3)
        {
            std::cout << std::endl << "Введите значение ключа: " << std::endl;
            userInput = input();
            addNodeRecursive(pRoot, userInput);
        }
        else if (choice == 4)
        {
            std::cout << std::endl << "Введите значение ключа: " << std::endl;
            userInput = input();
            addNodeNonRecursive(userInput);
        }
        else if (choice == 5)
        {
            std::cout << std::endl << "Вывод дерева в обратно-симметричном порядке:" << std::endl;
            showBackSymmetric(pRoot, 0);
            std::cout << std::endl;
        }
        else if (choice == 6)
        {
            std::cout << std::endl << "Вывод всех вершин в порядке возрастания их ключей:" << std::endl;
            showInLine(pRoot, 0);
            std::cout << std::endl;
        }
        else if (choice == 7)
        {
            if (!(isEmpty(pRoot)))
            {
                std::cout << std::endl << "Введите значение ключа: " << std::endl;
                userInput = input();
                deleteNode(pRoot, userInput);
            }
            else
                std::cout << std::endl << "Дерево поиска пустое!" << std::endl;
        }
        else if (choice == 0)
            break;
        else
            std::cout << std::endl << "Выберите действие из списка и введите соотвествующий номер!" << std::endl;
    }
}
 
int main()
{
    srand(static_cast<unsigned int>(time(0)));
    setlocale(LC_ALL, "Russian");
    initialization();
    menu();
    return 0;
}