426 lines
12 KiB
C
426 lines
12 KiB
C
/*
|
|
* Binární vyhledávací strom — iterativní varianta
|
|
*
|
|
* S využitím datových typů ze souboru btree.h, zásobníku ze souboru stack.h
|
|
* a připravených koster funkcí implementujte binární vyhledávací
|
|
* strom bez použití rekurze.
|
|
*/
|
|
|
|
#include "../btree.h"
|
|
#include "stack.h"
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
/*
|
|
* Inicializace stromu.
|
|
*
|
|
* Uživatel musí zajistit, že inicializace se nebude opakovaně volat nad
|
|
* inicializovaným stromem. V opačném případě může dojít k úniku paměti (memory
|
|
* leak). Protože neinicializovaný ukazatel má nedefinovanou hodnotu, není
|
|
* možné toto detekovat ve funkci.
|
|
*/
|
|
void bst_init(bst_node_t **tree)
|
|
{
|
|
*tree = NULL; // Inicializácia prázdneho stromu
|
|
}
|
|
|
|
/*
|
|
* Vyhledání uzlu v stromu.
|
|
*
|
|
* V případě úspěchu vrátí funkce hodnotu true a do proměnné value zapíše
|
|
* ukazatel na obsah daného uzlu. V opačném případě funkce vrátí hodnotu false a proměnná
|
|
* value zůstává nezměněná.
|
|
*
|
|
* Funkci implementujte iterativně bez použité vlastních pomocných funkcí.
|
|
*/
|
|
bool bst_search(bst_node_t *tree, char key, bst_node_content_t **value)
|
|
{
|
|
bst_node_t *current = tree;
|
|
|
|
// Iteratívne prechádzame strom
|
|
while (current != NULL) {
|
|
if (key == current->key) {
|
|
// Našli sme hľadaný kľúč
|
|
*value = &(current->content);
|
|
return true;
|
|
}
|
|
// Ak je kľúč menší, ideme do ľavého podstromu
|
|
if (key < current->key) {
|
|
current = current->left;
|
|
}
|
|
// Ak je kľúč väčší, ideme do pravého podstromu
|
|
else {
|
|
current = current->right;
|
|
}
|
|
}
|
|
|
|
return false; // Kľúč nebol nájdený
|
|
}
|
|
|
|
/*
|
|
* Vložení uzlu do stromu.
|
|
*
|
|
* Pokud uzel se zadaným klíče už ve stromu existuje, nahraďte jeho hodnotu.
|
|
* Jinak vložte nový listový uzel.
|
|
*
|
|
* Výsledný strom musí splňovat podmínku vyhledávacího stromu — levý podstrom
|
|
* uzlu obsahuje jenom menší klíče, pravý větší.
|
|
*
|
|
* Funkci implementujte iterativně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_insert(bst_node_t **tree, char key, bst_node_content_t value)
|
|
{
|
|
// Ak je strom prázdny, vytvoríme nový koreň
|
|
if (*tree == NULL) {
|
|
bst_node_t *new_node = malloc(sizeof(bst_node_t));
|
|
if (new_node == NULL) {
|
|
return; // Alokácia zlyhala
|
|
}
|
|
new_node->key = key;
|
|
new_node->content = value;
|
|
new_node->left = NULL;
|
|
new_node->right = NULL;
|
|
*tree = new_node;
|
|
return;
|
|
}
|
|
|
|
// Iteratívne hľadáme miesto pre vloženie
|
|
bst_node_t *current = *tree;
|
|
while (true) {
|
|
if (key == current->key) {
|
|
// Kľúč už existuje, aktualizujeme hodnotu
|
|
current->content = value;
|
|
return;
|
|
}
|
|
if (key < current->key) {
|
|
if (current->left == NULL) {
|
|
// Našli sme miesto pre vloženie vľavo
|
|
bst_node_t *new_node = malloc(sizeof(bst_node_t));
|
|
if (new_node == NULL) {
|
|
return; // Alokácia zlyhala
|
|
}
|
|
new_node->key = key;
|
|
new_node->content = value;
|
|
new_node->left = NULL;
|
|
new_node->right = NULL;
|
|
current->left = new_node;
|
|
return;
|
|
}
|
|
current = current->left;
|
|
} else {
|
|
if (current->right == NULL) {
|
|
// Našli sme miesto pre vloženie vpravo
|
|
bst_node_t *new_node = malloc(sizeof(bst_node_t));
|
|
if (new_node == NULL) {
|
|
return; // Alokácia zlyhala
|
|
}
|
|
new_node->key = key;
|
|
new_node->content = value;
|
|
new_node->left = NULL;
|
|
new_node->right = NULL;
|
|
current->right = new_node;
|
|
return;
|
|
}
|
|
current = current->right;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Pomocná funkce která nahradí uzel nejpravějším potomkem.
|
|
*
|
|
* Klíč a hodnota uzlu target budou nahrazené klíčem a hodnotou nejpravějšího
|
|
* uzlu podstromu tree. Nejpravější potomek bude odstraněný. Funkce korektně
|
|
* uvolní všechny alokované zdroje odstraněného uzlu.
|
|
*
|
|
* Funkce předpokládá, že hodnota tree není NULL.
|
|
*
|
|
* Tato pomocná funkce bude využita při implementaci funkce bst_delete.
|
|
*
|
|
* Funkci implementujte iterativně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_replace_by_rightmost(bst_node_t *target, bst_node_t **tree)
|
|
{
|
|
bst_node_t *current = *tree;
|
|
bst_node_t *parent = NULL;
|
|
|
|
// Hľadáme najpravejší uzol
|
|
while (current->right != NULL) {
|
|
parent = current;
|
|
current = current->right;
|
|
}
|
|
|
|
// Nahradíme hodnoty v cieľovom uzle
|
|
target->key = current->key;
|
|
target->content = current->content;
|
|
|
|
// Odstránime najpravejší uzol
|
|
if (parent == NULL) {
|
|
// Špeciálny prípad - current je koreň podstromu
|
|
*tree = current->left;
|
|
} else {
|
|
parent->right = current->left;
|
|
}
|
|
|
|
free(current);
|
|
}
|
|
|
|
/*
|
|
* Odstranění uzlu ze stromu.
|
|
*
|
|
* Pokud uzel se zadaným klíčem neexistuje, funkce nic nedělá.
|
|
* Pokud má odstraněný uzel jeden podstrom, zdědí ho rodič odstraněného uzlu.
|
|
* Pokud má odstraněný uzel oba podstromy, je nahrazený nejpravějším uzlem
|
|
* levého podstromu. Nejpravější uzel nemusí být listem.
|
|
*
|
|
* Funkce korektně uvolní všechny alokované zdroje odstraněného uzlu.
|
|
*
|
|
* Funkci implementujte iterativně pomocí bst_replace_by_rightmost a bez
|
|
* použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_delete(bst_node_t **tree, char key)
|
|
{
|
|
if (*tree == NULL) {
|
|
return; // Prázdny strom
|
|
}
|
|
|
|
bst_node_t *current = *tree;
|
|
bst_node_t *parent = NULL;
|
|
|
|
// Nájdeme uzol na odstránenie
|
|
while (current != NULL && current->key != key) {
|
|
parent = current;
|
|
if (key < current->key) {
|
|
current = current->left;
|
|
} else {
|
|
current = current->right;
|
|
}
|
|
}
|
|
|
|
if (current == NULL) {
|
|
return; // Kľúč nebol nájdený
|
|
}
|
|
|
|
// Prípad 1: Uzol nemá potomkov
|
|
if (current->left == NULL && current->right == NULL) {
|
|
if (parent == NULL) {
|
|
*tree = NULL;
|
|
} else if (parent->left == current) {
|
|
parent->left = NULL;
|
|
} else {
|
|
parent->right = NULL;
|
|
}
|
|
free(current);
|
|
}
|
|
// Prípad 2: Uzol má iba pravého potomka
|
|
else if (current->left == NULL) {
|
|
if (parent == NULL) {
|
|
*tree = current->right;
|
|
} else if (parent->left == current) {
|
|
parent->left = current->right;
|
|
} else {
|
|
parent->right = current->right;
|
|
}
|
|
free(current);
|
|
}
|
|
// Prípad 3: Uzol má iba ľavého potomka
|
|
else if (current->right == NULL) {
|
|
if (parent == NULL) {
|
|
*tree = current->left;
|
|
} else if (parent->left == current) {
|
|
parent->left = current->left;
|
|
} else {
|
|
parent->right = current->left;
|
|
}
|
|
free(current);
|
|
}
|
|
// Prípad 4: Uzol má oboch potomkov
|
|
else {
|
|
bst_replace_by_rightmost(current, &(current->left));
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Zrušení celého stromu.
|
|
*
|
|
* Po zrušení se celý strom bude nacházet ve stejném stavu jako po
|
|
* inicializaci. Funkce korektně uvolní všechny alokované zdroje rušených
|
|
* uzlů.
|
|
*
|
|
* Funkci implementujte iterativně s pomocí zásobníku a bez použití
|
|
* vlastních pomocných funkcí.
|
|
*/
|
|
void bst_dispose(bst_node_t **tree)
|
|
{
|
|
if (*tree == NULL) {
|
|
return;
|
|
}
|
|
|
|
stack_bst_t stack;
|
|
stack_bst_init(&stack);
|
|
stack_bst_push(&stack, *tree);
|
|
|
|
while (!stack_bst_empty(&stack)) {
|
|
bst_node_t *node = stack_bst_pop(&stack);
|
|
|
|
if (node->right != NULL) {
|
|
stack_bst_push(&stack, node->right);
|
|
}
|
|
if (node->left != NULL) {
|
|
stack_bst_push(&stack, node->left);
|
|
}
|
|
|
|
free(node);
|
|
}
|
|
|
|
*tree = NULL;
|
|
}
|
|
|
|
/*
|
|
* Pomocná funkce pro iterativní preorder.
|
|
*
|
|
* Prochází po levé větvi k nejlevějšímu uzlu podstromu.
|
|
* Nad zpracovanými uzly zavolá bst_add_node_to_items a uloží je do zásobníku uzlů.
|
|
*
|
|
* Funkci implementujte iterativně s pomocí zásobníku a bez použití
|
|
* vlastních pomocných funkcí.
|
|
*/
|
|
void bst_leftmost_preorder(bst_node_t *tree, stack_bst_t *to_visit, bst_items_t *items)
|
|
{
|
|
bst_node_t *current = tree;
|
|
while (current != NULL) {
|
|
bst_add_node_to_items(current, items);
|
|
stack_bst_push(to_visit, current);
|
|
current = current->left;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Preorder průchod stromem.
|
|
*
|
|
* Pro aktuálně zpracovávaný uzel zavolejte funkci bst_add_node_to_items.
|
|
*
|
|
* Funkci implementujte iterativně pomocí funkce bst_leftmost_preorder a
|
|
* zásobníku uzlů a bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_preorder(bst_node_t *tree, bst_items_t *items)
|
|
{
|
|
if (tree == NULL) {
|
|
return;
|
|
}
|
|
|
|
stack_bst_t stack;
|
|
stack_bst_init(&stack);
|
|
|
|
bst_leftmost_preorder(tree, &stack, items);
|
|
|
|
while (!stack_bst_empty(&stack)) {
|
|
bst_node_t *node = stack_bst_pop(&stack);
|
|
if (node->right != NULL) {
|
|
bst_leftmost_preorder(node->right, &stack, items);
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Pomocná funkce pro iterativní inorder.
|
|
*
|
|
* Prochází po levé větvi k nejlevějšímu uzlu podstromu a ukládá uzly do
|
|
* zásobníku uzlů.
|
|
*
|
|
* Funkci implementujte iterativně s pomocí zásobníku a bez použití
|
|
* vlastních pomocných funkcí.
|
|
*/
|
|
void bst_leftmost_inorder(bst_node_t *tree, stack_bst_t *to_visit)
|
|
{
|
|
bst_node_t *current = tree;
|
|
while (current != NULL) {
|
|
stack_bst_push(to_visit, current);
|
|
current = current->left;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Inorder průchod stromem.
|
|
*
|
|
* Pro aktuálně zpracovávaný uzel zavolejte funkci bst_add_node_to_items.
|
|
*
|
|
* Funkci implementujte iterativně pomocí funkce bst_leftmost_inorder a
|
|
* zásobníku uzlů a bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_inorder(bst_node_t *tree, bst_items_t *items)
|
|
{
|
|
stack_bst_t stack;
|
|
stack_bst_init(&stack);
|
|
|
|
bst_leftmost_inorder(tree, &stack);
|
|
|
|
while (!stack_bst_empty(&stack)) {
|
|
bst_node_t *node = stack_bst_pop(&stack);
|
|
bst_add_node_to_items(node, items);
|
|
|
|
if (node->right != NULL) {
|
|
bst_leftmost_inorder(node->right, &stack);
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Pomocná funkce pro iterativní postorder.
|
|
*
|
|
* Prochází po levé větvi k nejlevějšímu uzlu podstromu a ukládá uzly do
|
|
* zásobníku uzlů. Do zásobníku bool hodnot ukládá informaci, že uzel
|
|
* byl navštíven poprvé.
|
|
*
|
|
* Funkci implementujte iterativně pomocí zásobníku uzlů a bool hodnot a bez použití
|
|
* vlastních pomocných funkcí.
|
|
*/
|
|
void bst_leftmost_postorder(bst_node_t *tree, stack_bst_t *to_visit,
|
|
stack_bool_t *first_visit)
|
|
{
|
|
bst_node_t *current = tree;
|
|
while (current != NULL) {
|
|
stack_bst_push(to_visit, current);
|
|
stack_bool_push(first_visit, true);
|
|
current = current->left;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Postorder průchod stromem.
|
|
*
|
|
* Pro aktuálně zpracovávaný uzel zavolejte funkci bst_add_node_to_items.
|
|
*
|
|
* Funkci implementujte iterativně pomocí funkce bst_leftmost_postorder a
|
|
* zásobníku uzlů a bool hodnot a bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_postorder(bst_node_t *tree, bst_items_t *items)
|
|
{
|
|
if (tree == NULL) {
|
|
return;
|
|
}
|
|
|
|
stack_bst_t stack;
|
|
stack_bool_t first_visit;
|
|
stack_bst_init(&stack);
|
|
stack_bool_init(&first_visit);
|
|
|
|
bst_leftmost_postorder(tree, &stack, &first_visit);
|
|
|
|
while (!stack_bst_empty(&stack)) {
|
|
bst_node_t *node = stack_bst_top(&stack);
|
|
bool is_first_visit = stack_bool_pop(&first_visit);
|
|
|
|
if (is_first_visit) {
|
|
// Pri prvej návšteve uzla ideme do pravého podstromu
|
|
stack_bool_push(&first_visit, false);
|
|
if (node->right != NULL) {
|
|
bst_leftmost_postorder(node->right, &stack, &first_visit);
|
|
}
|
|
} else {
|
|
// Pri druhej návšteve spracujeme uzol
|
|
bst_add_node_to_items(node, items);
|
|
stack_bst_pop(&stack);
|
|
}
|
|
}
|
|
}
|