Úlohy na procvičení
Průměrná výška stromu
Pro binární strom navrhněte efektivní algoritmus, který zjistí průměrnou výšku stromu definovanou jako součet_délek_všech_cest_z_kořene_do_listu / počet_listů.
Můžete použít šablonu (pro ukázkový strom v šabloně byste měli dostat výsledek 3.2).
Zajímá nás jen tvar stromu, ne hodnoty ve vrcholech. Strom v šabloně tvarem odpovídá příkladu na obrázku níže (jeho vrcholy jsou pro snazší ladění očíslované po hladinách odshora dolů).
Cvičení na binární vyhledávací stromy
Pro binární vyhledávací strom implementujte následující operace (jako metody třídy BinarySearchTree ze cvičení):
- Najděte nejmenší hodnotu uloženou v binárním stromě.
- Určete výšku binárního stromu (délku nejdelší větvě z kořene do listu).
- Určete počet vrcholů ve stromě.
- Smažte prvek se zadanou hodnotou ze stromu.
Můžete se zamyslet nad různými způsoby řešení takových úloh (do hloubky nebo do šířky, pomocí rekurze nebo bez rekurze apod.). Nicméně doporučuji si nejdřív rozmyslet řešení teoreticky (zkusit si ho nakreslit na papír) a pak teprve začít implementovat.