AISD BST

#include <stdio.h>
#include <stdlib.h>

struct bst{
    struct bst *left;
    struct bst *right;
    struct bst *p;
    int k;
};

void bst_inorder(struct bst*);
void bst_postorder(struct bst*);
void bst_preorder(struct bst*);
struct bst * bst_wstaw(struct bst*, struct bst*);
struct bst * bst_szukaj(struct bst*, int);
struct bst * bst_szukaj_r(struct bst*, int);
struct bst * bst_min(struct bst*);
struct bst * bst_max(struct bst*);
struct bst * bst_usun(struct bst*, struct bst*);
struct bst * bst_nastepnik(struct bst*);
struct bst * bst_poprzednik(struct bst*);

int main(){
    int i, quit = 1;
    char znak;
    struct bst *root = NULL, *nowy = NULL;

    while(quit){
        printf("\nWybierz akcje:");
        printf("\n[D] - Dodaj nowy element");
        printf("\n[W] - Wyswietl elementy");
        printf("\n[S] - Znajdz element");
        printf("\n[M] - Znajdz minimalny element");
        printf("\n[X] - Znajdz maksymalny element");
        printf("\n[N] - Znajdz następnik elementu");
        printf("\n[P] - Znajdz poprzednik elementu");
        printf("\n[U] - Usun element");
        printf("\n[Q] - Wyjdz z programu\n");
        fflush(stdin);
        scanf("%c", &znak);

        system("cls");

        switch(znak){
            case 'd':
                printf("Podaj klucz elementu do wstawienia: ");
                scanf("%d", &i);
                nowy = calloc(1, sizeof(struct bst));
                nowy -> k = i;
                root = bst_wstaw(root, nowy);
                break;
            case 'w':
                if (root == NULL) {
                    printf("Drzewo jest puste");
                    break;
                }
                printf("Inorder: ");
                bst_inorder(root);
                printf("Preorder: ");
                bst_preorder(root);
                printf("Postorder: ");
                bst_postorder(root);
                break;
            case 's':
                printf("Podaj klucz szukanego elementu: ");
                scanf("%d", &i);
                nowy = calloc(1, sizeof(struct bst));
                nowy = bst_szukaj(root, i);
                if (nowy == NULL)
                    printf("Elementu o kluczu %d nieznaleziono", i);
                else
                    printf("Znaleziono element o kluczu %d", i);
                break;
            case 'm':
                nowy = calloc(1, sizeof(struct bst));
                nowy = bst_min(root);
                if (nowy == NULL)
                    printf("W drzewie nie ma elementow");
                else
                    printf("Najmniejszy klucz w drzewie wynosi %d", nowy -> k);
                break;
            case 'x':
                nowy = calloc(1, sizeof(struct bst));
                nowy = bst_max(root);
                if (nowy == NULL)
                    printf("W drzewie nie ma elementow");
                else
                    printf("Najwiekszy klucz w drzewie wynosi %d", nowy -> k);
                break;
            case 'n':
                printf("Podaj klucz elementu dla ktorego znalezc nastepnik: ");
                scanf("%d", &i);
                nowy = calloc(1, sizeof(struct bst));
                nowy = bst_szukaj(root, i);
                if (nowy == NULL)
                    printf("Nie znaleziono elementu o kluczu %d", i);
                else {
                    nowy = bst_nastepnik(nowy);
                    if (nowy == NULL)
                        printf("Element o kluczu %d nie ma nastepnika", i);
                    else
                        printf("Nastepnik elementu o kluczu %d ma klucz wynoszacy %d", i, nowy -> k);
                }
                break;
            case 'p':
                printf("Podaj klucz elementu dla ktorego znalezc poprzednik: ");
                scanf("%d", &i);
                nowy = calloc(1, sizeof(struct bst));
                nowy = bst_szukaj(root, i);
                if (nowy == NULL)
                    printf("Nie znaleziono elementu o kluczu %d", i);
                else {
                    nowy = bst_poprzednik(nowy);
                    if (nowy == NULL)
                        printf("Element o kluczu %d nie ma poprzednika", i);
                    else
                        printf("Poprzednik elementu o kluczu %d ma klucz wynoszacy %d", i, nowy -> k);
                }
                break;
            case 'u':
                printf("Podaj klucz elementu do usuniecia: ");
                scanf("%d", &i);
                nowy = calloc(1, sizeof(struct bst));
                nowy = bst_szukaj(root, i);
                if (nowy == NULL){
                    printf("Nie znaleziono elementu o kluczu %d", i);
                    break;
                }
                else{
                    root = bst_usun(root, nowy);
                }
                break;
            case 'q':
                quit = 0;
                break;
        }

    }

    system("pause");
    return 1;
}

