Izpitno vprašanje RAČ2PRA 8900

Iz MaFiRaWiki

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

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 metodo DvDrevo normiraj(DvDrevo d), ki s pomočjo osnovnih operacij nad dvojiškim drevesom naredi kopijo danega dvojiškega drevesa s pozitivnimi podatki, katerega vrednosti v vozliščih so celoštevilski kvocienti med vrednostmi v vozliščih originalnega dvojiškega drevesa in največjim elementom v dvojiškem drevesu.


Odgovor

  1.  
  2. public static DvDrevo normiraj(DvDrevo d) {
  3. // če je drevo prazno, vrni prazno dvojisko drevo
  4. if(d.prazno()) {
  5. return new DvDrevo();
  6. }
  7. // če drevo ni prazno, določimo najvecji element
  8. double naj = najvecji(d);
  9. // ter rekurzivno kličemo metodo deli
  10. return deli(d, naj);
  11. }
  12.  
  13. // izračunamo največji element v vozlišču
  14. private static double najvecji(DvDrevo d) {
  15. // če je drevo prazno, vrne 0
  16. if(d.prazno()) {
  17. return 0;
  18. }
  19. // če drevo ni prazno, določimo največji element
  20. // maxL določi največji element v levem poddrevesu
  21. double maxL = najvecji(d.levoPoddrevo());
  22. // maxD določi največji element v desnem poddrevesu
  23. double maxD = najvecji(d.desnoPoddrevo());
  24. // koren drevesa
  25. double koren = d.vrni();
  26. // vrne največji element med levim poddrevesom, desnim poddrevesom
  27. // ter korenom
  28. return Math.max(Math.max(maxL, maxD), koren);
  29. }
  30.  
  31. // delimo vrednost vozlišča v originalnem dvojiškem drevesu
  32. // z največjim elementom v dvojiškem drevesu
  33. private static DvDrevo deli(DvDrevo d, double najv) {
  34. // če je drevo prazno, nam vrne novo dvojiško drevo
  35. if(d.prazno()) {
  36. return new DvDrevo();
  37. }
  38. // če drevo ni prazno:
  39. // definiramo koren, levo poddrevo in desno poddrevo
  40. double koren = d.vrni();
  41. DvDrevo ld = d.levoPoddrevo();
  42. DvDrevo dd = d.desnoPoddrevo();
  43. // delimo neničelni element najv z levim poddrevesom
  44. DvDrevo dLevo = deli(ld, najv);
  45. // delimo neničelni element najv z desnim poddrevesom
  46. DvDrevo dDesno = deli(dd, najv);
  47. // vrnemo sestavljeno dvojiško drevo
  48. return DvDrevo.sestavi(dLevo, koren/najv, dDesno);
  49. }
Osebna orodja