Динамические структуры данных Вариант 18 Павловской

struct telbook
{
   char name[20];      // Имя абонента
   char phone[11];     // Номер абонента
   char time[10];       // Время разговоров по телефону
   char duty[15];       // Задолжность
};

struct telbook
{
   char name[20];       // Имя абонента
   int phone;           // Номер абонента
   int time;            // Время разговоров по телефону в мин.
   char duty[8];        // Задолжность в руб.
};

#include <iostream>
using namespace std;
 
/* структура бинарного дерева */
struct Tree
{
    int data; // данные
 
    Tree* parent; // родительский элемент
    Tree* left;  // левое поддерево
    Tree* right; // правое поддерево
};
 
/* вставка элемента */
void TreeInsert(Tree** root, int data)
{
    Tree* parent = NULL; // указатель на предыдущий родительский элемент
    Tree* current = *root; // вспомогательный указатель для перемещения по дереву
 
    /* создаём новый элемент, инициализурем его данными */
    Tree* newelement = new Tree;
    newelement->data = data;
    newelement->left = NULL;
    newelement->right = NULL;
 
    /* в цикле доходим до листьев */
    while (current)
    {
        parent = current;
        if (data < current->data)
            current = current->left;
        else
            current = current->right;
    }
 
    newelement->parent = parent; // устанавлием указатель на родительский элемент
    /* устанавлием указетели в родительском элементе */
    if (!parent) // дерево пустое
        *root = newelement;
    else if (data < parent->data)
        parent->left = newelement;
    else
        parent->right = newelement;
}
 
/* Возвращает минимальный элемент в дереве  */
Tree* TreeMinimum(Tree* root)
{
    while (root->left != NULL)
        root = root->left;
    return root;
}
/*  */
Tree* TreeSuccessor(Tree* root)
{
    if (root->right != NULL)
        return TreeMinimum(root->right);
    Tree* current = root->parent;
    while (current != NULL && root == current->right)
    {
        root = current;
        current = current->parent;
    }
    return current;
}
 
/* удаление элемента */
Tree* TreeRemove(Tree** root, Tree* element)
{
    Tree* current = NULL;
    Tree* temp = NULL;
 
    if (element->left == NULL || element->right == NULL)
        current = element;
    else
        current = TreeSuccessor(element);
 
    if (current->left != NULL)
        temp = current->left;
    else
        temp = current->right;
 
    if (temp != NULL)
        temp->parent = current->parent;
 
    if (current->parent == NULL)
        *root = temp;
    else if (current == current->parent->left)
        current->parent->left = temp;
    else
        current->parent->right = temp;
 
    if (current != element)
        element->data = current->data;
 
    return current;
 
}
 
/* симметричный обход дерева, печать элементов */
void TreePrint(Tree* root)
{
    if (root != NULL)
    {
        TreePrint(root->left);
        cout << root->data << endl;
        TreePrint(root->right);
    }
}
 
/* поиск элемента в дереве */
Tree* TreeSearch(Tree* root, int key)
{
    if (root == NULL || root->data == key)
        return root;
 
    if (key < root->data)
            TreeSearch(root->left, key);
    else
            TreeSearch(root->right, key);
}
 
/* рекурсивное удаление дерева  */
void TreeDelete(Tree* root)
{
    /*  пока есть левые потомки - рекурсивно перемещаемся в левое поддерево */
    if (root->left)
            TreeDelete(root->left);
    /*  пока есть правые потомки - рекурсивно перемещаемся в правое поддерево */
    if (root->right)
            TreeDelete(root->right);
    /* мы в листе - удаляем его */
    delete root;
}
 
int main()
{
    int data; // данные для ввода
 
    /* создаем корень */
    Tree* root = NULL;
 
    /* вводим элементы до ввода некорректного элемента */
    while (true)
    {
        cout << "Enter next element: \n";
        cin >> data;
        if (cin.good()) // проверяем успешность ввода
        {
            cin.ignore(10, '\n'); // очищаем буфер
            TreeInsert(&root, data); // добавляем элемент в дерево
        }
        else
        {
            cin.clear(); // очищаем флаги потока cin
            cin.ignore(10, '\n'); // очищаем буфер
            cout << "Data should be an integer, stop!\n";
            break;
        }
    }
 
    /* Рекурсивный обход с печатью элементов */
    cout << "Your tree: \n";
    TreePrint(root);
 
    /* поиск элемента */
    int key;
 
    cout << "Enter a key to find: ";
    while (true)
    {
        cin >> key;
        if (cin.good())
        {
            cin.ignore(10, '\n');
            break;
        }
 
        cin.clear();
        cin.ignore(10, '\n');
        cout << "Key should be an integer!\n";
    }
 
    Tree* found = TreeSearch(root, key);
    if (found == NULL)
        cout << "There is no such element!\n";
    else
        cout << "Here is your element: " << found->data << endl;
    cout << "Trying to delete the found element...\n";
    TreeRemove(&root, found);
    cout << "Printing your tree again: \n";
    TreePrint(root);
 
    cout << "Exiting...\n";
    /* Освобождение памяти */
    TreeDelete(root);
    return 0;
}