Binárne a lexikografické stromy

Zhrnutie prednášky

Prednáška uvádza tému stromov ako acyklických súvislých grafov a zameriava sa na binárne a lexikografické stromy. Na príklade prekladu morzeovky do latinky ukazuje binárny strom, v ktorom uzol nesie znak a dva smerníky (vľavo pre bodku, vpravo pre čiarku), pričom koreň obsahuje medzeru. Vysvetľuje terminológiu (koreň, listy, hrany ako smerníky) a navrhuje funkcie inicializácie, vkladania uzla a vyhľadávania, zatiaľ nerekurzívne. Podrobne rozoberá inicializáciu koreňa pomocou alokácie a začiatok vkladania, pri ktorom sa po reťazci morzovho kódu pohybuje pomocný smerník stromom. Rekurzívne riešenie a odstránenie stromu sa odkladajú na neskôr.

• - Strom je aciklický súvislý graf; má koreň, hrany a listy.
• - V binárnom strome vchádza do každého uzla (okrem koreňa) jedna hrana a vychádzajú najviac dve.
• - Uzol obsahuje znak a smerníky vľavo a vpravo; strom je reprezentovaný smerníkom na koreň.
• - V morzeovke bodka vedie doľava, čiarka doprava a koreň obsahuje medzeru.
• - Inicializácia alokuje koreň so znakom medzery a nulovými smerníkmi.
• - Vkladanie prechádza reťazec morzovho kódu pomocným smerníkom a vytvára chýbajúce uzly.
• - Vyhľadávanie podľa morzovho kódu vráti písmeno; nerekurzívny postup, rekurzívny nasleduje neskôr.

Zhrnutie pripravené s pomocou AI z prepisu videa.