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

From Algopedia
Jump to: navigation, 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