Binary search tree

c401.c

/* ------------------------------ c401.c ------------------------------------ */
/* Téma: Rekurzivní implementace operací nad BVS (Dynamické pridel.pam.)
**                           Vytvořil: Petr Přikryl, listopad 1994
**                           Úpravy:   Andrea Němcová, prosinec 1995
**                                     Petr Přikryl, duben 1996
**                                     Petr Přikryl, listopad 1997
**           Přepracované do jazyku c: Martin Tuček, rijen 2005
**
** Implementujte rekurzivním způsobem operace nad binárním vyhledávacím
** stromem (BVS; v angličtině BST -- Binary Search Tree).
**
** Klíčem uzlu stromu je jeden znak (obecně jím může být cokoliv, podle
** čeho se vyhledává). Užitečným (vyhledávaným) obsahem je zde integer.
** Uzly s menším klíčem leží vlevo, uzly s větším klíčem leží ve stromu
** vpravo. Využijte dynamického přidělování paměti.
** Rekurzivním způsobem řešte následující procedury a funkce:
**
**   BSTInit ...... inicializace vyhledávacího stromu
**   BSTSearch .... vyhledávání hodnoty uzlu zadaného klíčem
**   BSTInsert .... vkládání nové hodnoty
**   BSTDelete .... rušení uzlu se zadaným klíčem
**   BSTDispose ... rušení celého stromu
**
** Přesnou definici typů naleznete v souboru c401.h; pro přehled --
** ADT BVS je reprezentováno kořenovým ukazatelem stromu typu tBSTNodePtr.
** Uzel stromu (struktura typu tBSTNode) obsahuje ukazatele LPtr a RPtr na levý
** a pravý podstrom, složku char KEY -- klíč, podle kterého se vyhledává,
** a int BSTNodeCont -- obsah uzlu (demonstrativne integer).
**
** !Upozorneni! Je treba, abyste spravne rozlisovali, kdy pouzit dereferencni 
** operator * na samotny ukazatel (tj. kdyz budeme chtit zapsat urcitou hodnotu 
** do tohoto pointeru, typicky modifikacni operace) a kdy budeme pracovat pouze 
** se samotnym ukazatelem (vyhledavaci fce). V techto ulohach poznate tuto
** skutecnost predevsim pomoci prototypu techto fci. V situaci, kdy pracujeme 
** s ukazatelem na ukazatel, je treba pouzit dereferenci.
**
** Poznámka: nepoužívejte nestandardní příkazy (exit(),...) a operace.
*/
 
#include "c401.h"
int solved;
int errflg;
 
