Izpitno vprašanje RAČ2PRA 9100

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka LidijaSterk.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Opiši preglede dvojiškega drevesa. Pokaži jih tudi na primeru.

Odgovor

Poznamo več načinov kako sistematično pregledati vsa vozlišča v dvojiškem drevesu.

Nekaj načinov:

  • Po nivojih
  • Najprej liste, potem očete listov,...
  • Po nivojih z desne
  • "Grafovsko"
    • Pregled v globino
      • S pomočjo sklada
    • Pregled v širino
      • S pomočjo vrste

Najpomembnejši pregledi:

  • Premi vrstni red: obisk korena(očeta), premi pregled(levo poddrevo), premi pregled(desno poddrevo)
  • Vmesni vrstni red: vmesni pregled(levo poddrevo), obisk korena, vmesni pregled(desno poddrevo)
  • Obratni vrstni red: obratni pregled(levo poddrevo), obratni pregled(desno poddrevo), obisk korena


Zgled za vse tri primere:

Slika:PregledDD.jpg

  • PREMI: 1,2,4,7,8,3,5,9,6,10
  • VMESNI: 7,4,8,2,1,5,9,3,10,6
  • OBRATNI: 7,8,4,2,9,5,10,6,3,1
Osebna orodja