Úlohy na procivčování k desáté hodině

Binární vyhledávací strom

Úloha:
Naprogramujte datovou strukturu "binární vyhledávací strom". Umožní ukládat celá čísla typu int, k přístupu k datům použije následující funkce:

int vloz(int x);
Funkce vloží číslo x do stromu. Pokud se vše povede (x tam ještě není), vrátí nenulovou hodnotu, pokud ve stromě již x je, nic s ním neudělá a vrátí nulu jako indikaci chyby.

int vyjmi(int x);
Funkce odebere číslo x ze stromu. Pokud x ve stomě je, odstraní ho a vrátí nenulovou hodnotu jako že se povedlo, pokud x ve stromě není, nic se stromem neudělá a vrátí nulu.

int najdi(int x);
Vrátí nenulové číslo pokud prvek x ve stromě je, nulu pokud ve stromě není.

Optimalizace jako vyvažování a podobné nemusíte dělat, vkládejte a odebírejte prvky tak, jak vám to vychází.

Nápověda:
Jako uzel stromu použijte následující strukturu:

struct Uzel
{
    int cislo;
    Uzel * levy;
    Uzel * pravy;
}

Tu budete dynamicky alokovat podle potřeby, levy ukazuje na levého syna, pravy na pravého, pokud tam nejsou, mají hodnotu NULL.

Hledání ve stromě: Vždy když přijdete do uzlu, podíváte se, zda neobsahuje vámi hledané číslo, pokud ano, našli jste, pokud ne a vaše číslo je menší než to v daném uzlu, jdete doleva, pokud je větší, jdete doprava, když narazíte na NULL tak tam číslo není.

Vkládání: Zkusíte číslo najít. Pokud tam již je, nevkládáte a hlásíte chybu, pokud tam ještě není, narazili jste na NULL a místo tohoto NULL vložíte nově naalokovaný list s vkládanou hodnotou.

Odstraňování: Zkusíte číslo najít, pokud tam není, není co odstraňovat. Jestliže tam je a je v listu, stačí tento list smazat. Pokud má odstraňovaný uzel jednoho syna, tak tohoto syna pověsíte místo něj. A pokud má dva syny, prvek se odstraňovat nebude, ale najde se číslo, které se může dát místo něj a odstraní se uzel s tímto přemístěným číslem. Protože čísla pověšená pod levým synem jsou menší než to odstraňované a čísla vpravo jsou větší, musí se najít největší z levých nebo nejmenší z pravých. Co si vyberete je na vás, pokud si např. vyberete hledat nejmenší z pravých, tak vejdete do pravého syna a pak jdete doleva dokud nenarazíte na NULL. A prvek obsahující toto NULL je hledaný nejmenší z pravých. Toho již odstranit umíme, protože obsahuje jen jednoho syna nebo je to list.