drzewo.c

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "drzewo.h"
//lokalny typ danych
typedef struct para {
	Wezel *rodzic;
	Wezel *dziecko;
} Para;

//funkcje lokalne
static Wezel *UtworzWezel(const Pozycja *wp) {
	Wezel *nowy;
	nowy = (Wezel *)malloc(sizeof(Wezel));
	if (nowy != NULL) {
		nowy->pozycja = *wp;
		nowy->lewy = NULL;
		nowy->prawy = NULL;
	}
	return nowy;
}
static bool NaLewo(const Pozycja *p1, const Pozycja *p2) {
	int porown1;
	if ((porown1 = strcmp(p1->imie, p2->imie)) < 0)
		return true;
	else if (porown1 == 0 && strcmp(p1->gatunek, p2->gatunek) < 0)
		return true;
	else
		return false;
}
static bool NaPrawo(const Pozycja *p1, const Pozycja *p2) {
	int porown1;
	if ((porown1 = strcmp(p1->imie, p2->imie)) > 0)
		return true;
	else if (porown1 == 0 && strcmp(p1->gatunek, p2->gatunek) > 0)
		return true;
	else
		return false;
}
static void DodajWezel(Wezel *nowy, Wezel *korzen) {
	if (NaLewo(&nowy->pozycja, &korzen->pozycja)) {
		if (korzen->lewy == NULL)	//puste poddrzewo
			korzen->lewy = nowy;	//wiec wstawiamy tu wezel
		else
			DodajWezel(nowy, korzen->lewy);	//w przeciwnym wypadku szukamy szczescia w poddrzewie
	}
	else if (NaPrawo(&nowy->pozycja, &korzen->pozycja)) {
		if (korzen->prawy == NULL)
			korzen->prawy = nowy;
		else
			DodajWezel(nowy, korzen->prawy);
	}
	else	//nie powinno byc dwoch identycznych pozycji
	{
		fprintf(stderr, "Blad funkcji DodajWezel()\n");
		exit(1);
	}
}
static void PoKolei(const Wezel *korzen, void(*wfun)(Pozycja pozycja)) {
	if (korzen != NULL) {
		PoKolei(korzen->lewy, wfun);
		(*wfun)(korzen->pozycja);
		PoKolei(korzen->prawy, wfun);
	}
}
static Para SzukajPozycji(const Pozycja *wp, const Drzewo *wdrzewo) {
	Para szuk;
	szuk.rodzic = NULL;
	szuk.dziecko = wdrzewo->korzen;
	if (szuk.dziecko == NULL)
		return szuk;
	while (szuk.dziecko != NULL) {
		if (NaLewo(wp, &(szuk.dziecko->pozycja))) {
			szuk.rodzic = szuk.dziecko;
			szuk.dziecko = szuk.dziecko->lewy;
		}
		else if (NaPrawo(wp, &(szuk.dziecko->pozycja))) {
			szuk.rodzic = szuk.dziecko;
			szuk.dziecko = szuk.dziecko->prawy;
		}
		else			//jesli szukana pozycja nie znajduje sie ani po lewej ani po prawej
			break;		//stronie pozycji szuk.dziecko->pozycja
	}
	return szuk;
}
static void UsunWezel(Wezel **wsk) {
	//wsk jest adresem skladnika rodzica, ktory wskazuje na usuwany wezel
	Wezel *tymcz;
	if ((*wsk)->lewy == NULL) {
		tymcz = *wsk;
		*wsk = (*wsk)->prawy;
		free(tymcz);
	}
	else if ((*wsk)->prawy == NULL) {
		tymcz = *wsk;
		*wsk = (*wsk)->lewy;
		free(tymcz);
	}
	else {	//usuwany wezel ma dwoje dzieci
		//szukamy miejsca dolaczenia prawego poddrzewa
		for (tymcz = (*wsk)->lewy; tymcz->prawy != NULL; tymcz = tymcz->prawy)
			continue;
		tymcz->prawy = (*wsk)->prawy;
		tymcz = *wsk;
		*wsk = (*wsk)->lewy;
		free(tymcz);
	}
}
static void UsunWszystkieWezly(Wezel *wsk) {
	Wezel *wprawy;
	if (wsk != NULL) {
		wprawy = wsk->prawy;
		UsunWszystkieWezly(wsk->lewy);
		free(wsk);
		UsunWszystkieWezly(wprawy);
	}
}

//definicje funkcji
void InicjujDrzewo(Drzewo *wdrzewo) {
	wdrzewo->korzen = NULL;
	wdrzewo->rozmiar = 0;
}

