Dvojiško drevo

Navodila

DvDrevo.java

public class DvDrevo { // konstruktorji public DvDrevo(); // pripravi // metode public boolean prazno(); // prazno public static DvDrevo sestavi(DvDrevo, int, DvDrevo); // sestavi public int koren(); // vrni vrednost iz korena, napaka ce drevo prazno public DvDrevo leviSin()(); // levo poddrevo public DvDrevo desniSin()(); // desno poddrevo } // class

Drevo torej sestaviš tako, da za vsak list pripraviš dve prazni drevesi, ki jih potem "sestaviš" skupaj tako, da imata v korenu vrednost tega lista.

Če potrebuješ več informacij o dvojiških drevesih vprašaj asistenta, si oglej predavanja ali pa poglej na internetno stran University of Saskatchewan.

Naloge

1. Napiši metodo, ki sestavi dvojiško drevo, ki je podano z zapisom (1(3()())(2()()). Za pomen zapisa si oglej prosojnice s predavanj!
2. Seveda moraš preveriti, če si pri prejšnji nalogi sestavi(a) pravilno drevo. To storiš tako, da narediš premi pregled po drevesu. Začneš s korenom, izpišeš njegovo vrednost, potem pa na enak način o njegovem levem in nato še o desnem poddrevesu. Za zgornje drevo naj izpis izgleda takole:
   
   KOREN: 1
   LEVO PODDREVO:
   KOREN: 3
   LEVO PODDREVO: -
   DESNO PODDREVO: -
   DESNO PODDREVO:
   KOREN: 2
   LEVO PODDREVO: -
   DESNO PODDREVO: -
   
   Sestaviti bo torej potrebno metodo public static void izpis(DvDrevo drevo), ki bo izpisala podatke o dvojiškem drevesu.
3. Sestavi program, ki prebira števila, dokler uporabnik ne vnese števila 0, in iz njih zgradi levo izrojeno levo drevo. Izpiši ga!
4. Sestavi program, ki prebira števila, dokler uporabnik ne vnese števila 0, in iz njih zgradi desno izrojeno drevo. Izpiši ga!
5. Recimo, da želimo imeti drevo, ki ima za koren vrednost 0. Levo poddrevo naj bo levo izrojeno drevo iz samih lihih, desno poddrevo pa desno izrojeno drevo iz samih sodih števil. Ali ga znaš sestaviti? Kot prej številke dobivaš od uporabnika, vnos pa zaključi s številko 0. Drevo tudi izpiši.
6. Verjetno si že opazil, da metoda izpis drevesa ne izpiše najlepše. Popravi jo tako, da izpis za poddrevo zamakneš za 3 presledke v desno. Zapis za drevo iz druge naloge bi tako izgledal:

   KOREN: 1
   LEVO PODDREVO:
      KOREN: 3
      LEVO PODDREVO: -
      DESNO PODDREVO: -
   DESNO PODDREVO:
      KOREN: 2
      LEVO PODDREVO: -
      DESNO PODDREVO: -
   			

   Namig: najlažje boš zastavljeno nalogo rešil(a) tako, da metodi izpis dodaš dodaten parameter, ki pomeni globino drevesa, ki ga izpisujemo (ali pa število presledkov v izpisu).
7. Metodo izpis popravi tako, da namesto premega narediš vmesni pregled.
8. 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.
9. Sestavi metodo, ki podatke v drevesu preloži v sklad tako, da so podatki v skladu razvrščeni glede na obratni pregled dv. drevesa.

10. Dobili smo naslednjo metodo:

      public static int izberiIzDrevesa(DvDrevo tt, int kateri) {

        if (tt.prazno()) return Integer.MIN_VALUE;

        if (kateri == 0) return tt.koren();

        if (kateri % 2 == 0) return izberiIzDrevesa(tt.leviSin(), kateri/2);

        else                 return izberiIzDrevesa(tt.desniSin(), kateri/2);

      }

    ki naj bi omogočala izbor poljubnega elementa iz dvojiškega drevesa. Ali lahko pridemo do vseh elementov naslednjega drevesa? Kakšna naj bo vrednost kateri za dostop do posameznega elementa.