source.cpp

#include "pch.h"
#include "Header.h"

int get_int()
{
    int i, n;

    do
    {
        rewind(stdin);
        i = scanf_s("%d", &n);

        if (!i)
        {
            printf("Введите целое число!\n");
            continue;
        }
    } while (!i);

    return n;
}

char* get_string()
{
    char c;
    int size = 0;
    char* string = NULL;;

    do
    {
        c = _getch();

        if (c != '\n' && c != '\b' && c != '\r')
        {
            string = (char*)realloc(string, sizeof(char) * ((++size) + 1));
            string[size - 1] = c;
            printf("%c", c);
        }
        else
        {
            if (c == '\b')
            {
                printf("%c", c);

                if (size > 1)
                {
                    string = (char*)realloc(string, sizeof(char) * (--size));
                    string = (char*)realloc(string, sizeof(char) * (size + 1));
                }
                else
                {
                    free(string);
                    string = NULL;
                    size = 0;
                }
            }
        }
    } while (c != '\n' && c != '\r');

    string[size] = '\0';
    printf("\n");

    return string;
}

int get_year()
{
    int year;

    do
    {
        year = get_int();
    } while (year < 1 || year > 11);

    return year;
}

int get_positive()
{
    int n;

    do
    {
        n = get_int();
    } while (n <= 0);

    return n;
}

int* get_ints(int size)
{
    int* array = (int*)malloc(sizeof(int) * size);
    int i;

    for (i = 0; i < size; i++)
    {
        array[i] = get_positive();
    }

    return array;
}

struct student* get_student()
{
    struct student* stud = (struct student*)malloc(sizeof(struct student));

    printf("Введите имя ученика:");
    stud->name = get_string();
    printf("Введите фамилию ученикa:");
    stud->surname = get_string();
    printf("Введите отчесто ученика:");
    stud->patronimyc = get_string();
    printf("Введите год обучения(номер класса):");
    stud->year = get_year();
    printf("Введите букву класса:");
    rewind(stdin);
    stud->letter = getchar();
    printf("Введите количество предметов:");
    stud->marks_numb = get_positive();
    printf("Введите оценки:\n");
    stud->marks = get_ints(stud->marks_numb);

    return stud;
}

struct student* student_delete(struct student* stud)
{
    if (stud != NULL)
    {
        free(stud->name);
        free(stud->surname);
        free(stud->patronimyc);
        free(stud->marks);
        free(stud);
    }

    stud = NULL;
    return stud;
}

void student_print(struct student* stud)
{
    if (stud == NULL)
    {
        return;
    }

    printf("%2d%c %s %s %s", stud->year, stud->letter, stud->surname, stud->name, stud->patronimyc);

    printf(" Оценки: ");

    for (int i = 0; i < stud->marks_numb; i++)
    {
        printf("%2d ", stud->marks[i]);
    }
    printf("\n");
}

void student_copy(struct student* source, struct student* destinition)
{
    if (!source) return;

    destinition->letter = source->letter;
    destinition->marks_numb = source->marks_numb;
    destinition->year = source->year;

    destinition->name = (char*)malloc(sizeof(char) * (strlen(source->name) + 1));
    strcpy(destinition->name, source->name);

    destinition->surname = (char*)malloc(sizeof(char) * (strlen(source->surname) + 1));
    strcpy(destinition->surname, source->surname);

    destinition->patronimyc = (char*)malloc(sizeof(char) * (strlen(source->patronimyc) + 1));
    strcpy(destinition->patronimyc, source->patronimyc);

    destinition->marks = (int*)malloc(sizeof(int) * destinition->marks_numb);

    int i;
    for (i = 0; i < destinition->marks_numb; i++)
    {
        destinition->marks[i] = source->marks[i];
    }
}

struct tree* add_element(struct tree* root, struct student* stud)
{
    struct tree* new_tree = (struct tree*)malloc(sizeof(struct tree));
    new_tree->stud = (struct student*)malloc(sizeof(struct student));
    student_copy(stud, new_tree->stud);
    new_tree->left = new_tree->right = NULL;

    if (!root)
    {
        root = new_tree;
        root->parent = NULL;
    }
    else
    {
        struct tree* cur = root;

        while (cur)
        {
            if (cur->stud->year >= new_tree->stud->year)
            {
                if (cur->left)
                {
                    cur = cur->left;
                }
                else
                {
                    cur->left = new_tree;
                    new_tree->parent = cur;
                    cur = NULL;
                }
            }
            else
            {
                if (cur->right)
                {
                    cur = cur->right;
                }
                else
                {
                    cur->right = new_tree;
                    new_tree->parent = cur;
                    cur = NULL;
                }
            }
        }
    }

    return root;
}

void show_tree_recursive1(struct tree* root) //симметричный обход (левое поддерево -> корень -> правое)
{
    if (root)
    {
        if (root->left)
        {
            show_tree_recursive1(root->left);
        }

        student_print(root->stud);

        if (root->right)
        {
            show_tree_recursive1(root->right);
        }
    }
}

void show_tree_recursive2(struct tree* root) //прямой обход (корень -> левое поддерево -> правое поддерево)
{
    if (root)
    {
        student_print(root->stud);

        if (root->left)
        {
            show_tree_recursive2(root->left);
        }

        if (root->right)
        {
            show_tree_recursive2(root->right);
        }
    }
}

