/* --------------------------- 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řepracované do jazyku c: Martin Tuček, srpen 2005
**
** S využitím dynamického přidělování paměti, implementujte
** následující operace nad binárním vyhledávacím stromem -- vše NEREKURZIVNĚ.
** (BT znamená Binary Tree; Tato předpona je u procedur uvedena kvůli možné
** kolizi jmen v ostatních příkladech):
**
**     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 procedur, které využívají některý z průchodů stromem, deklarujte
** lokální proceduru nazvanou Leftmost -- nalezení nejlevějšího uzlu
** v podstromu (viz přednášky, kde se tato procedura jmenovala Nejlev).
**
** Definice typů naleznete v souboru c402.h; uzel stromu je typu tBTNode,
** ukazatel na něj je typu tBTNodePtr, uzel obsahuje položku int Cont
** (obsah) a ukazatele 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ů
** pro výpočet počtu uzlů stromu, počtu listů stromu, výšky stromu a 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 proceduru BTWorkOut().
** Pro práci se zásobníky použijte rovněž předem připravené procedury
** a funkce. K dispozici máte zásobníky pro hodnoty typu boolean
** a tBTNodePtr (SInit*, SPush*, STopPop*, SEmpty*, kde místo '*' použijete
** 'P' pro zásobník s ukazateli nebo 'B' pro zásobník s boolovskými hodnotami.
**
** !Upozornění! Je třeba, abyste spravně rozlišovali, kdy použit dereferenční 
** operátor * na samotný ukazatel a kdy budeme pracovat pouze se samotným 
** ukazatelem (prohledavaci fce). V techto úlohách poznáte tuto skutečnost 
** predevším pomocí prototypu těchto funkcí. V situaci, kdy pracujeme s 
** ukazatelem na ukazatel, je třeba použít dereferenci.
*/
#include "c402.h"
int solved;
int errflg;

void BTWorkOut (tBTNodePtr Ptr) {
/* Pomocná procedura používaná při průchodech stromem.
** Zpracuje uzel, na který ukazuje Ptr. 
** Nemodifikovat!
*/

  if (Ptr == NULL) 
    printf("NULL\n");
  else 
    printf("Vypis hodnoty daneho uzlu> %d\n", Ptr->Cont);
}
  
/* -------------------------------------------------------------------------- */
/* Implementace zásobníků je velmi zjednodušena. Zdrojový text je formátován
** s ohledem na úsporu místa a není příliš komentován (neberte si z toho
** příklad -- když, tak odstrašující). Definice datovych struktur, viz. 
** hlavickovy soubor. 
*/

/* *********************** OPERACE SE ZÁSOBNÍKEM **************************** */

/* ----------------------- Zásobník ukazatelů: ------------------------------ */
void SInitP (tStackP *S) {
/* inicializace zásobníku ukazatelů */
  S->top = 0;  
}

void SPushP (tStackP *S, tBTNodePtr ptr) {
/* vloží hodnotu na vrchol zásobníku */
  if (S->top==MAXSTACK) 
    printf("Přetečení zásobníku s ukazateli!\n");
  else {  
    S->top++;  
    S->a[S->top] = ptr;  
  }
}

tBTNodePtr STopPopP (tStackP *S) {
/* vrací odstraněnou hodnotu */
  if (S->top == 0)  {
    printf("Podtečení zásobníku s ukazateli!\n");
    return(NULL);  
  }
  else {
    return (S->a[S->top--]);
  }
}

bool SEmptyP (tStackP *S) {
/* test na prázdnost zásobníku */
  if (S->top == 0)
    return(true);
  else
    return(false);
}


/* ----------------------- Zásobník boolovských hodnot: --------------------- */
void SInitB (tStackB *S) {
/* inicializace zásobníku */
  S->top = 0;  
}

void SPushB (tStackB *S,bool val) {
/* vloží hodnotu na vrchol zásobníku */
  if (S->top == MAXSTACK) 
    printf("Přetečení zásobníku pro boolean!\n");
  else {
    S->top++;  
    S->a[S->top] = val;
  }
}

bool STopPopB (tStackB *S) {
/* vrací odstraněnou hodnotu */
  if (S->top == 0) {
    printf("Podtečení zásobníku pro boolean!\n");
    return(NULL);  
  } 
  else {
    return(S->a[S->top--]); 
  }
}

bool SEmptyB (tStackB *S) {
  if (S->top == 0)
    return(true);
  else 
    return(false);  
}

