Cvičení 8 - Binární vyhledávací strom

• Prostudujte si ukázkovou implementaci binárního vyhledávacího stromu, kde klíče jsou celočíselné hodnoty typu int.
• Podívejte se zde na celkem pěkný výklad k binárnímu vyhledávacímu stromu.
• Implementujte následující úlohy:

Rozšíření implementace binárního stromu

• Implementujte privátní metody MinKey a MaxKey, které pro daný strom vráti nejmenší, resp. nejvetší klíč
• Předpokládejte, že strom není prázdný, tedy výše uvedené funkce vždy vrátí nějakou hodnotu.
• Implementujte privátní metodu ToVector, která pro daný strom vrátí vektor všech klíčú ve stromu ve vzestupném pořadí.

Převod pole na uspořádanou množinu

• Vygenerujte pole (vektor) celých čísel v intervalu <0, 100> o délce 10 000 prvků
• V poli se budou zajisté vyskytovat duplicitní prvky
• Cílem je toto neuspořádané pole čísel, ve kterém se vyskytují duplicitní prvky, převést na (uspořádanou) množinu a vypsat prvky množiny od nejmenšího po největší
• Procházejte pole sekvenčně a hodnoty vkládejte do BST
• Až budete mít pole celé zpracované, projděte BST pomocí In-Order přístupu a hodnoty vypište

Počítání jmen v textovém souboru

• Cílem bude vytvořit implementaci stromu, která umožní přečíst sekvenci jmen ze souboru a následně je vypsat v pořadí dle abecedy včetně počtu jejich výskytů.
• V souboru se bude nacházet předem nespecifikovaný počet řádků. Na každém řádku bude umístěno právě jedno jméno.
• Vytvořte alternativní implementaci binárního vyhledávacího stromu BST_string, kde bude v každém uzlu uložen klíč typu string reprezentující jméno a číselná proměnná count reprezentující počet jeho výskytů.
• Vkládání do binárního vyhledávacího stromu standardně neprovádí žádnou akci pokud klíč ve stromu již existuje.
• Bude tedy potřeba vkládání upravit upravit tak, že při vložení duplicitního klíče (jména) se bude proměnná count u příslušného jména inkrementovat
• Pokud se slovo ve stromu zatím nebude nacházet, standardně se do stromu přídá.
• Implementace vyhledávací funkce a funkcí pro zjištění minimálního nebo maximálního klíče nebudou potřeba.
• Vytvořte funkci LoadFromFile, která načte jména ze souboru, jehož cesta byla zadaná jako parametr, a vloží je do stromu.
• Následně vytvořte modifikaci funkce InOrder, která jména vypíše v abecedním pořadí včetně počtu jejich výskytů ve vstupním souboru.
• Otestujte váš program na poskytnutých testovacích souborech níže.