Izpitno vprašanje RAČ2PRA 9300

Iz MaFiRaWiki

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

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 ugotoviš višino dvojiškega drevesa. Uporabi le osnovne operacije nad drevesom.

Odgovor

Ta metoda sprejme dvojiško drevo in vrne višino dvojiškega drevesa. V metodi je uporabljena rekurzija.

  1. public static int visina(DvojiskoDrevo d) throws Exception{
  2. //izračunam višino dvojiškega drevesa, ko je drevo prazno
  3. if(d.prazno()){
  4. return 0;
  5. }
  6. //izračunam višino dvojiškega drevesa, ko je drevo sestavljeno
  7. //razdelim drevo na levo in desno drevo
  8. DvojiskoDrevo levoPoddrevo = d.levoDrevo();
  9. DvojiskoDrevo desnoPoddrevo = d.desnoDrevo();
  10.  
  11. int levo = visina(levoPoddrevo);
  12. int desno = visina(desnoPoddrevo);
  13. if(levo > desno){
  14. return 1 + levo;
  15. }
  16. else{
  17. return 1 + desno;
  18. }
  19. }
Osebna orodja