Naloga/Programiranje/Objektno programiranje/Razred Drevo/Rešitev (Java)

Iz MaFiRaWiki

  1. public class Drevo<T> {
  2. private boolean prazen;
  3. private Drevo<T> levi;
  4. private Drevo<T> desni;
  5. private T vsebina;
  6.  
  7. public Drevo() {
  8. prazen = true;
  9. levi = null;
  10. desni = null;
  11. vsebina = null;
  12. }
  13. public Drevo(T v, Drevo<T> l, Drevo<T> d) {
  14. prazen = false;
  15. levi = l;
  16. desni = d;
  17. vsebina = v;
  18. }
  19. //konstruktor, ki naredi drevo s samo korenom
  20. public Drevo(T x) {
  21. prazen = false;
  22. vsebina = x;
  23. levi = new Drevo<T>();
  24. desni = new Drevo<T>();
  25. }
  26. public String toString() {
  27. if(prazen) return "-";
  28. return "{" + vsebina + ", " + levi + ", " + desni + "}";
  29. }
  30. //globina drevesa == st. nivojev
  31. //globina = globina vecjega od poddreves + 1 za koren
  32. public int globina() {
  33. if(prazen) return 0;
  34. return 1 + Math.max(levi.globina(), desni.globina());
  35. }
  36. //metoda, ki vrne število vozlišč v drevesu:
  37. //1 za koren + rekurzivno za izracun vozlisc v levem in desnem poddrevesu, st. vozlisc je vsota teh
  38. public int steviloVozlisc() {
  39. if(prazen) return 0;
  40. return 1 + levi.steviloVozlisc() + desni.steviloVozlisc();
  41. }
  42. //narisi drevo v pregledni obliki:
  43. //risemo drevo, obrnjeno za 90st.; koren je levo na sredini, nato risemo proti desni in narazen
  44. //narisi posebej desno poddrevo, koren, levo poddrevo, da gremo po vrsti od zgoraj dol
  45. //upostevaj, da rabis pravilno stevilo presledkov od levega roba za vsak izpis
  46. public void narisi(String odmik) { //odmik je st. odmikov, je niz
  47. if(prazen) return;
  48. desni.narisi(odmik + " ");
  49. System.out.println(odmik + vsebina); //napises tudi odmik, ker je to rekuzivno in to uporabis tudi pri izpisu levi in desni
  50. levi.narisi(odmik + " ");
  51. }
  52.  
  53. //get metode:
  54. public boolean prazen() {
  55. return prazen;
  56. }
  57. //vrne levo poddrevo:
  58. public Drevo<T> levo() {
  59. return levi;
  60. }
  61. //vrne desno poddrevo:
  62. public Drevo<T> desno() {
  63. return desni;
  64. }
  65. public T vsebina() {
  66. return vsebina;
  67. }
  68. //set metode:
  69. public void nastavi_levi(Drevo<T> l) {
  70. if(prazen) {
  71. prazen = false;
  72. levi = new Drevo<T>();
  73. vsebina = null;
  74. }
  75. levi = l;
  76. }
  77. public void nastavi_desni(Drevo<T> d) {
  78. if(prazen) {
  79. prazen = false;
  80. desni = new Drevo<T>();
  81. vsebina = null;
  82. }
  83. desni = d;
  84. }
  85. public void nastavi_vsebino(T v) {
  86. if(prazen) {
  87. prazen = false;
  88. levi = new Drevo<T>();
  89. desni = new Drevo<T>();
  90. }
  91. vsebina = v;
  92. }
  93. //pregled drevesa:
  94. //levo, koren, desno:
  95. public void izpisi() {
  96. if(!prazen) {
  97. levi.izpisi();
  98. System.out.println(vsebina);
  99. desni.izpisi();
  100. }
  101. }
  102. }
Osebna orodja