lab10

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
#include <locale.h>
#define SIZE 10

struct node
{
    int data; //node will store an integer
    struct node *right_child; // right child
    struct node *left_child; // left child
};



//function to find the minimum value in a node
struct node* find_minimum(struct node *root)
{
    if(root == NULL)
        return NULL;
    else if(root->left_child != NULL) // node with minimum value will have no left child
        return find_minimum(root->left_child); // left most element will be minimum
    return root;
}

//function to create a node
struct node* new_node(int x)
{
    struct node *p;
    p = malloc(sizeof(struct node));
    p->data = x;
    p->left_child = NULL;
    p->right_child = NULL;

    return p;
}

struct node* insert(struct node *root, int x)
{
    //searching for the place to insert
    if(root==NULL)
        return new_node(x);
    else if(x>root->data) // x is greater. Should be inserted to right
        root->right_child = insert(root->right_child, x);
    else // x is smaller should be inserted to left
        root->left_child = insert(root->left_child,x);
    return root;
}

// funnction to delete a node
struct node* delete(struct node *root, int x)
{
    //searching for the item to be deleted
    if(root==NULL)
        return NULL;
    if (x>root->data)
        root->right_child = delete(root->right_child, x);
    else if(x<root->data)
        root->left_child = delete(root->left_child, x);
    else
    {
        //No Children
        if(root->left_child==NULL && root->right_child==NULL)
        {
            free(root);
            return NULL;
        }

        //One Child
        else if(root->left_child==NULL || root->right_child==NULL)
        {
            struct node *temp;
            if(root->left_child==NULL)
                temp = root->right_child;
            else
                temp = root->left_child;
            free(root);
            return temp;
        }

        //Two Children
        else
        {
            struct node *temp = find_minimum(root->right_child);
            root->data = temp->data;
            root->right_child = delete(root->right_child, temp->data);
        }
    }
    return root;
}

void display(struct node *root)
{


    if(root!=NULL) // checking if the root is not null
    {
        display(root->left_child); // visiting left child
        printf(" %d ", root->data); // printing data at root

        display(root->right_child);// visiting right child

    }


}

int main()
{

    struct node *root;
    int y;
    printf("Введите вершину дерева\n");
    scanf("%d", &y);
    root = new_node(y);

    int choice = 10, x;

    while(choice!=4)
    {
        printf("\n1.Добавить элемент\n2.Удалить элемент\n3.Показать элементы очереди\n4.Выход\n");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            printf("Введите элемент\n");

            scanf("%d", &x);
            insert(root,x);
            break;

        case 2:
            printf("Введите элемент\n");

            scanf("%d", &x);
            delete(root, x);
            break;

        case 3:

            display(root);
            break;


        case 4:
            exit(-1);
        default:
            printf("\nПовторите ввод\n");
        }

    }


    return 0;
}