====== 2. domácí úloha ======
[[wp>Binary search tree]]
/* ------------------------------ 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 --------------------------------------- */
/* 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 ----------------------------------- */
/* 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 --------------------------------- */