void show_tree_recursive3(struct tree* root) //обход снизу (левое поддерево -> прaвое поддерево -> корень)
{
    if (root)
    {
        if (root->left)
        {
            show_tree_recursive3(root->left);
        }

        if (root->right)
        {
            show_tree_recursive3(root->right);
        }

        student_print(root->stud);
    }
}

struct tree* add_element_recursive(struct tree* root, struct student* stud, struct tree* parent)
{
    if (!root)
    {
        root = (struct tree*)malloc(sizeof(struct tree));
        root->stud = (struct student*)malloc(sizeof(struct student));
        student_copy(stud, root->stud);
        root->parent = parent;
        root->left = root->right = NULL;

        if (parent)
        {
            if (root->parent->stud->year >= root->stud->year)
            {
                root->parent->left = root;
            }
            else
            {
                root->parent->right = root;
            }
        }
    }
    else
    {
        if (root->stud->year >= stud->year)
        {
            root->left = add_element_recursive(root->left, stud, root);
        }
        else
        {
            root->right = add_element_recursive(root->right, stud, root);
        }
    }

    return root;
}

void push(struct list** stack, struct tree* node)
{
    struct list* new_el = (struct list*)malloc(sizeof(struct list));
    new_el->node = node;
    struct list* temp = *stack;
    *stack = new_el;
    new_el->next = temp;
}

struct tree* pop(struct list** stack)
{
    struct list* temp = *stack;
    struct tree* ret_val = temp->node;
    *stack = (*stack)->next;
    free(temp);
    return ret_val;
}

void show_tree(struct tree* root) //нерекурсивный прямой обход дерева
{
    if (!root) return;

    int left = 1;
    struct list* stack = NULL;
    push(&stack, root);

    student_print(root->stud);

    if (root->left == NULL && root->right == NULL)
    {
        return;
    }

    while (stack || root->right)
    {
        do
        {
            if (left && root->left)
            {
                root = root->left;
            }
            else
            {
                if (root->right)
                {
                    root = root->right;
                }
            }

            if (root->left && root->right)
            {
                push(&stack, root);
            }

            left = 1;
            student_print(root->stud);

        } while (root->left || root->right);

        if (stack)
        {
            root = pop(&stack);
        }

        if (root->right)
        {
            left = 0;
        }
    }
}

int choose()
{
    int n;
    do
    {
        printf("Выберите действие:\n");
        n = get_int();
    } while (n < 1 || n > 10);

    return n;
}

int students_cmp(struct student* stud1, struct student* stud2)
{
    if (stud1 == NULL || stud2 == NULL) return 0;

    if (strcmp(stud1->name, stud2->name) != 0) return 0;
    if (strcmp(stud1->surname, stud2->surname) != 0) return 0;
    if (strcmp(stud1->patronimyc, stud2->patronimyc) != 0) return 0;
    if (stud1->year != stud2->year || stud1->letter != stud2->letter) return 0;
    if (stud1->marks_numb != stud2->marks_numb) return 0;

    for (int i = 0; i < stud1->marks_numb; i++)
    {
        if (stud1->marks[i] != stud2->marks[i]) return 0;
    }

    return 1;
}

struct tree* search(struct tree* root, struct student* stud)
{
    if (root == NULL || students_cmp(root->stud, stud)) return root;

    if (stud->year <= root->stud->year)
    {
        return search(root->left, stud);
    }
    else
    {
        return search(root->right, stud);
    }
}

struct tree* tree_minimum(struct tree* root)
{
    while (root->left != NULL)
    {
        root = root->left;
    }

    return root;
}

void transplant(struct tree** root, struct tree* u, struct tree* v) //меняет поддерево u на поддерево v
{
    if (u->parent == NULL)
    {
        *root = v;
        return;
    }

    if (u->parent->left == u) //если u - левый элемент
    {
        u->parent->left = v;
    }
    else
    {
        u->parent->right = v;
    }

    if (v)
    {
        v->parent = u->parent;
    }
}

void tree_delete(struct tree** root, struct student* stud)
{
    struct tree* del = search(*root, stud);
    if (!del)
    {
        return;
    }

    struct tree* min;

    if (!del->left)
    {
        transplant(root, del, del->right);
        free(del);
    }
    else if (!del->right)
    {
        transplant(root, del, del->left);
        free(del);
    }
    else
    {
        min = tree_minimum(del->right);

        if (min->parent != del)
        {
            transplant(root, min, min->right);
            min->right = del->right;
            min->right->parent = min;
        }

        transplant(root, del, min);
        min->left = del->left;
        min->left->parent = min;
        free(del);
    }
}

void tree_show_by_level(struct tree* root, int level)
{
    if (root)
    {
        tree_show_by_level(root->right, level + 1);
    }

    for (int i = 0; i < level; i++)
    {
        printf(" ");
    }

    if (root)
    {
        printf("%d\n", root->stud->year);
    }

    if (root)
    {
        tree_show_by_level(root->left, level + 1);
    }
}

void info()
{
    printf("1)Добавить элемент\n");
    printf("2)Добавить элемент рекурсивно\n");
    printf("3)Нерекурсивный вывод дерева с использованием стека\n");
    printf("4)Симметричный обход дерева(рекурсивно)\n");
    printf("5)Прямой обход дерева(рекурсивно)\n");
    printf("6)Обход дерева снизу(рекуссивно)\n");
    printf("7)Удаление элемента\n");
    printf("8)Рекурсивный поиск\n");
    printf("9)Вывод дерева по уровням\n");
    printf("10)Закончить\n");
}