Izpitno vprašanje RAČ2PRA 10200

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vprašanje

Sestavi algoritem, ki s pomočjo osnovnih operacij nad dvojiškim drevesom, ugotovi, če sta dve drevesi identični (imata enako strukturo in hranita enake vrednosti)


Odgovor

Dvojiško drevo je v računalništvu drevesna podatkovna struktura. Dvojiško drevo je lahko prazno ali pa ga sestavlja t.i. vozlišče koren, levo in desno poddrevo. Levo in desno poddrevo sta prav tako dvojiški drevesi. V vsakdanjem življenju lahko z dvojiškim drevesom predstavimo rodoslovne podatke. V teoriji grafov je dvojiško drevo definirano kot povezan neciklični graf, kjer stopnja nobene točke (vozlišča) ne presega števila 3. Število vozlišč drevesa imenujemo teža drevesa, dolžina najdaljše poti od korena do kateregakoli lista pa je globina drevesa.

Ideja

Imamo dve drevesi d in u. Dokler nista prazni, primejamo korena mad seboj, če sta identična. Na enak način primerjamo tudi levo in desno poddrevo. Če se vrednosti ujemajo, metoda vrne true, sicer false.

  1.  
  2. public static boolean identicni(DvDrevo d, DvDrevo u) //imamo dve drevesi d in u
  3. {
  4.  
  5. if(!d.prazno() && !u.prazno() ) //dokler nista prazni ju primerjamo med sabo ce sta identicni(imata enako strukturo
  6. //in hranita enake vrednosti)
  7. {
  8. return d.koren().equals(u.koren()) && identicni(d.leviSin(),u.leviSin())&&identicni(d.desniSin(),u.desniSin());
  9. }
  10. else
  11. return (d.prazno() == u.prazno());
  12.  
  13. } //vrne true oz. false
Osebna orodja