Note de curs, clasele 9-10, 7 decembrie 2012
From Algopedia
Jump to navigationJump to search
Arbori parțiali minimi
- aplicație: generarea unui labirint
Arbori - generalități
- definiție (graf conex aciclic)
- definiții echivalente
- cale unică între oricare două noduri
- graf aciclic maximal
- graf conex minimal
- demonstrație la câteva dintre aceste echivalențe
- tipuri: binar, ternar, binar strict, general, complet
- reprezentări
- vector de tați
- pointeri la fii (pentru cazul binar)
- pointeri la listă de fii (pentru cazul general)
- pointeri la fiu + frate
- heap (arbore binar strict)
- cod Prüfer (mai mult ca problemă)
- tipuri de parcurgeri: preordine, postordine, inordine (cazul binar)
Notație poloneză
- pe scurt, definiția notației prefixate (poloneze), postfixate, infixate
- exemplificarea pe arborele unei expresii
- notația postfixată nu necesită paranteze
- parser de expresie aritmetică, cele trei funcții care se apelează una pe alta