bool PusteDrzewo(const Drzewo *wdrzewo) {
	if (wdrzewo->korzen == NULL)
		return true;
	else
		return false;
}

bool PelneDrzewo(const Drzewo *wdrzewo) {
	if (wdrzewo->rozmiar == MAXPOZ)
		return true;
	else
		return false;
}

int LiczbaPozycji(const Drzewo *wdrzewo) {
	return wdrzewo->rozmiar;
}

bool DodajPozycje(const Pozycja *wp, Drzewo *wdrzewo) {
	Wezel *nowy;
	if (PelneDrzewo(wdrzewo)) {
		fprintf(stderr, "Drzewo jest pelne\n");
		return false;	//wczesny powrot
	}
	if (SzukajPozycji(wp, wdrzewo).dziecko != NULL) {
		fprintf(stderr, "Proba dodania istniejacej pozycji\n");
		return false;
	}
	nowy = UtworzWezel(wp);	//nowy wskazuje na nowy wezel
	if (nowy == NULL) {
		fprintf(stderr, "Nie mozna utworzyc wezla\n");
		return false;
	}//utworzenie nowego wezla sie powiodlo
	wdrzewo->rozmiar++;
	if (wdrzewo->korzen == NULL)			//przypadek 1: drzewo jest puste
		wdrzewo->korzen = nowy;				//nowy wezel jest korzeniem drzewa
	else									//przypadek 2: drzewo nie jest puste
		DodajWezel(nowy, wdrzewo->korzen);	//dodaje nowy wezel dodrzewa
	return true;							//udalo sie dodac pozycje
}

bool WDrzewie(const Pozycja *wp, const Drzewo *wdrzewo) {
	return (SzukajPozycji(wp, wdrzewo).dziecko == NULL) ? false : true;
}

bool UsunPozycje(const Pozycja *wp, Drzewo *wdrzewo) {
	Para szuk;
	szuk = SzukajPozycji(wp, wdrzewo);
	if (szuk.dziecko == NULL)
		return false;
	if (szuk.rodzic == NULL) //usuwa pozycje w korzeniu
		UsunWezel(&wdrzewo->korzen);
	else if (szuk.rodzic->lewy == szuk.dziecko)
		UsunWezel(&szuk.rodzic->lewy);
	else
		UsunWezel(&szuk.rodzic->prawy);
	wdrzewo->rozmiar--;
	return true;
}

void Przejdz(const Drzewo *wdrzewo, void(*wfun)(Pozycja pozycja)) {
	if (wdrzewo != NULL)
		PoKolei(wdrzewo->korzen, wfun);
}

void UsunWszystko(Drzewo *wdrzewo) {
	if (wdrzewo != NULL)
		UsunWszystkieWezly(wdrzewo->korzen);
	wdrzewo->korzen = NULL;
	wdrzewo->rozmiar = 0;
}

drzewo.h

#ifndef DRZEWO_H_
#define DRZEWO_H_
#include <stdbool.h>

typedef struct pozycja {
	char imie[20];
	char gatunek[20];
} Pozycja;
#define MAXPOZ 10
typedef struct wezel {
	Pozycja pozycja;
	struct wezel *lewy;		//wskaznik do prawej galezi
	struct wezel *prawy;	//wskaznik do lewej galezi
} Wezel;
typedef struct drzewo {
	Wezel *korzen;			//wskaznik do korzenia drzewa
	int rozmiar;			//liczba pozycji w drzewie
} Drzewo;

void InicjujDrzewo(Drzewo *wdrzewo);
bool PusteDrzewo(const Drzewo *wdrzewo);
bool PelneDrzewo(const Drzewo *wdrzewo);
int LiczbaPozycji(const Drzewo *wdrzewo);
bool DodajPozycje(const Pozycja *wp, Drzewo *wdrzewo);
bool WDrzewie(const Pozycja *wp, const Drzewo *wdrzewo);
bool UsunPozycje(const Pozycja *wp, Drzewo *wdrzewo);
void Przejdz(const Drzewo *wdrzewo, void(*wfun)(Pozycja pozycja));
void UsunWszystko(Drzewo *wdrzewo);

#endif

main.c

#include<stdio.h>
#include <string.h>
#include <ctype.h>
#include "drzewo.h"
#define MAXROZ 20

char menu(void);
void dodajzw(Drzewo *wd);
void wyswpoz(Pozycja pozycja);
void pokazzw(const Drzewo *wd);
void szukajzw(const Drzewo *wd);
void usunzw(Drzewo *wd);
void duzelit(char *lan);
char *wczytaj(char *z, int ile);

