Izpitno vprašanje RAČ2PRA 9400

Iz MaFiRaWiki

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

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

Sestavi algoritem, s katerim prešteješ število listov v dvojiškem drevesu. Algoritem naj uporablja le osnovne operacije nad dvojiškim drevesom.

Odgovor

  1. public static int listi(DvojiskoDrevo d){
  2. //če je dvojiško drevo prazno vrnemo 0
  3. if(d.prazno()){
  4. return 0;
  5. }
  6. //če ni prazno ločimo drevo na levo in desno poddrevo
  7. DvojiskoDrevo levoPod = d.levoPoddrevo();
  8. DvojiskoDrevo desnoPod = d.desnoPoddrevo();
  9. //če sta oba poddrevesa prazna vrnemo 1, ker nam ostane samo koren
  10. if(levoPod.prazno() && desnoPod.prazno()){
  11. return 1;
  12. }
  13. //v nasprotnem primeru pa preštejemo liste levega in desnega poddrevesa
  14. return listi(levoPod) + listi(desnoPod);
  15. }
Osebna orodja