AiSD_Lab_5_Drzewa_BST

/* dodać jeszcze następnik, poprzednik, usuwanie, zwalnianie pamieci */
//DK
#include<stdio.h>
#include<stdlib.h>

struct element {
    int key;
    struct element *parent;
    struct element *left;
    struct element *right;
};

struct element *BST_WSTAW(struct element *T, struct element *Z);
struct element *BST_szukaj(struct element *x, int k);
struct element *BST_min(struct element *x);
struct element *BST_max(struct element *x);
void Inorder( struct element *x);

int main()
{
    struct element *head = NULL;
    struct element *nowy = NULL;
    char znak;
    int key;

    printf("Legenda:\n*)d   dodaj do BST\n*)w   wyswietl BST\n*)s   szukaj\n*)l min\n*)h    max\n\n");

    while (1)
    {
        fflush(stdin);
        znak = getchar();
        switch(znak)
        {
            case 'd':
                nowy = (struct element*) malloc(sizeof(struct element));
                printf("\nPodaj key: ");
                scanf("%d", &key);
                nowy->key = key;
                nowy->left = NULL;
                nowy->right = NULL;
                head = BST_WSTAW(head, nowy);
                break;
            case 's':
                nowy = (struct element*) malloc(sizeof(struct element));
                printf("\nPodaj szukany element: ");
                scanf("%i", &key);
                nowy = BST_szukaj(head, key);
                if(nowy != NULL)
                    printf("\nZnaleziono! ");
                else
                    printf("\nNie znaleziono! ");
                break;
            case 'l':
                nowy = (struct element*) malloc(sizeof(struct element));
                nowy = BST_min(head);
                printf("\nMinimum : %i\n", nowy->key);
                break;
            case 'h':
                nowy = (struct element*) malloc(sizeof(struct element));
                nowy = BST_max(head);
                printf("\nMaksiumum : %i\n", nowy->key);
                break;
            case 'w':
                Inorder(head);
                printf("\n");
                break;
            case 'q':
                return 0;

        }
    }
    return 0;
}

struct element *BST_WSTAW(struct element *T, struct element * Z)
{
    struct element *y = NULL;
    struct element *x = T;

    while (x!=NULL)
    {
        y = x;
        if ( (Z->key) < (x->key) )
            x = x->left;
        else x = x->right;
    }

        Z->parent = y;

        if(y == NULL)
            T = Z;
        else if( (Z->key) < (y->key) )
            y->left = Z;
        else y->right = Z;


    return T;
}

void Inorder( struct element *x)
{
    if( x!=NULL )
    {
        Inorder( x->left);
        printf("%d-", x->key);
        Inorder( x->right );
    }
}
struct element *BST_szukaj(struct element *x, int k)
{
    while (x!=NULL && k!=(x->key))
    {
        if (k < (x->key))
            x = x->left;
        else x = x->right;
    }

    return x;
}

struct element *BST_min(struct element *x)
{
    while (x->left != NULL )
        x = x->left;
    return x;
}

struct element *BST_max(struct element *x)
{
    while (x->right != NULL )
        x = x->right;
    return x;
}