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

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

void bst_wyswietl(struct wezel *x);
struct wezel *bst_dodaj(struct wezel *root, struct wezel *nowy);
struct wezel *bst_szukaj(struct wezel *root, int liczba);
struct wezel *bst_usun(struct wezel *root, struct wezel* u);
struct wezel *bst_min(struct wezel *root);
struct wezel *bst_nast(struct wezel *x);
struct wezel* bst_odwroc(struct wezel *root);
struct wezel * bst_zwolnij(struct wezel *root);

int main()
{
    struct wezel *root=NULL, *nowy=NULL, *x=NULL;
    char z;
    int liczba;
    while(1)
    {
        printf("Co chcesz zrobic?");
        printf("\nd - dodac");
        printf("\ns - szukac");
        printf("\nu - usunac");
		printf("\nm - minimum");
		printf("\nn - nastepnik");
        printf("\no - odwrocic liste");
        printf("\nw - wyswietlic");
        printf("\nq - wyjsc\n");
        fflush(stdin);
        z=getchar();
        switch(z)
        {
        case 'd':
            nowy=(struct wezel*)malloc(sizeof(struct wezel));
            printf("\nPodaj wartosc wezla do wstawienia: ");
            scanf("%d",&liczba);
            nowy->k=liczba;
			nowy->left=NULL;
			nowy->right=NULL;
            root=bst_dodaj(root,nowy);
            break;
        case 's':printf("Podaj wartosc elementu do wyszukania");
			scanf("%d",&liczba);
			nowy=bst_szukaj(root,liczba);
			printf("Wartosc wskaźnika wynosi %d",nowy);
            break;
        case 'u':
            break;
		case 'm':nowy=bst_min(root);
			printf("%d",nowy->k);
			break;
		case 'n':printf("Podaj wartosc wezla");
			scanf("%d",&liczba);
			nowy=bst_szukaj(root,liczba);
			nowy=bst_nast(nowy);
			printf("%d",nowy->k);
			break;
        case 'o':
            break;
        case 'w':bst_wyswietl(root);
            break;
        case 'q':
            return 0;
        default :
            printf("Podano zly znak. Podaj poprawny.");
            break;
        }
    }
}

void bst_wyswietl(struct wezel *x)
{
    if(x!=NULL)
	{

		bst_wyswietl(x->left);
		printf("%d ",x->k);
		bst_wyswietl(x->right);
	}
}


struct wezel *bst_dodaj(struct wezel *root, struct wezel *nowy)
{
	struct wezel *y=NULL;
	struct wezel *x=root;
    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 wezel *bst_szukaj(struct wezel *x, int liczba)
{
	if(x==NULL || liczba==x->k)
		return x;
	if(liczba < x->k)
		return bst_szukaj(x->left,liczba);
	else
		return bst_szukaj(x->right,liczba);
}
struct wezel *bst_usun(struct wezel *root, struct wezel* u)
{
	struct wezel *x=root;
	while(x!=NULL)
	{

	}
}
struct wezel *bst_min(struct wezel *root)
{
	struct wezel *x=root;
	while(x->left!=NULL)
		x=x->left;
	return x;
}
struct wezel *bst_nast(struct wezel *x)
{
	struct wezel *y=NULL;
	if(x->right!=NULL)
		return bst_min(x->right);
	y=x->p;
	while(x!=NULL && x==y->right)
	{
		x=y;
		y=y->p;
	}
	return y;
}