lab10right

#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;
    struct node *right_child;
    struct node *left_child;
};




struct node* find_minimum(struct node *root)
{
    if(root == NULL)
        return NULL;
    else if(root->left_child != NULL)
        return find_minimum(root->left_child);
    return root;
}


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)
{

    if(root==NULL)
        return new_node(x);
    else if(x>root->data)
        root->right_child = insert(root->right_child, x);
    else
        root->left_child = insert(root->left_child,x);
    return root;
}


struct node* delete(struct node *root, int x)
{

    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
    {
        if(root->left_child==NULL && root->right_child==NULL)
        {
            free(root);
            return NULL;
        }

        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;
        }

        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)
        return;
    else
    {
        display(root->left_child);

        printf("%d ", root->data);

        display(root->right_child);
    }



}
int count_height(struct node *root)
{
    if(root!=NULL)
    {
        int a = count_height(root->left_child);
        int b = count_height(root->right_child);
        if (a>b)

            return a+1;
        else
            return b+1;
    }
    else
        return 0;

}

int count_sum(struct node *root,  int level, int i)
{
    int sum = 0;
    if(root == NULL)
        return 0;
    if(i==level)
        return root->data;
    else {
        sum += count_sum(root->left_child,  level, i+1);
        sum += count_sum(root->right_child, level, i+1);
    }
    return sum;

}



int main()
{

    struct node *root;
    int y, level=0, sum = 0, num_levels;

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

    int choice = 10;




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

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

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

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

        case 3:
            printf("элементы: ");

            display(root);
            break;
        case 4:
            num_levels = count_height(root);
            for(int i = 0; i<count_height(root); i++)
            {
                sum = 0;

                printf("lvl%d, sum: %d\n", i, count_sum(root, i, 0));
            }
            break;

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

    }



    return 0;
}