c402.c

/* c402.c: ********************************************************************}
{* Téma: Nerekurzivní implementace operací nad BVS 
**                                     Implementace: Petr Přikryl, prosinec 1994
**                                           Úpravy: Petr Přikryl, listopad 1997
**                                                     Petr Přikryl, květen 1998
**			  	                        Převod do jazyka C: Martin Tuček, srpen 2005
**                                         Úpravy: Bohuslav Křena, listopad 2009
**                                         Upravy: Karel Masarik, rijen 2013
**
** S využitím dynamického přidělování paměti, implementujte NEREKURZIVNĚ
** následující operace nad binárním vyhledávacím stromem (předpona BT znamená
** Binary Tree a je u identifikátorů uvedena kvůli možné kolizi s ostatními
** příklady):
**
**     BTInit .......... inicializace stromu
**     BTInsert ........ nerekurzivní vložení nového uzlu do stromu
**     BTPreorder ...... nerekurzivní průchod typu pre-order
**     BTInorder ....... nerekurzivní průchod typu in-order
**     BTPostorder ..... nerekurzivní průchod typu post-order
**     BTDisposeTree ... zruš všechny uzly stromu
**
** U všech funkcí, které využívají některý z průchodů stromem, implementujte
** pomocnou funkci pro nalezení nejlevějšího uzlu v podstromu.
**
** Přesné definice typů naleznete v souboru c402.h. Uzel stromu je typu tBTNode,
** ukazatel na něj je typu tBTNodePtr. Jeden uzel obsahuje položku int Cont,
** která současně slouží jako užitečný obsah i jako vyhledávací klíč 
** a ukazatele na levý a pravý podstrom (LPtr a RPtr).
**
** Příklad slouží zejména k procvičení nerekurzivních zápisů algoritmů
** nad stromy. Než začnete tento příklad řešit, prostudujte si důkladně
** principy převodu rekurzivních algoritmů na nerekurzivní. Programování
** je především inženýrská disciplína, kde opětné objevování Ameriky nemá
** místo. Pokud se Vám zdá, že by něco šlo zapsat optimálněji, promyslete
** si všechny detaily Vašeho řešení. Povšimněte si typického umístění akcí
** pro různé typy průchodů. Zamyslete se nad modifikací řešených algoritmů
** například pro výpočet počtu uzlů stromu, počtu listů stromu, výšky stromu
** nebo pro vytvoření zrcadlového obrazu stromu (pouze popřehazování ukazatelů
** bez vytváření nových uzlů a rušení starých).
**
** Při průchodech stromem použijte ke zpracování uzlu funkci BTWorkOut().
** Pro zjednodušení práce máte předem připraveny zásobníky pro hodnoty typu
** bool a tBTNodePtr. Pomocnou funkci BTWorkOut ani funkce pro práci
** s pomocnými zásobníky neupravujte 
** Pozor! Je třeba správně rozlišovat, kdy použít dereferenční operátor *
** (typicky při modifikaci) a kdy budeme pracovat pouze se samotným ukazatelem 
** (např. při vyhledávání). V tomto příkladu vám napoví prototypy funkcí.
** Pokud pracujeme s ukazatelem na ukazatel, použijeme dereferenci.
**/

#include "c402.h"
int solved;

void BTWorkOut (tBTNodePtr Ptr)		{
/*   ---------
** Pomocná funkce, kterou budete volat při průchodech stromem pro zpracování
** uzlu určeného ukazatelem Ptr. Tuto funkci neupravujte.
**/
			
	if (Ptr==NULL) 
    printf("Chyba: Funkce BTWorkOut byla volána s NULL argumentem!\n");
  else 
    printf("Výpis hodnoty daného uzlu> %d\n",Ptr->Cont);
}
	
/* -------------------------------------------------------------------------- */
/*
** Funkce pro zásobník hotnot typu tBTNodePtr. Tyto funkce neupravujte.
**/

void SInitP (tStackP *S)  
/*   ------
** Inicializace zásobníku.
**/
{
	S->top = 0;  
}	

void SPushP (tStackP *S, tBTNodePtr ptr)
/*   ------
** Vloží hodnotu na vrchol zásobníku.
**/
{ 
                 /* Při implementaci v poli může dojít k přetečení zásobníku. */
  if (S->top==MAXSTACK) 
    printf("Chyba: Došlo k přetečení zásobníku s ukazateli!\n");
  else {  
		S->top++;  
		S->a[S->top]=ptr;
	}
}	