void BSTInit (tBSTNodePtr *RootPtr) {
/* Počáteční inicializace stromu před prvním použitím datové struktury.
** Počáteční testování ukazatele není možné, protože obsahuje nedefinovanou
** (tj. libovolnou) hodnotu, která ovšem neodráží reálný stav.
** 
** Všimněte si, ze zde se poprvé v hlavičce objevuje typ ukazatel na ukazatel,
** proto je treba pri práci s RootPtr(přiřazení) použít dereferenční operátor.
** Ten bude ještě třeba použít v procedurách BSTDelete, BSTInsert a BSTDispose.
**/
 
	*RootPtr = NULL; //prazdny strom
 
}
 
 
int BSTSearch (tBSTNodePtr RootPtr, char K, int *Content) {
/* Vyhledávání uzlu v BVS podle zadaného klíče K. Pokud je nalezen, vrací
** funkce hodnotu TRUE a v proměnné Content se vrací obsah příslušného uzlu.
** Pokud příslušný uzel není nalezen, vrací funkce hodnotu FALSE a obsah
** proměnné Content není definován (to znamená, že do ní nebudete nic
** přiřazovat). Při vyhledávání v binárním stromu bychom typicky použili
** cyklus ukončený testem zahrnujícím stav dosažení listu nebo nalezení
** uzlu s klíčem. V tomto případě ovšem test nepoužijte a problém řešte
** rekurzivním volání této funkce (nedeklarujte žádnou pomocnou proceduru
** nebo funkci).
**/
 
	if (RootPtr == NULL) { //kdy je prazdny strom
		return FALSE; //neni co hledat
	} else if (RootPtr -> Key != K) { //jinak kdyz klic neni hledanym
		if (RootPtr -> Key > K) { //kdyz je aktualni klic vetsi nez hledany
			return BSTSearch(RootPtr -> LPtr, K, Content); //zanor se doleva
		} else {
			return BSTSearch(RootPtr -> RPtr, K, Content); //a kdyz mensi tak doprava
		}
	} else {
		*Content = RootPtr -> BSTNodeCont; //nasel jsem a precetl obsah
		return TRUE; //a nasel jsem
	}
 
}
 
 
void BSTInsert (tBSTNodePtr* RootPtr, char K, int Content) {
/* Vloží do stromu hodnotu Content s klíčem K. Pokud již uzel
** se zadaným klíčem existuje, nahradí se obsah uzlu novou hodnotou.
** Nově vytvořený uzel nechť je vždy listem stromu. Řešte rekurzivně.
**
** Tato rekurzivní implementace je poněkud neefektivní, protože se při
** každém rekurzivním zanoření musí kopírovat celý integer "Content" (obecně
** obsah uzlu). V praxi by se tento problém řešil například jedním
** z těcho způsobů:
**  - předáváním proměnné "Content" odkazem (v tom případě je nutné dosazovat
**    při volání proměnnou a není možné přímo zapsat hodnotu);
**  - deklarací vnitřní procedury, které by se parametr předal odkazem;
**    vnější procedura by sloužila jen jako obal (nevolala by se
**    rekurzivně);
**  - při využití předchozí varianty by se do rekurzivní procedury předával
**    předem naplněný nový uzel, který by se na závěr zrušil v případě,
**    že se uzel nepodařilo zařadit (pokud už uzel s tímto klíčem existoval,
**    přepsal by se jen obsah, případně by se uzly vyměnily a ke zrušení
**    by se předal starý uzel);
**
** Nerekurzivní varianta by v tomto případě byla efektivnější jak z hlediska
** rychlosti, tak z hlediska paměťových nároků. Zde však jde o školní
** příklad. Nedeklarujte žádnou pomocnou proceduru nebo funkci, problém
** řešte rekurzivním voláním procedury samé.
**
** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím
** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na 
** ukazatel). Správné zavolání např. na levý podstrom:
** BSTInsert(&((*RootPtr)->LPtr), K, Content)
*/
 
	if (*RootPtr == NULL) { //kdyz vkladam do prazdnyho stromu
		tBSTNodePtr uzel; //novy uzel
		if ((uzel = malloc(sizeof(struct tBSTNode))) == NULL) { //zkusime ho alokovat
			return; //nebo umrem
		}
		uzel -> Key = K; //vloz kliv
		uzel -> BSTNodeCont = Content; //vloz obsah
		uzel -> LPtr = NULL; //prazdny strom nema listy
		uzel -> RPtr = NULL;
		*RootPtr = uzel; // a konecne ho vloz
	} else if (K < (*RootPtr) -> Key) { //nebo kdyz klic je mensi
			BSTInsert(&((*RootPtr) -> LPtr), K, Content); //chci vkladat doleva
	} else if (K > (*RootPtr) -> Key) { //kdyz vetsi
		BSTInsert(&((*RootPtr) -> RPtr), K, Content); //vlozit doprava
	} else {
		(*RootPtr) -> BSTNodeCont = Content; //kdyz uz se nemam kam norit, nalezl jsem a vloz obsah
	}
 
}
 
 
/* POZOR NASLEDUJÍCÍ PROCEDURA BUDE POUŽITA DÁLE, 
** PREČTĚTE SI PROTO PODROBNĚ NEJPRVE KOMENTÁŘ K PROCEDUŘE BSTDELETE(),
** NEŽ ZAČNETE VYTVÁŘET REPLACEBYRIGHTMOST().
*/
void ReplaceByRightmost (tBSTNodePtr PtrReplaced,tBSTNodePtr *RootPtr) {
/* Pomocná procedura pro vyhledání, přestěhování a uvolnění nejpravějšího
** uzlu v podstromu určeném ukazatelem RootPtr. Na vstupu se předpokládá
** hodnota ukazatele RootPtr různá od NULL (zajistěte to testováním před
** volání procedury). Dále se předpokládá, že pomocný ukazatel PtrReplaced
** ukazuje na uzel, který se má naplnit hodnotami vyhledaného uzlu.
*/
  tBSTNodePtr ptr; /* používejte tento pomocný ukazatel */
  ptr = NULL;
 
	if ((*RootPtr) -> RPtr != NULL) { //kdyz vravo neco je
		ReplaceByRightmost(PtrReplaced, &((*RootPtr) -> RPtr)); //bez doprava
	} else { //no a kdyz tam nic neni
		PtrReplaced -> BSTNodeCont = (*RootPtr) -> BSTNodeCont; //nahrad obsah
		PtrReplaced -> Key = (*RootPtr) -> Key; //nahrad klic
		ptr = *RootPtr; //zalohuj koren
		*RootPtr = (*RootPtr) -> LPtr; //novy koren
		free(ptr); //uvolni stary koren
	}
 
}
 
 
void BSTDelete (tBSTNodePtr *RootPtr, char K) {
/* Zruší uzel stromu, který obsahuje klíč K. Pokud uzel se zadaným klíčem
** neexistuje, nedělá nic. Veškeré manipulace řešte rekurzivně.
**
** Pokud má rušený uzel jen jeden podstrom, pak jej zdědí otec. Pokud má
** oba podstromy, pak je rušený uzel nahrazen nejpravějším uzlem levého
** podstromu. Pozor! Nejpravější uzel nemusí být listem. Pro tuto operaci
** jsme deklarovali proceduru ReplaceByRightmost -- viz. její komentář
** uveden výše.
** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím
** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na 
** ukazatel). Správné zavolání např. na levý podstrom:
** BSTDelete(&((*RootPtr)->LPtr), K).
** Podobně je tomu tak i u ReplaceByRightMost().  
** Například: ReplaceByRightmost(*RootPtr, (&((*RootPtr)->LPtr)))
*/
  tBSTNodePtr ptr;  /* používejte tento pomocný ukazatel */
  ptr=NULL;
 
	if (*RootPtr != NULL) { //kdyz je co mazat
		if (K < (*RootPtr) -> Key) { //kdyz je klic mensi
			BSTDelete(&((*RootPtr) -> LPtr), K); //bez doleva
		} else {
			if (K > (*RootPtr) -> Key) { //kdyz je klic vetsi
				BSTDelete(&((*RootPtr) -> RPtr), K); //bez doprava
			} else {
				ptr = *RootPtr; //zalohuj koren
				if (ptr -> RPtr == NULL) { //kdyz koren vpravo nic nema
					(*RootPtr) = ptr -> LPtr; //koren bude levej
					free(ptr); //uvolni starej koren
				} else {
					if (ptr -> LPtr == NULL) { //kdyz koren vlevo nic nema
						(*RootPtr) = ptr -> RPtr; //koren bude prvej
						free(ptr); //uvolni starej koren
					} else {
						ReplaceByRightmost(*RootPtr, (&((*RootPtr) -> LPtr))); //jinak kouzli
					}
				}
			}
		}
	}
 
} 
 
 
void BSTDispose (tBSTNodePtr *RootPtr) {
/* Korektně zruší celý binární vyhledávací strom. Zvolte nejvýhodnější
** druh rekurzívního průchodu stromem. Nedeklarujte žádné pomocné procedury
** nebo funkce.
** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím
** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na 
** ukazatel). Správné zavolání např. na levý podstrom:
** BSTDispose(&(*RootPtr)->LPtr).
*/
 
	if (*RootPtr != NULL) { //kdyz je co sidposovat
		BSTDispose(&(*RootPtr) -> RPtr); //disposuj doprava
		BSTDispose(&(*RootPtr) -> LPtr); //dsposuj doleva
		free(*RootPtr); //uvolni
		*RootPtr = NULL; //a oznac za prazdny
	}
 
//solved = FALSE;
}
 
