Izpitno vprašanje RAČ2PRA 9900

Iz MaFiRaWiki

Vprašanje

Z osnovnimi operacijami nad dvojiškim drevesom sestavi zrcalno kopijo dvojiškega drevesa.

Odgovor

Izhajamo iz osnovne definicije dvojiškega drevesa. Zato poveamo, kakpšna je zrcalna kopija praznega drevesa (to je prazno drevo) in kakšna je zrcalna kopija sestavljenega drevesa (gledj komentarje v metodi).

  1. public static DvDrevo zrcali(DvDrevo d){
  2. // če je drevo prazno, vrne prazno dvojiško drevo
  3. if(d.prazno()){
  4. return new Drevo();
  5. }
  6. // če ni prazno ločimo drevo na levo in desno poddrevo
  7. DvDrevo lD = d.levoPoddrevo();
  8. DvDrevo dD = d.desnoPoddrevo();
  9. // rekurzivno kličemo metodo zrcali
  10. // zrcalni kopiji levega in desnega poddrevesa
  11. DvDrevo zrcaliLevoD = zrcali(lD);
  12. DvDrevo zrcaliDesnoD = zrcali(dD);
  13. // vrnemo sestavljeno dvojiško drevo
  14. //desno je zrcalna kopija levega poddrevesa in levo zrcalna kopija desnega poddrevesa
  15. return sestavi(zrcaliDesnoD,d.koren(),zrcaliLevoD);
  16. }
Osebna orodja