Ú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.