/* --------------------------- konec c401.c -------------------------------- */

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

c403.c

/* ------------------------------- c403.c ----------------------------------- */
/* Téma: Vyhledávací tabulka v neseřazeném poli se zarážkou (optimalizace)
**       První implementace: Petr Přikryl, prosinec 1994
**       Úpravy: Petr Přikryl, listopad 1997, květen 1998
**       Další úprava: Martin Tuček, srpen 2005 (jazyk C)
**       Další úprava: Roman Lukáš, říjen 2006
**
** Implementujte vyhledávací tabulku podle následujících požadavků.
** Tabulka je implementována v poli, obsah prvků pole není seřazen.
** Při vyhledávání se sekvenčně prochází celé využité pole s využitím
** takzvané zarážky. Maximální kapacita tabulky je tedy o jedničku nižší,
** než maximální využitelná kapacita pole. Implementujte následující procedury
** a funkce (zkratka AS pochází ze slova Array = pole a Sentinel = zde zarážka):
** 
**   ASInit ..... inicializace tabulky
**   ASSearch ... vyhledávání se zarážkou v neseřazeném poli
**   ASInsert ... vkládání do neseřazeného pole s využitím ASSearch
**
** Při každém vyhledání se optimalizuje doba vyhledávání často hledaných
** položek tím, že se nalezená položka vždy posunuje o jedno místo směrem
** k začátku pole.
**
** Definici typů naleznete v souboru c403.h. Tabulka je reprezentována
** datovou strukturou typu tASTable, která se skládá z pole 'arr' a indexu
** poslední využité položky pole 'last'. Položky pole jsou tvořeny záznamy
** typu tASData, ve kterých se nachází složka Key (klíčem je pro jednoduchost
** číslo typu integer) a obsah Cont (demonstrativně int). Při implementaci těl
** řešených procedur uvažujte maximální rozměr pole ASSize (viz poznámka
** v c403.h).
**
** Důležitým rysem vyhledávacích metod je počet porovnávání vyhledávaného
** klíče s klíči prohledávaných položek pole. K porovnávání využívejte
** povinně funkce ASCompare (viz dále). Počet porovnávání omezte
** na minimum. To znamená, že nebudete volat podruhé funkci ASCompare
** pro stejné klíče tam, kde jste si mohli výsledek porovnání zapamatovat
** v pomocné proměnné.
*/
 