void bst_inorder(struct bst *root){
    struct bst *x = root;
    if (x != NULL && x -> left != NULL)
        bst_inorder(x->left);
    printf("%d ", x -> k);
    if (x -> right != NULL)
        bst_inorder(x -> right);
}

void bst_preorder(struct bst *root){
    struct bst *x = root;
    printf("%d ", x -> k);
    if (x != NULL && x -> left != NULL)
        bst_inorder(x->left);
    if (x -> right != NULL)
        bst_inorder(x -> right);
}

void bst_postorder(struct bst *root){
    struct bst *x = root;
    if (x != NULL && x -> left != NULL)
        bst_inorder(x->left);
    if (x -> right != NULL)
        bst_inorder(x -> right);
    printf("%d ", x -> k);
}

struct bst * bst_wstaw(struct bst* root, struct bst* nowy){
    struct bst *x = root, *y = NULL;
    while (x != NULL){
        y = x;
        if (nowy -> k < x -> k)
            x = x -> left;
        else
            x = x -> right;
    }
    nowy -> p = y;
    if (y == NULL)
        root = nowy;
    else
        if (nowy -> k < y -> k)
            y -> left = nowy;
        else
            y -> right = nowy;
    return root;
}

struct bst * bst_szukaj(struct bst* root, int key){
    struct bst *x = root;
    while (x != NULL && key != x -> k){
        if (key < x -> k)
            x = x -> left;
        else
            x = x -> right;
    }
    return x;
}

struct bst * bst_szukaj_r(struct bst* root, int key){
    struct bst *x = root;
    if (x == NULL) return NULL;
    else if (x -> k == key) return x;
    else if (key < x -> k) return bst_szukaj(x -> left, key);
    else return bst_szukaj(x -> right, key);
}

struct bst * bst_min(struct bst *root){
    struct bst *x = root;
    while (x -> left != NULL)
        x = x -> left;
    return x;
}

struct bst * bst_max(struct bst *root){
    struct bst *x = root;
    while (x -> right != NULL)
        x = x -> right;
    return x;
}

struct bst * bst_nastepnik(struct bst *look){
    struct bst *x = look, *y = NULL;
    if (x -> right != NULL)
        return bst_min(x -> right);
    y = x -> p;
    while (y != NULL && x == y -> right){
        x = y;
        y = y -> p;
    }
    return y;
}

struct bst * bst_poprzednik(struct bst *look){
    struct bst *x = look, *y = NULL;
    if (x -> left != NULL)
        return bst_max(x -> left);
    y = x -> p;
    while (y != NULL && x == y -> left){
        x = y;
        y = y -> p;
    }
    return y;
}

struct bst * bst_usun(struct bst *root, struct bst *waste){
    struct bst *y = NULL, *x = NULL, *T = root;
    int temp;
    if (root -> left == NULL && root -> right == NULL) return NULL;
    if (waste -> left == NULL || waste -> right == NULL)
        y = waste;
    else
        y = bst_nastepnik(waste);
    if (y -> left != NULL)
        x = y -> left;
    else
        x = y -> right;
    if (y != NULL)
        x -> p = y -> p;
    if (y -> p == NULL)
        T = x;
    else if (y == y -> p -> left)
       y -> p -> left = x;
    else
        y -> p -> right = x;
    if (y != waste){
        temp = y -> k;
        y -> k = waste -> k;
        waste -> k = temp;
    }
    free(y);
    free(x);
    return T;
}