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

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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