tBTNodePtr STopPopP (tStackP *S)
/*         --------
** Odstraní prvek z vrcholu zásobníku a současně vrátí jeho hodnotu.
**/
{
                            /* Operace nad prázdným zásobníkem způsobí chybu. */
	if (S->top==0)  {
		printf("Chyba: Došlo k podtečení zásobníku s ukazateli!\n");
		return(NULL);	
	}	
	else {
		return (S->a[S->top--]);
	}	
}

bool SEmptyP (tStackP *S)
/*   -------
** Je-li zásobník prázdný, vrátí hodnotu true.
**/
{
  return(S->top==0);
}	

/* -------------------------------------------------------------------------- */
/*
** Funkce pro zásobník hotnot typu bool. Tyto funkce neupravujte.
*/

void SInitB (tStackB *S) {
/*   ------
** Inicializace zásobníku.
**/

	S->top = 0;  
}	

void SPushB (tStackB *S,bool val) {
/*   ------
** Vloží hodnotu na vrchol zásobníku.
**/
                 /* Při implementaci v poli může dojít k přetečení zásobníku. */
	if (S->top==MAXSTACK) 
		printf("Chyba: Došlo k přetečení zásobníku pro boolean!\n");
	else {
		S->top++;  
		S->a[S->top]=val;
	}	
}

bool STopPopB (tStackB *S) {
/*   --------
** Odstraní prvek z vrcholu zásobníku a současně vrátí jeho hodnotu.
**/
                            /* Operace nad prázdným zásobníkem způsobí chybu. */
	if (S->top==0) {
		printf("Chyba: Došlo k podtečení zásobníku pro boolean!\n");
		return(NULL);	
	}	
	else {  
		return(S->a[S->top--]); 
	}	
}

bool SEmptyB (tStackB *S) {
/*   -------
** Je-li zásobník prázdný, vrátí hodnotu true.
**/
  return(S->top==0);
}

/* -------------------------------------------------------------------------- */
/*
** Následuje jádro domácí úlohy - funkce, které máte implementovat. 
*/

void BTInit (tBTNodePtr *RootPtr)	{
/*   ------
** Provede inicializaci binárního vyhledávacího stromu.
**
** Inicializaci smí programátor volat pouze před prvním použitím binárního
** stromu, protože neuvolňuje uzly neprázdného stromu (a ani to dělat nemůže,
** protože před inicializací jsou hodnoty nedefinované, tedy libovolné).
** Ke zrušení binárního stromu slouží procedura BTDisposeTree.
**	
** Všimněte si, že zde se poprvé v hlavičce objevuje typ ukazatel na ukazatel,	
** proto je třeba při práci s RootPtr použít dereferenční operátor *.
**/
	
	(*RootPtr) = NULL;	////Inicializujeme tak ze Korenovy bude mat hodnotu NULL

}

void BTInsert (tBTNodePtr *RootPtr, int Content) {
/*   --------
** Vloží do stromu nový uzel s hodnotou Content.
**
** Z pohledu vkládání chápejte vytvářený strom jako binární vyhledávací strom,
** kde uzly s hodnotou menší než má otec leží v levém podstromu a uzly větší
** leží vpravo. Pokud vkládaný uzel již existuje, neprovádí se nic (daná hodnota
** se ve stromu může vyskytnout nejvýše jednou). Pokud se vytváří nový uzel,
** vzniká vždy jako list stromu. Funkci implementujte nerekurzivně.
**/
	
	if((*RootPtr) == NULL) 									//Vkladame do prazdneho stromu
	{
		tBTNodePtr PomVar = malloc(sizeof(struct tBTNode));	//alokujeme novy prvok
		
		if(PomVar == NULL)									//ak sa nepodari alokacia
			return;

		(*RootPtr) = PomVar;								//prave vytvorena hodnota bude korenovy uzol, nacita sa donho obsah
		(*RootPtr)->Cont = Content;
		(*RootPtr)->LPtr = NULL;							//Co lavych a pravych uzlov budu mat hodnotu NULL, lebo niesu vytvorene
		(*RootPtr)->RPtr = NULL;
			
	}
	
	else													//Vkladame do neprazdneho stromu
	{
		tBTNodePtr OUzol = NULL;							//OUzol je otcovsky uzol, na zac. hodnota NULL
		tBTNodePtr PomUz = (*RootPtr);						//PomUz - v nom bude ulozeny korenovy uzol, ten sa nezmeni, a s korenovym ulozenym v pom. premennej mozeme dalej pracovat

		while(PomUz != NULL)								
		{
			if(PomUz->Cont > Content)						//Ak bude sucasny korenovy vacsi ako obsah co hladame...
			{	
				OUzol = PomUz;								//Ulozime si sucasny korenovy do Otcovskeho, a zmenime korenovy na ten co je vlavo
				PomUz = PomUz->LPtr;
			}

			else if(PomUz->Cont < Content)					//Symetricke s predch.
			{
				OUzol = PomUz;
				PomUz = PomUz->RPtr;
			}
			else return;									//Inak ukonci
		}
		
	
		tBTNodePtr PomVar = malloc(sizeof(struct tBTNode));	//Alokujeme novy prvok

		if(PomVar == NULL)
			return;

		PomVar->Cont = Content;								//ulozime si do nove vytvoreneho obsah
		PomVar->LPtr = NULL;								//Co lavych a pravych uzlov budu mat hodnotu NULL, lebo niesu vytvorene
		PomVar->RPtr = NULL;
		
		if(OUzol->Cont < Content)							//Ak otcovsky obsah je mensi , novu hodnotu vlozime do toho kt. je pravym poduzlom otcovskeho
			OUzol->RPtr	= PomVar;

		else if(OUzol->Cont > Content)						//symetricke s predchadzajucim
			OUzol->LPtr	= PomVar;
	}

}

