Note de curs, clasele 9-10, 7 decembrie 2012

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