Izpitno vprašanje RAČ2PRA 12000

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MonikaDraškovič.

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 algoritem, s katerim poiščeš dani element v dvojiškem iskalnem drevesu.

Odgovor

Izhajamo iz osnovne definicije iskalnega dvojiškega drevesa. Zato iščemo dani element v levem poddrevesu, če je koren večji, oz. v desnem poddrevesu, če je koren manjši od iskanega elementa.

  1. public static boolean poisci(DvDrevo d, int x) {
  2. //drevo je prazno, v njem ni elementa
  3. if(d.prazno()) return false;
  4. //če podatek ustreza iskanemu, vrnemo true in zaključimo iskanje
  5. if(d.koren() == x) return true;
  6. //podatek v korenu poddrevesa je večji od iskanega elementa
  7. //gremo iskat naprej v levo poddrevo
  8. else if(d.koren() > x) {
  9. return poisci(d.leviSin(), x);
  10. }
  11. //podatek v korenu poddrevesa je manjši od iskanega elementa
  12. //gremo iskat naprej v desno poddrevo
  13. else if(d.koren() < x) {
  14. return poisci(d.desniSin(), x);
  15. }
  16. }
Osebna orodja