/*                                  PREORDER                                  */

void Leftmost_Preorder (tBTNodePtr ptr, tStackP *Stack)	{
/*   -----------------
** Jde po levě větvi podstromu, dokud nenarazí na jeho nejlevější uzel.
**
** Při průchodu Preorder navštívené uzly zpracujeme voláním funkce BTWorkOut()
** a ukazatele na ně is uložíme do zásobníku.
**/

	while(ptr != NULL)			//pokial nebude nalavo NULL, teda az po najlavejsi
	{
		BTWorkOut(ptr);			//Postupne vypisuj a ukladaj na zasobnik.
		SPushP(Stack, ptr);
		ptr = ptr->LPtr; 		//Posun sa o dalsi lavu poduzol, znovu vypis pushni atd.

	}
	
}

void BTPreorder (tBTNodePtr RootPtr)	{
/*   ----------
** Průchod stromem typu preorder implementovaný nerekurzivně s využitím funkce
** Leftmost_Preorder a zásobníku ukazatelů. Zpracování jednoho uzlu stromu
** realizujte jako volání funkce BTWorkOut(). 
**/

	tStackP Stack;						//Pomocny zasobnik
	tBTNodePtr PomUz = RootPtr;
	SInitP(&Stack);

	Leftmost_Preorder(RootPtr, &Stack); //Napln zasobnik a vypis vsetky lave poduzly

	while(!SEmptyP(&Stack))				//Pokial nebude zasobnik prazdny....
	{
		PomUz = STopPopP(&Stack);		//z vrcholu odstran prvok a daj ho do pomocnej premennej
		PomUz = PomUz->RPtr;			//ulozime si pravy poduzol
		
		Leftmost_Preorder(PomUz, &Stack); //znovu (s pravym poduzlom) hladame najlavejsi, a postupne vypisujeme a ukladame na zasobnik...a takto dalej
	}

}


/*                                  INORDER                                   */ 

void Leftmost_Inorder(tBTNodePtr ptr, tStackP *Stack)		{
/*   ----------------
** Jde po levě větvi podstromu, dokud nenarazí na jeho nejlevější uzel.
**
** Při průchodu Inorder ukládáme ukazatele na všechny navštívené uzly do
** zásobníku. 
**/
		
	while(ptr != NULL)				//pokial nebude nalavo NULL, teda az po najlavejsi
	{
		SPushP(Stack, ptr);			//Uloz prvok na zasobnik, ale nevypisuj, to az neskor
		ptr = ptr->LPtr; 			//ulozime si dalsi lavy poduzol

	}
	
}

void BTInorder (tBTNodePtr RootPtr)	{
/*   ---------
** Průchod stromem typu inorder implementovaný nerekurzivně s využitím funkce
** Leftmost_Inorder a zásobníku ukazatelů. Zpracování jednoho uzlu stromu
** realizujte jako volání funkce BTWorkOut(). 
**/
	tStackP Stack;				     //Pomocny zasobnik...aj premenna v kt. bude ulozena hodnota korenoveho uzlu
	tBTNodePtr PomUz = RootPtr;

	SInitP(&Stack);
	Leftmost_Inorder(PomUz, &Stack); //Naplnime zasobnik lavymi poduzlami

	while(!SEmptyP(&Stack))			 //Pokial nebude zasobnik prazdny
	{
		PomUz = STopPopP(&Stack);	 //ulozime si do pomocnej premennej to co je na vrcholu zasobniku (prepiseme sucasne koren, kt. sa tam nachadzal)
		BTWorkOut(PomUz);			 //vypiseme uzol zo zasobniku
	
		if(PomUz->RPtr != NULL)		 //napln zasobnik najlevejsimi uzlami praveho podstromu
			Leftmost_Inorder(PomUz->RPtr, &Stack);
		
	}

}

