zpět
Cvičení 8 - Binární vyhledávací strom
Zadání cvičení:
- 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.
Šablona:
BST.h BST.cpp cviceni8.cpp
Ukázkový vstupní soubor:
jmena.txt
Řešení:
BST.h BST.cpp cviceni8.cpp
BST_string.h BST_string.cpp