242 lines
7.5 KiB
C
242 lines
7.5 KiB
C
/*
|
|
* Binární vyhledávací strom — rekurzivní varianta
|
|
*
|
|
* S využitím datových typů ze souboru btree.h a připravených koster funkcí
|
|
* implementujte binární vyhledávací strom pomocí rekurze.
|
|
*/
|
|
|
|
#include "../btree.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; // Inicializace prázdného 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 rekurzivně bez použité vlastních pomocných funkcí.
|
|
*/
|
|
bool bst_search(bst_node_t *tree, char key, bst_node_content_t **value)
|
|
{
|
|
// Prázdný strom nebo došli jsme na konec větve
|
|
if (tree == NULL) {
|
|
return false;
|
|
}
|
|
|
|
// Porovnáme klíče
|
|
if (key < tree->key) {
|
|
// Hledáme v levém podstromu
|
|
return bst_search(tree->left, key, value);
|
|
} else if (key > tree->key) {
|
|
// Hledáme v pravém podstromu
|
|
return bst_search(tree->right, key, value);
|
|
} else {
|
|
// Našli jsme hledaný uzel
|
|
*value = &(tree->content);
|
|
return true;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* 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 rekurzivně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_insert(bst_node_t **tree, char key, bst_node_content_t value)
|
|
{
|
|
// Pokud je strom prázdný nebo jsme došli na místo pro vložení
|
|
if (*tree == NULL) {
|
|
// Vytvoříme nový uzel
|
|
bst_node_t *new_node = (bst_node_t *)malloc(sizeof(bst_node_t));
|
|
if (new_node == NULL) {
|
|
return; // Chyba alokace
|
|
}
|
|
|
|
new_node->key = key;
|
|
new_node->content = value;
|
|
new_node->left = NULL;
|
|
new_node->right = NULL;
|
|
|
|
*tree = new_node;
|
|
return;
|
|
}
|
|
|
|
// Porovnáme klíče
|
|
if (key < (*tree)->key) {
|
|
// Vkládáme do levého podstromu
|
|
bst_insert(&(*tree)->left, key, value);
|
|
} else if (key > (*tree)->key) {
|
|
// Vkládáme do pravého podstromu
|
|
bst_insert(&(*tree)->right, key, value);
|
|
} else {
|
|
// Klíč už existuje - nahradíme hodnotu
|
|
(*tree)->content = value;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Pomocná funkce která nahradí uzel nejpravějším potomkem.
|
|
*
|
|
* Klíč a hodnota uzlu target budou nahrazeny 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žitá při implementaci funkce bst_delete.
|
|
*
|
|
* Funkci implementujte rekurzivně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_replace_by_rightmost(bst_node_t *target, bst_node_t **tree)
|
|
{
|
|
if ((*tree)->right == NULL) {
|
|
// Našli jsme nejpravější uzel
|
|
target->key = (*tree)->key;
|
|
target->content = (*tree)->content;
|
|
|
|
// Uložíme si levý podstrom
|
|
bst_node_t *left_subtree = (*tree)->left;
|
|
// Uvolníme nejpravější uzel
|
|
free(*tree);
|
|
// Napojíme levý podstrom
|
|
*tree = left_subtree;
|
|
} else {
|
|
// Pokračujeme v hledání nejpravějšího uzlu
|
|
bst_replace_by_rightmost(target, &(*tree)->right);
|
|
}
|
|
}
|
|
|
|
/*
|
|
* 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 rekurzivně 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; // Strom je prázdný nebo uzel nebyl nalezen
|
|
}
|
|
|
|
if (key < (*tree)->key) {
|
|
// Mažeme v levém podstromu
|
|
bst_delete(&(*tree)->left, key);
|
|
} else if (key > (*tree)->key) {
|
|
// Mažeme v pravém podstromu
|
|
bst_delete(&(*tree)->right, key);
|
|
} else {
|
|
// Našli jsme mazaný uzel
|
|
bst_node_t *node_to_delete = *tree;
|
|
|
|
if (node_to_delete->left == NULL) {
|
|
// Uzel má jen pravý podstrom
|
|
*tree = node_to_delete->right;
|
|
free(node_to_delete);
|
|
} else if (node_to_delete->right == NULL) {
|
|
// Uzel má jen levý podstrom
|
|
*tree = node_to_delete->left;
|
|
free(node_to_delete);
|
|
} else {
|
|
// Uzel má oba podstromy
|
|
// Nahradíme hodnoty nejpravějším uzlem levého podstromu
|
|
bst_replace_by_rightmost(node_to_delete, &node_to_delete->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 rekurzivně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_dispose(bst_node_t **tree)
|
|
{
|
|
if (*tree != NULL) {
|
|
// Rekurzivně zrušíme podstromy
|
|
bst_dispose(&(*tree)->left);
|
|
bst_dispose(&(*tree)->right);
|
|
// Uvolníme aktuální uzel
|
|
free(*tree);
|
|
*tree = NULL;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Preorder průchod stromem.
|
|
*
|
|
* Pro aktuálně zpracovávaný uzel zavolejte funkci bst_add_node_to_items.
|
|
*
|
|
* Funkci implementujte rekurzivně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_preorder(bst_node_t *tree, bst_items_t *items)
|
|
{
|
|
if (tree != NULL) {
|
|
bst_add_node_to_items(tree, items); // Zpracujeme aktuální uzel
|
|
bst_preorder(tree->left, items); // Levý podstrom
|
|
bst_preorder(tree->right, items); // Pravý podstrom
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Inorder průchod stromem.
|
|
*
|
|
* Pro aktuálně zpracovávaný uzel zavolejte funkci bst_add_node_to_items.
|
|
*
|
|
* Funkci implementujte rekurzivně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_inorder(bst_node_t *tree, bst_items_t *items)
|
|
{
|
|
if (tree != NULL) {
|
|
bst_inorder(tree->left, items); // Levý podstrom
|
|
bst_add_node_to_items(tree, items); // Zpracujeme aktuální uzel
|
|
bst_inorder(tree->right, items); // Pravý podstrom
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Postorder průchod stromem.
|
|
*
|
|
* Pro aktuálně zpracovávaný uzel zavolejte funkci bst_add_node_to_items.
|
|
*
|
|
* Funkci implementujte rekurzivně bez použití vlastních pomocných funkcí.
|
|
*/
|
|
void bst_postorder(bst_node_t *tree, bst_items_t *items)
|
|
{
|
|
if (tree != NULL) {
|
|
bst_postorder(tree->left, items); // Levý podstrom
|
|
bst_postorder(tree->right, items); // Pravý podstrom
|
|
bst_add_node_to_items(tree, items); // Zpracujeme aktuální uzel
|
|
}
|
|
}
|