/*                                 POSTORDER                                  */ 

void Leftmost_Postorder (tBTNodePtr ptr, tStackP *StackP, tStackB *StackB) {
/*           --------
** Jde po levě větvi podstromu, dokud nenarazí na jeho nejlevější uzel.
**
** Při průchodu Postorder ukládáme ukazatele na navštívené uzly do zásobníku
** a současně do zásobníku bool hodnot ukládáme informaci, zda byl uzel
** navštíven poprvé a že se tedy ještě nemá zpracovávat. 
**/
	while(ptr != NULL) 				//pokial nebude najlevejsi uzol laveho podstrom nulovy...
	{
		SPushP(StackP, ptr);		//...ukladaj postupne na zasobnik..
		SPushB(StackB, FALSE);		//...a prirad k nim hodnotu FALSE - este ich teda nespracuvaj
		ptr = ptr->LPtr;
	}

}

void BTPostorder (tBTNodePtr RootPtr)	{
/*           -----------
** Průchod stromem typu postorder implementovaný nerekurzivně s využitím funkce
** Leftmost_Postorder, zásobníku ukazatelů a zásobníku hotdnot typu bool.
** Zpracování jednoho uzlu stromu realizujte jako volání funkce BTWorkOut(). 
**/
	tStackP StackP;					//2 pomocne zasobniky, jeden pre pravdivostne hodnoty - ci mame uz spracuvat alebo nie, a druhy pre prvky stromu (uzly)
	tStackB StackB;
	tBTNodePtr PomUz = RootPtr;

	SInitP(&StackP);
	SInitB(&StackB);
	Leftmost_Postorder(PomUz, &StackP, &StackB); //Naplnime zasobnik vsetkymi najlevejsimi uzlami laveho podstromu
	
	while(!SEmptyP(&StackP))					//Cyklus bezi az po vyprazdnenie zasobniku, teda az pokial nebude na vystupe posledna hodnota
	{
		PomUz = STopPopP(&StackP);				//uloz si hodnotu do pomocneho prvku. zial nemame oddelene implementovane funkcie pop a top...
		SPushP(&StackP, PomUz);					//...preto musime znovu vlozit prvok na zasobnik

		if(!STopPopB(&StackB))					//Ak sme este len raz navstivili uzol, teda vracia hodnotu FALSE , !FALSE = true, teda pojdeme k prvej casti podmien. prikazu
		{
			SPushB(&StackB, TRUE);				//vlozime hodnotu TRUE na bool zasobnik, to znamena ze uz ho najblizsie spracuvame , pretoze uz raz navstiveny bol 
			Leftmost_Postorder(PomUz->RPtr, &StackP, &StackB);	//Hned za tym vlozime na zasobnik prave uzly 
			continue;							//Cyklus ideme od zaciatku, znovu skontrolujeme uzol , ak mame spracuvat pokracujeme 2.vetvou, ak nie(napr. ze je na zas. pravy uzol) tak 1. vetvou
		}
			STopPopP(&StackP);					//uzol sme uz raz navstivili, takze ho dame pred zo zasobniku 
			BTWorkOut(PomUz);					//Vypiseme na vystup uzol , kt. sme naposledy pushli na zasobnik
	}
}


void BTDisposeTree (tBTNodePtr *RootPtr)	{
/*   -------------
** Zruší všechny uzly stromu a korektně uvolní jimi zabranou paměť.
**
** Funkci implementujte nerekurzivně s využitím zásobníku ukazatelů.
**/

	
	if((*RootPtr) == NULL)							//Ak uz je korenovy NULL, nic nerob
		return;			
	else
	{
		tStackP StackP;								//Pomocny zasobnik,pomocou neho sa bude rusit
		SInitP(&StackP);
		tBTNodePtr PomUz = (*RootPtr);				//pomocne premenne
		tBTNodePtr PomUz2 = NULL;

		while(1)									//bezi nekonecny cyklus
		{
			if(!SEmptyP(&StackP))	//ak zasobnik nieje prazdny
			{
				PomUz = STopPopP(&StackP);			//do pomocneho uzlu si vlozime hodnotu zo zasobniku , v cykle uz nic nerobime , pokracujeme dalsou iteraciou
				continue;
			}
			else if(PomUz == NULL) 					//cyklus sa ukonci ,az ked bude sucasny korenovy uzol prazdny
				break;

			PomUz2 = PomUz;
			PomUz = PomUz->LPtr;
			free(PomUz2);
		}

		(*RootPtr) = NULL; 							//Po zruseni celeho stromu proved to iste co pri inicializacii, teda nastav korenovy na NULL
	}
}

/* konec c402.c */