/* ---------------------------------- INIT ---------------------------------- */
void BTInit (tBTNodePtr *RootPtr) {
/* Inicializace stromu. Smí se volat pouze před prvním použitím
** konkrétního binárního stromu, protože neuvolňuje uzly neprázdného
** stromu (ani to dělat nemůže). K rušení neprázdného stromu slouží
** procedura BTDisposeTree (viz dále).
**
** 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(přiřazení) použít dereferenční operator.
** Ten bude ještě třeba použít v procedurách BTInsert() a BTDisposeTree().
*/

	*RootPtr = NULL; //prazdny strom

}


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 (BVS = BST),
** kde uzly s hodnotou menší než má otec leží v levém podstromu, uzly větší
** leží vpravo. Pokud vkládaný uzel již existuje, neprovádí se nic (hodnota
** se ve stromu vyskytuje maximálně jedenkrát). Pokud se vytváří nový uzel,
** vzniká vždy jako list stromu. Řešte nerekurzivně.
*/
  tBTNodePtr fptr;  /* ukazatel na otcovský uzel F */
  tBTNodePtr ptr;   /* pomocný ukazatel */
  bool myend;       /* příznak ukončení cyklu */

/* V případě, kdy strom není prázdný, musíme vyhledat místo, kam by se nová 
** hodnota měla vložit. Pokud uzel se zadanou hodnotou již existuje, neděláme 
** nic. Pokud se bude uzel vytvářet, musíme si pamatovat ukazatel na otce, 
** na kterého bude nový uzel připojen.
*/

	if (*RootPtr == NULL) { //kdyz mam prazdnys trom
		if ((ptr = malloc(sizeof(struct tBTNode))) == NULL) { //zkusim alokovat pomocny uzel
			return; //nebo umru
		}
		ptr -> Cont = Content; //novy obsah
		ptr -> LPtr = NULL; //jednoprvkovy strom nema listy
		ptr -> RPtr = NULL; //jednprvkovy strom strom nema listy
		*RootPtr = ptr;
	} else { //kdyz uz ve stromu neco je
		ptr = *RootPtr; //ulozim koren
		while (ptr != NULL) { //dokud je nakej koren
			fptr = ptr; //tak ten koren bude otec
			if (ptr -> Cont == Content) { //kdyz uz takovy uzel existuje
				return; //nedelej nic
			} else if (ptr -> Cont > Content) { //kdyz je vkladany mensi nez aktualni
				ptr = ptr -> LPtr; //jdi doleva
			} else if (ptr -> Cont < Content) { //kdyz je vkladany vetsi nez aktualni
				ptr = ptr -> RPtr; //jdi doprava
			}
		}
		myend = true; //aby to nervalo chwarning
		if ((ptr = malloc(sizeof(struct tBTNode))) == NULL) { //alokuj novy uzel
			return; //nebo umri
		}
		ptr -> Cont = Content; //obsah
		ptr -> LPtr = NULL; //list nema podprvky
		ptr -> RPtr = NULL;
		if (fptr -> Cont > Content) { //znovu se porovna novy obsah s otcem a zvoli se na kterou stranu se pripoji novy uzel
			fptr -> LPtr = ptr;
		} else {
			fptr -> RPtr = ptr;
		}
	}

}

/* Nyní následuje sekce jednotlivých průchodů stromem, před tvorbou Leftmost
čtěte vždy i popisek nasledujíci procedury = implikace řešení daného Leftmost */

/* ------------------------------ PREORDER ---------------------------------- */
void Leftmost_Preorder (tBTNodePtr ptr, tStackP *Stack) {
/* Lokální procedura BTPreorder -- funkce viz přednášky.
** Pohybuje se po levé větvi podstromu, až narazí na jeho nejlevější uzel.
** Ukazatele na všechny navštívené uzly ukládá do zásobníku. Protože jde
** o průchod typu preorder, je navštívený uzel současně zpracován, použijte
** BTWorkOut(). 
*/

	while (ptr != NULL) { //dokud je co resit
		SPushP(Stack, ptr); //pushni uzel na stack
		BTWorkOut(ptr); //napis uzel
		ptr = ptr -> LPtr; //bez doleva
	}

}

void BTPreorder (tBTNodePtr RootPtr) {
/* Samotný nerekurzivní průchod typu pre-order, použijte dané Leftmost_Preorder
** dle prednášek. 
*/
  tStackP Stack ;  /* zásobník ukazatelů */
  tBTNodePtr ptr;  /* pomocný ukazatel na uzel */

	SInitP(&Stack);
	Leftmost_Preorder(RootPtr, &Stack); //pis levy dokud to jde
	while (!SEmptyP(&Stack)) { //dokud neprojdes uplne doprava
		ptr = STopPopP(&Stack); //popni posledni uzel
		Leftmost_Preorder(ptr -> RPtr, &Stack); //bez od nej doprava
	}

}