#include "c403.h"
int ASCompNum;
int solved;
int errflg;
 
int ASCompare (int k1, int k2) {
  ASCompNum = ASCompNum + 1;      /* počet porovnání */ 
  if (k1 < k2)                    /* porovnání dvou klíčů */
    return(-1);
  else if (k1 == k2)
    return(0);
  else                            /* k1 > k2 */ 
    return(1);
}
 
void ASError() {
  printf("Chyba: Polozka jiz nemuze byt vlozena\n");
  errflg = TRUE;
}
/* ------------------------------------------------------------------------- */
void ASInit(tASTable *Tab) {
/* Inicializace tabulky (výsledkem je prázdná tabulka).
** Inicializace tabulky se provede tak, že se index posledního prvku nastaví na
** hodnotu -1. Hodnoty prvků ani klíčů se v tabulce nemění.
*/
 
	Tab -> last = -1;
 
}
 
 
int ASSearch (tASTable *Tab, int key, int* ind) {
/* Vyhledávání v NESEŘAZENÉM poli se zarážkou a s přesunem nalezené
** položky o jednu pozici dopředu (výměna s předchozí položkou).
**
** Vyhledávacím klíčem je hodnota key. Funkce vrací příznak, zda byl prvek
** nalezen. Pokud ne (vrací false), pak se v proměnné 'ind' vrací první
** volná pozice, na kterou se může prvek vložit.
** Pokud byl prvek nalezen (vrací true), došlo k jeho posunutí o jednu
** pozici dopředu a v proměnné ind se vrací nová pozice nalezeného prvku.
**
** Pro porovnání dvou klíčů používejte předdefinovanou funkci ASCompare
** (viz. výše). Vzhledem k tomu, že se při vyhledávání vždy používá
** zarážka, bude minimální počet porovnání (při prázdné tabulce) roven 1.
**
** POZOR!!!
** Při vložení zarážky se hodnota 'last' NEMĚNÍ! Zarážka se tedy nachází
** na pozici 'last' + 1. Zarážka může obsahovat obecně libovolnou hodnotu, 
** vy ale hodnotu zarážky nastavte na -1, aby se vám shodovaly výsledky testů!
*/
 
	Tab -> arr[Tab -> last + 1].Key = key; //zarazka klice
	Tab -> arr[Tab -> last + 1].Cont = -1; //zarazka obsahu
	unsigned int index = 0; //index pole
	while (ASCompare(key, Tab -> arr[index].Key) != 0) { // dokud jsme nenasli klic (nebo zarazku)
		index++; //pousunujeme se v poli
	}
	if (index != Tab -> last + 1) { //kdyz jsme nenasli zarazku, budeme prohazovat prvky
		if (index > 0) { //prvek uplne na zacatku uz by nebylo s cim prohodit
			tASData swap = Tab -> arr[index]; //zalohujeme nalezeny prvek
			Tab -> arr[index] = Tab -> arr[index - 1]; //prohodime prvky
			Tab -> arr[index - 1] = swap; //vlozime nalezeny prvek
			index--; //taku by bylo dobry aby index ukazoval spravne ;)
		}
		*ind = index; //nastavime nalezeny index
		return TRUE; //a skoncime
	}
	*ind = index; //nastavime nalezeny index (na prazdny prvek)
	return FALSE; //skoncime
 
}
 
 
void ASInsert (tASTable *Tab, int Key, int Content) {
/* Vloží novou položku s obsahem Content a klíčem Key do tabulky Tab.
**
** Pokud by vložením další položky došlo k přeplnění Tab (pokud by nešlo
** při dalším vyhledávání uložit zarážku), volejte proceduru ASError()
** a novou položku nevkládejte.
**
** Pokud daná položka (udaná klíčem Key) v poli již existuje, přiřadí se do
** odpovídající složky záznamu nový obsah. Při vyhledávání již existující 
** položky využijte dříve implementovanou funkci ASSearch (to znamená, že se
** existující a modifikovaná položka automaticky posune dopředu).
*/
 
	int index = 0; //index polozky v poli
	short nasli = ASSearch(Tab, Key, &index); //zjistime jestli nahodou takovy klic uz neexistuje (a posuneme ho)
	if (nasli) { //kdyz uz klic existuje
		Tab -> arr[index].Cont = Content; //zapiseme novou hodnutu
	} else { //klic neexistuje, vlozime novy
		if (index > ASSize - 2) { //bacha, lezem za roh (-2 kvuli zarazce a indexovani od 0)
			ASError(); //zakric
		} else { //vlezeme se
			Tab -> arr[index].Key = Key; //novy klic
			Tab -> arr[index].Cont = Content; //novy obsah
			Tab -> last = index; //nova posledni prazdna polozka
		}
	}
 
}
 
/* -------------------------- konec c403.c --------------------------------- */