c402

/* 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
**
** 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 *.
**/


	//nastavim prvni prvek na NULL

	(*RootPtr)=NULL;
	 //solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}

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ě.
**/

		//vytvorim si novy list
		tBTNodePtr item=NULL,item_2=NULL;
		item_2=malloc(sizeof(tBTNodePtr)*sizeof(tBTNodePtr)*sizeof(tBTNodePtr)*sizeof(int));
		item_2->Cont=Content;
		item_2->LPtr=NULL;
		item_2->RPtr=NULL;

		//pokud jsme na zacatku okamzite ho ulozim
		if ((*RootPtr)==NULL)
			(*RootPtr)=item_2;

		//jinak projdu cely strom a ulozim ho na konec
		else
		{
			//pomocna pro pruchod stromu
			item=(*RootPtr);

			//dokud jsme nenrazili na konec stromu
			while (item!=NULL)
			{

				//pokud se tam jiz tato hodnota nachazi, uvolnim novy list a koncim funkci
				if (item->Cont == Content)
				{
					free(item_2);
					return ;
				}

				//pokud je hodnota vetsi nez hledany prvek jdu do leva
				else if (item->Cont > Content)
				{

					//pokud se v levo nic nenachazi, ulozim tam nove vytvoreny list a koncim funkci
					if (item->LPtr==NULL)
					{
						item->LPtr=item_2;
						return;
					}
					//pokud, ale v levo neco je, nactu levy uzel a pokracuji v cyklu
					item=item->LPtr;
				}
				//pokud je hodnota mensi nez hledany prvek jdu do prava
				else if (item->Cont < Content)
				{

					//pokud se v pravo nic nenachazi, ulozim tam nove vytvoreny list a koncim funkci
					if (item->RPtr==NULL)
					{
						item->RPtr=item_2;
						return;
					}

					//pokud, ale v pravo neco je, nactu pravy uzel a pokracuji v cyklu
					item=item->RPtr;
				}
			}
		}

	//solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}

/*                                  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.
**/

	//s pouzitim zasobniku prochazim strom
	tBTNodePtr item;
	item=ptr;

	//dokud nejsme na konci
	while (item!=NULL)
	{
		//tisknu uzel, na kterem se nachazim
		BTWorkOut(item);

		//ulozim uzel pro pozdejsi pruchod do prava na zasobnik
		SPushP(Stack,item);

		//a jdu do leva
		item=item->LPtr;
	}


	 //solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}

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().
**/

	//pokud ve strome vubec neco je
	if (RootPtr!=NULL)
	{

		//inicializace zasobniku, pomocneho stromu a prvni pruchod do leva
		//mam radsi dynamicke zasobniky
		tStackP *Stack=NULL;
		Stack=malloc (sizeof (tStackP));
		tBTNodePtr item=RootPtr;
		SInitP(Stack);
		Leftmost_Preorder(item,Stack);

		//dokud enni zasobnik prazdny
		while (!SEmptyP(Stack))
		{

			//do promenne ulozim ukazatel na uzel
			item=STopPopP(Stack);

			//a projfu uzel tentokrat do prava
			Leftmost_Preorder(item->RPtr,Stack);
		}
		free (Stack);
	}
	 //solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}


/*                                  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.
**/
	//s pouzitim zasobniku prochazim strom
	tBTNodePtr item;
	item=ptr;

	//dokud nejsme na konci
	while (item!=NULL)
	{
		//dam stavajici uzel na zasobnik pro pozdejsi pruchod do prava
		SPushP(Stack,item);

		//a jdu do leva
		item=item->LPtr;
	}



	// solved = FALSE;		  /* V případě řešení smažte tento řádek! */

}

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().
**/

	//pokud vubec neco je ve strome
	if (RootPtr!=NULL)
	{

		//pocatecni inicializace a vytvoreni zasobniku
		//mam radsi dynamicke zasobniky
		tStackP *Stack=NULL;
		Stack=malloc (sizeof (tStackP));
		tBTNodePtr item=RootPtr;
		SInitP(Stack);

		//prvni pruchod do leva
		Leftmost_Inorder(item,Stack);
		while (!SEmptyP(Stack))
		{

			//vytahnu si ze zasobniku prvni uzel
			item=STopPopP(Stack);
			//vytisknu ho
			BTWorkOut(item);

			//a prochazim jeho pravy list do leva
			Leftmost_Inorder(item->RPtr,Stack);
		}
		free (Stack);
	}

	// solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}

/*                                 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.
**/

	//s pouzitim dvou zasobniku prochazim strom
	tBTNodePtr item;
	item=ptr;

	//dkud nejsme na konci stromu
	while (item!=NULL)
	{

		//na zasobnik ulozim stavajici uzel
		SPushP(StackP,item);

		//a ulozim ze jsem sel do leva
		SPushB(StackB,true);
		item=item->LPtr;
	}


	//solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}

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().
**/
	if (RootPtr!=NULL)
	{

		//ininicializace promennych a zasobniku
		bool left;

		//mam radsi dynamicke zasobniky
		tStackP *StackP=NULL;
		StackP=malloc (sizeof (tStackP));
		tStackB *StackB=NULL;
		StackB=malloc (sizeof (tStackB));
		tBTNodePtr item;
		item = RootPtr;
		SInitP(StackP);
		SInitB(StackB);

		//prvni pruchod do leva
		Leftmost_Postorder(item,StackP,StackB);
		while (!SEmptyP(StackP))
		{
			//vytahnu si prvni uzel ze saboniku
			item=STopPopP(StackP);
			//ale on tam musi zustat
			SPushP(StackP,item);

			//zjistim, jestli jsem posledne sel do leva
			left=STopPopB(StackB);

			//pokud ano
			if (left)
			{
				//pujdu do prava
				SPushB(StackB,false);
				Leftmost_Postorder(item->RPtr,StackP,StackB);
			}

			//pokud jsem sel do prava
			else
			{
				//vytahnu uzel
				item=STopPopP(StackP);
				//a vytisknu ho
				BTWorkOut(item);
			}
		}
		free(StackP);
		free(StackB);
	}
	//solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}


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ů.
**/
	//pokud ve stromu vubec neco je, tak ho smazu
	if ((*RootPtr)!=NULL)
	{

		//mama radsi dynamicke zasobniky
		tStackP *StackP=NULL;
		StackP=malloc (sizeof (tStackP));
		tBTNodePtr item_2;
		SInitP(StackP);

		//cyklus repeat
		do
		{
			//pokud jsme na konci vetve
			if ((*RootPtr)==NULL)
			{
				//a neni prazdny zasobnik, tak si vytahneme uzel a pokracujeme v cyklu
				if (!SEmptyP(StackP))
					(*RootPtr)=STopPopP(StackP);
			}

			//pokud jsme nekde uprostred vetve
			else
			{
				//pokud ve stavajicim uzlu v pravo neco je, ulozim uzel na zasobnik
				if ((*RootPtr)->RPtr!=NULL)
					SPushP(StackP,(*RootPtr)->RPtr);

				//posunu se do leva a prvek, na kterem jsem doposud byl odsranim
				item_2=(*RootPtr);
				(*RootPtr)=(*RootPtr)->LPtr;
				free(item_2);
				item_2=NULL;
			}
		}
		while (!((*RootPtr)==NULL && SEmptyP(StackP)));
		//cyklus do while, pracuje podobne jako repeat v pascalu, s tim rozdilem ze
		//ukoncovaci podminku musime znegovat

		free(StackP);
	}

	//solved = FALSE;		  /* V případě řešení smažte tento řádek! */
}

/* konec c402.c */