Izpitno vprašanje RAČ2PRA 10100

Iz MaFiRaWiki

Vprašanje

V dvojiškem drevesu hranimo cela števila. Naj bo »vsota poti do lista« enaka vsoti elementov, ki jih prehodimo od korena do lista. Sestavi algoritem, ki ugotovi, ali v danem drevesu obstaja list, ki ima vsoto poti enako vrednosti v tem listu.

Odgovor

Če dvojiško drevo ni prazno, se list z iskano lastnostjo nahaja bodisi v levem, bodisi v desnem ali obeh poddrevesih. Sprehajamo se po drevesu in seštevamo elemente na poti. Ko naletimo na list, preverimo, ali se podatek v listu ujema z »vsoto poti«. Če se, takoj zaključimo z iskanjem, saj je dovolj, da najdemo enega. Če list ni ustrezen, začnemo iskanje po drugi poti (če še kakšna obstaja).

Algoritem bo rekurziven, saj se tako najlažje gibljemo po rekurzivno definirani podatkovni strukturi. Potrebujemo sledeče osnovne operacije nad dvojiškim drevesom:

  • metodo, ki vrne, ali je drevo prazno - naj se imenuje prazno()
  • metodo, ki vrne podatek v korenu - naj se imenuje podatek()
  • metodo, ki vrne levo poddrevo - naj se imenuje levoDrevo()
  • metodo, ki vrne desno poddrevo - naj se imenuje desnoDrevo()

  1. //Krovna metoda - to kliče uporabnik
  2. public static boolean vsotaPotiJeVListu(DvojiskoDrevo<Integer> d)throws Exception{
  3. //Če je drevo prazno, raje vržemo izjemo, kot pa vrnemo false:
  4. if(d.prazno()) throw new Exception("Nimam kaj preverjati, saj je drevo prazno!");
  5. //Sicer, če drevo ni prazno:
  6. //ker nočemo, da tudi za vsak list vrže gornjo napako
  7. //(levo in desno poddrevo lista sta prazni drevesi!),
  8. //spravimo glavni del metode v privatno (pomožno) metodo, ki jo kličemo tu;
  9. //pri prvem klicu te rekurzivne metode je vsota poti kar vrednost v korenu:
  10. return privatnaVsotaPotiJeVListu(d, d.podatek());
  11. }
  12.  
  13. //Glavni del opravi rekurzivna pomožna metoda, ki ima še en parameter,
  14. //da ob vsakem klicu vemo, kolikšna je bila vsota poti do tedaj
  15. private static boolean privatnaVsotaPotiJeVListu(DvojiskoDrevo<Integer> d, int vsotaPoti)throws Exception{
  16. //če drevo prazno (klicali smo metodo na poddrevesu lista):
  17. if(d.prazno()) return false;
  18. //sicer, če list:
  19. if(d.levoDrevo().prazno() && d.desnoDrevo().prazno()){
  20. //če podatek ne ustreza:
  21. if(vsotaPoti != d.podatek()){
  22. vsotaPoti = 0; //začnemo seštevati znova
  23. return false;
  24. }
  25. //sicer podatek ustreza
  26. return true; //zaključimo iskanje
  27. }
  28. //sicer:
  29. //iskani list lahko najdemo v levem ali desnem poddrevesu ali obeh
  30. return privatnaVsotaPotiJeVListu(d.levoDrevo(),vsotaPoti+d.podatek()) ||
  31. privatnaVsotaPotiJeVListu(d.desnoDrevo(),vsotaPoti+d.podatek());
  32. }

Glej tudi

Osebna orodja