Izpitno vprašanje RAČ2PRA 9600

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

V dvojiškem drevesu hranimo cela števila. Sestavi algoritem, s katerim izračuna povprečno vrednost elementov v drevesu.

Odgovor

Da izračunamo povprečno vrednost elementov v dvojiškem drevesu potrebujemo dve pomožni metodi:

- metoda, ki v dvojiškem drevesu prešteje vsa vozlišča

- metoda, ki izračuna vsoto elementov v dvojiškem drevesu.

Povprečna vrednost elementov je pa, da vsoto elementov delimo z število vozlišč.

  1. //PREŠTEJEMO VOZLIŠČA V DVOJIŠKEM DREVESU
  2. public static int steviloVozlisc(DvojiskoDrevo<Integer> d) throws Exception{
  3. if(d.prazno()){
  4. return 0;
  5. }
  6. DvojiskoDrevo<Integer> levoPoddrevo = d.levoDrevo();
  7. DvojiskoDrevo<Integer> desnoPoddrevo = d.desnoDrevo();
  8. return 1 + steviloVozlisc(levoPoddrevo) + steviloVozlisc(desnoPoddrevo);
  9. }
  10. //IZRAČUNAMO VSOTO ELEMENTOV V DVOJIŠKEM DREVESU
  11. public static int vsota(DvojiskoDrevo <Integer> d) throws Exception{
  12. if(d.prazno()){
  13. return 0;
  14. }
  15. DvojiskoDrevo<Integer> levoPoddrevo = d.levoDrevo();
  16. DvojiskoDrevo<Integer> desnoPoddrevo = d.desnoDrevo();
  17. int koren = d.podatek();
  18. return koren + vsota(levoPoddrevo) + vsota(desnoPoddrevo);
  19. }
  20. //IZRAČUNAMO POVPREČNO VREDNOST ELEMENTOV V DVOJIŠKEM DREVESU
  21. public static double povprečje(DvojiskoDrevo d) throws Exception{
  22. if(d.prazno()){
  23. throw new Exception("V praznem dvojiskem drevesu ne moreŠ izračunati povprečja");
  24. }
  25. else{
  26. return (double)vsota(d) / steviloVozlisc(d);
  27. }
  28. }
Osebna orodja