int main(void) {
	Drzewo zwierz;
	char wybor;
	InicjujDrzewo(&zwierz);
	while ((wybor = menu()) != 'q') {
		switch (wybor) {
		case 'd':	dodajzw(&zwierz);
					break;
		case 'w':	pokazzw(&zwierz);
					break;
		case 's':	szukajzw(&zwierz);
					break;
		case 'l':	printf("%d zwierzat w klubie.\n", LiczbaPozycji(&zwierz));
					break;
		case 'u':	usunzw(&zwierz);
					break;
		default:	puts("Blad w instrukcji switch");
		}
	}
	UsunWszystko(&zwierz);
	puts("Do widzenia!");
	return 0;
}

char menu(void) {
	int ch;
	puts("Klub Zwierzat Domowych - baza danych czlonkow");
	puts("Podaj litere odpowiadajaca wybranej opcji:");
	puts("d) dodaj zwierze		w) wyswietl liste zwierzat");
	puts("l) liczba zwierzat	s) szukaj zwierzecia");
	puts("u) usun zwierze		q) koniec");
	while ((ch = getchar()) != EOF) {
		while (getchar() != '\n')
			continue;
		ch = tolower(ch);
		if (strchr("dwlsuq", ch) == NULL)
			puts("Wpisz d, w, l, s, u lub q:");
		else
			break;
	}
	if (ch == EOF)
		ch = 'q';
	return ch;
}
void dodajzw(Drzewo *wd) {
	Pozycja tymcz;
	if (PelneDrzewo(wd))
		puts("Brak wolnych miejsc w klubie!");
	else {
		puts("Podaj imie zwierzecia:");
		wczytaj(tymcz.imie, MAXROZ);
		puts("Podaj gatunek zwierzecia:");
		wczytaj(tymcz.gatunek, MAXROZ);
		duzelit(tymcz.imie);
		duzelit(tymcz.gatunek);
		DodajPozycje(&tymcz, wd);
	}
}

void wyswpoz(Pozycja pozycja) {
	printf("Zwierze: %-19s	Gatunek: %-19s\n", pozycja.imie, pozycja.gatunek);
}

void pokazzw(const Drzewo *wd) {
	if (PusteDrzewo(wd))
		puts("Brak pozycji!");
	else
		Przejdz(wd, wyswpoz);
}

void szukajzw(const Drzewo *wd) {
	Pozycja tymcz;
	if (PusteDrzewo(wd)) {
		puts("Brak pozycji!");
		return;	//wychodzi z funkcji, jesli drzewo jest puste
	}
	puts("Podaj imie zwierzecia, ktore chcesz znalezc:");
	wczytaj(tymcz.imie, MAXROZ);
	puts("Podaj gatunek zwierzecia:");
	wczytaj(tymcz.gatunek, MAXROZ);
	duzelit(tymcz.imie);
	duzelit(tymcz.gatunek);
	printf("%s, %s ", tymcz.imie, tymcz.gatunek);
	if (WDrzewie(&tymcz, wd))
		printf("jest czlonkiem klubu.\n");
	else
		printf("nie jest czlonkiem klubu.\n");
}

void usunzw(Drzewo *wd) {
	Pozycja tymcz;
	if (PusteDrzewo(wd)) {
		puts("Brak pozycji!");
		return;	//wychodzi z funkcji jesli drzewo jest puste
	}
	puts("Podaj imie zwierzecia, ktore chcesz usunac:");
	wczytaj(tymcz.imie, MAXROZ);
	puts("Podaj gatunek zwierzecia:");
	wczytaj(tymcz.gatunek, MAXROZ);
	duzelit(tymcz.imie);
	duzelit(tymcz.gatunek);
	printf("%s, %s ", tymcz.imie, tymcz.gatunek);
	if (UsunPozycje(&tymcz, wd))
		printf("zostal(a) usuniety/a z klubu.\n");
	else
		printf("nie jest czlonkiem klubu.\n");
}

void duzelit(char *lan) {
	while (*lan != '\0') {
		*lan = toupper(*lan);
		lan++;
	}
}

char *wczytaj(char *z, int ile) {
	char *tutaj, *wynik;
	wynik = fgets(z, ile, stdin);
	if (wynik) {
		tutaj = strchr(z, '\n');
		if (tutaj)
			*tutaj = '\0';
		else
			while (getchar() != '\n')
				continue;
	}
	return wynik;
}