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