#include
#include

#define RED 1 /* stala oznaczajaca kolor wezla */
#define BLACK 0 /* stala oznaczajaca kolor wezla */
#define SZER_EKR 80 /* szerokosc ekranu */
#define IL_POZ 5 /* ilosc poziomow drzewa, ktore beda wydrukowane */
/* gwiazdka bedzie sygnalizowac istnienie nizszych */
/* poziomow */

/* struktury danych do reprezentowania drzewa */
typedef struct wezel *Wskwezla; /* wskaznik na wezel drzewa */
typedef struct wezel{
int klucz;
Wskwezla lewy, prawy, ojciec;
int kolor;
} Twezla ; /* typ wezla */

/* funkcja drukujaca drzewo binarne na ekranie (tutaj tylko deklaracja) */
/* funkcja drukuje drzewo o korzeniu "w" */
void drukuj(Wskwezla w);

/* ------------ implementacja ------------------------------------- */
char wydruk[IL_POZ+1][SZER_EKR];

int wysokosc(Wskwezla w){
if (w==NULL) return -1;
int l = wysokosc(w->lewy);
int p = wysokosc(w->prawy);
if (l else return l+1;
}

void drukujost(Wskwezla w, int l, int p,int poziom){
int srodek = (l+p)/2;

if (w==NULL) return;
wydruk[poziom][srodek]='*';
}

void drukujwew(Wskwezla w, int l, int p,int poziom){
int srodek = (l+p)/2;
int i,dl;
char s[9];
if (w==NULL) return;
if (w->kolor==BLACK)
dl=sprintf(s,"%d",w->klucz);
else
dl=sprintf(s,"%+d",w->klucz);
for (i=0;i wydruk[poziom][srodek-dl/2+i]=s[i];
if (++poziom drukujwew(w->lewy,l,srodek,poziom) ;
drukujwew(w->prawy,srodek+1,p,poziom) ;
}
else {
drukujost(w->lewy,l,srodek,poziom) ;
drukujost(w->prawy,srodek+1,p,poziom) ;
}
}

void drukuj(Wskwezla w){
int j,i;
for (i=0;i<=IL_POZ;i++){
for (j=0;j wydruk[i][j] = ' ';
wydruk[i][SZER_EKR]='\n';
}
drukujwew(w,0,SZER_EKR,0);
// for (i=0;i<=IL_POZ;i++)
printf("%s\n",wydruk);
printf("\nwysokosc: %d\n ", wysokosc(w));
printf("----------------------------------\n");
getchar();
}

void wstaw(Wskwezla *korzen, int wartosc){
Wskwezla x,y;
Wskwezla w = (Wskwezla) malloc(sizeof(Twezla));
w->klucz = wartosc;
w->lewy = NULL;
w->prawy = NULL;
if (*korzen==NULL) {
*korzen = w;
(*korzen)->ojciec = NULL;
} else{
x=*korzen;
while (x != NULL){
y = x;
if (y->klucz > wartosc) x=y->lewy;
else x = y->prawy;
}
w->ojciec = y;
if (y->klucz > wartosc) y->lewy = w;
else y->prawy = w;
}
}

Wskwezla szukaj(Wskwezla x, int k){
if (x!=NULL) printf(" szukanie: %d;",x->klucz);
if (x==NULL || k==x->klucz) return x;
if (k< x->klucz)
return szukaj(x->lewy,k);
else
return szukaj(x->prawy,k);
}

Wskwezla min(Wskwezla x){
// zalozenie: x!=NULL
while (x->lewy != NULL) {
printf("min: %d;",x->klucz);
x = x->lewy;
}
return x;
}

Wskwezla usunWezel(Wskwezla *r, Wskwezla z){
Wskwezla y,x;
if (z->lewy == NULL || z->prawy == NULL)
y=z;
else
y=min(z->prawy); // usuwamy y z co najw. jednym synem
if (y-> lewy != NULL) x= y->lewy;
else x= y->prawy; // x - jedyny syn y badz NULL
x->ojciec = y->ojciec;
if (y->ojciec == NULL)
*r=x; // y byl korzeniem
else
if (y == y->ojciec->lewy)
y->ojciec->lewy = x; // y byl lewym synem
else
y->ojciec->prawy =x; // y byl prawym synem
if (y!=z) z->klucz = y->klucz; // z mial dwoch synow
y->ojciec = x; // x wszedl w miejsce usunietego y
// printf("\nusuwanie: y= %d x= %d\n", y->klucz, (x == NULL ?-1:x->klucz));
return y;
}

void usun(Wskwezla *wr,int k){
Wskwezla w;
if ((w=szukaj(*wr,k)) != NULL) usunWezel(wr,w);
}

/* ----------------- program testujacy -----------------------*/

main(){
int i;
Wskwezla korzen = NULL;
wstaw(&korzen, 3);
drukuj(korzen);
wstaw(&korzen, 4);
drukuj(korzen);
wstaw(&korzen, 6);
drukuj(korzen);
wstaw(&korzen, 1);
drukuj(korzen);
wstaw(&korzen, 2);
drukuj(korzen);
wstaw(&korzen, 5);
drukuj(korzen);
szukaj(korzen,5);
usun(&korzen,4);
drukuj(korzen);
for (i=10;i<100;i++)
wstaw(&korzen,rand()%100);
drukuj(korzen);

/* ----------------
Zadanie: porownac wysokosc drzewa w przypadku wstawienia
n kolejnych liczb i
n losowych liczb
Sprawdzic dla n=1000 i n=40000.
(lg 1000 =10, lg 40000 =12)
*/
}