/* ------------------------------ IN ORDER ---------------------------------- */
void Leftmost_Inorder(tBTNodePtr ptr, tStackP *Stack) {
/* Lokální procedura BTInorder -- funkce viz přednášky.
** Pohybuje se po levé větvi podstromu, až narazí na jeho nejlevější uzel.
** Ukazatele na všechny navštívené uzly ukládá do zásobníku. 
*/

	while (ptr != NULL) { //dokud je co resit
		SPushP(Stack, ptr); //pushni uzel
		ptr = ptr -> LPtr; //bez doleva
	}

}


void BTInorder (tBTNodePtr RootPtr) {
/* Nerekurzivní průchod typu in-order. Pro zpracování uzlu volejte
** proceduru BTWorkOut a pracujte s LeftMost_Inorder.
*/
  tStackP Stack;  /* zásobník ukazatelů */
  tBTNodePtr ptr; /* pomocný ukazatel na uzel */

	SInitP(&Stack);
	Leftmost_Inorder(RootPtr, &Stack); //bez doleva co to jde
	while (!SEmptyP(&Stack)) { //dokud je neco na stacku
		ptr = STopPopP(&Stack); //vyvolej posledni uzel
		BTWorkOut(ptr); //vypis uzel
		Leftmost_Inorder(ptr -> RPtr, &Stack); //bez doprava
	}

}


/* ------------------------------ POST ORDER -------------------------------- */
void Leftmost_Postorder (tBTNodePtr ptr, tStackP *StackP, tStackB *StackB) {
/* Lokální procedura pro Postorder -- funkce viz přednášky.
** Pohybuje se po levé větvi podstromu, až narazí na jeho nejlevější uzel.
** Ukazatele na všechny navštívené uzly ukládá do zásobníku. Protože jde
** o průchod typu postorder, je současně do boolovského zásobníku ukládána
** hodnota, která říká, že uzel byl navštíven poprvé (při průchodu do
** levého podstromu) a že se tedy ještě nemá zpracovávat.
*/

	while (ptr != NULL) { //dokud je co resit
		SPushP(StackP, ptr); //pushni uzel
		SPushB(StackB, ptr); //uz jsem tam byl
		ptr = ptr -> LPtr; //bez doleva
	}

}


void BTPostorder (tBTNodePtr RootPtr) {
/* Nerekurzivní průchod typu post-order. Pro zpracování uzlu volejte
** proceduru BTWorkOut.
*/
  tStackP StackP;  /* zásobník ukazatelů */
  tBTNodePtr ptr;  /* pomocný ukazatel na uzel */
  tStackB StackB;  /* zásobník boolovských hodnot */

	SInitP(&StackP);
	SInitB(&StackB);
	Leftmost_Postorder(RootPtr, &StackP, &StackB); //bez doleva co to jde
	while (!SEmptyP(&StackP)) { //dokud mame uzly k reseni
		ptr = STopPopP(&StackP); //vyvolej uzel
		SPushP(&StackP, ptr); //zase ho vrat
		if (STopPopB(&StackB)) { //kdyz jsem v uzlu jeste nebyl
			SPushB(&StackB, false); //tak uz jsem tam byl
			Leftmost_Postorder(ptr -> RPtr, &StackP, &StackB); //a jdi doprava
		} else { //kdyz uz jsem v uzlu byl
			STopPopP(&StackP); //vyvolej uzel
			BTWorkOut(ptr); //vypis
		}
	}

}

/* ------------------------------ DISPOSE ----------------------------------- */
void BTDisposeTree (tBTNodePtr *RootPtr)  {
/* Zruší všechny uzly stromu -- uvolní jimi zabíraný prostor voláním
** standardní funkce free.
**
** Pozn.: při rušení uzlů stromu není důležité, v jakém pořadí se budou rušit,
** proto můžete uvažovat i jiné varianty, než klasické typy průchodu stromem.
*/
  tStackP S;       /* zásobník ukazatelů */
  tBTNodePtr ptr;  /* pomocný ukazatel na uzel */

	if (*RootPtr != NULL) { //kdyz neni prazdny strom
		SInitP(&S);
		do {
			if (*RootPtr == NULL && !SEmptyP(&S)) { //kdyz uz je strom prazdny ale stack neni prazdny
				*RootPtr = STopPopP(&S); //precti neco ze stacku
			} else {
				if ((*RootPtr) -> RPtr != NULL) { //kdyz vpravo neco je
					SPushP(&S, (*RootPtr) -> RPtr); //narvi to na stack
				}
				ptr = *RootPtr; //zalohuj koren
				*RootPtr = (*RootPtr) -> LPtr; //novy koren
				free(ptr); //zrus stary koren
			}
		} while (!SEmptyP(&S) || *RootPtr != NULL); //vyse uvedene delj doku je neco na stacku nebo dokud neni prazdny koren
	}

}

/* ----------------------------- konec c402.c ------------------------------- */