Bu yazımda veri modellerinden birisi olan ikili arama ağacı (binary search tree) ile ilgili örnek bir kod paylaşacağım. Bu kod plaka numarası, adı, enlem ve boylam bilgisi girilen şehirleri ikili arama ağacı modeline göre saklamaktadır. Yani ilk girilen şehir ikili arama ağacının kökü olarak kaydedilecek; ardından kaydedilen her şehir, plaka numarasına göre kökteki ilk şehirden küçükse ağacın soluna, büyükse ağacında sağ tarafında kaydedilecektir.
Bu sayede aranan şehir daha kolay bir şekilde bulunacaktır. İkili arama ağacı ile ilgili fazla bilgi vermeyecem internette bu konuda fazlasıyla bilgi var. Kodları paylaşma kısmına geçiyorum...
Önce düğüm yapımızı oluşturan Sehir.java dosyasının içeriğine bakalım.
public class Sehir {
int plaka, balance;
String il, enlem, boylam;
Sehir sol, sag;
public Sehir (int plaka, String il, String enlem, String boylam){
this.plaka = plaka;
this.balance = 0;
this.il = il;
this.enlem = enlem;
this.boylam = boylam;
this.sol = null;
this.sag = null;
}
}
Düğümleri içerisinde barındıracak olan İkili Arama Ağaç modelimizi oluşturan Agac.java dosyasının içeriği aşağıdaki gibidir. import java.awt.Desktop;
import java.io.IOException;
import java.net.URI;
import java.net.URISyntaxException;
import java.util.logging.Level;
import java.util.logging.Logger;
public class Agac {
Sehir kok;
int dgm_say, indis;
int [] sehirler;
public Agac(){
kok = null;
dgm_say = 0;
indis = 0;
}
public void ekle(int plaka, String il, String enlem, String boylam){
Sehir tmp = null, k = kok;
while (k != null) {
tmp = k;
if (plaka == k.plaka) return;
else if (plaka < k.plaka) {
k = k.sol;
}
else {
k = k.sag;
}
}
Sehir Eleman = new Sehir(plaka, il, enlem, boylam);
if (kok == null) {
kok = Eleman;
dgm_say++;
}
else if (Eleman.plaka < tmp.plaka) {
tmp.sol = Eleman;
dgm_say++;
}
else {
tmp.sag = Eleman;
dgm_say++;
}
}
public Sehir bul(int plaka){
Sehir tmp = kok;
while (tmp != null){
if (plaka == tmp.plaka) return tmp;
else if (plaka < tmp.plaka) {
tmp = tmp.sol;
}
else tmp = tmp.sag;
}
return null;
}
public Sehir e_kucuk_bul (Sehir dugum) {
Sehir tut = dugum;
while (tut.sol != null) {
tut = tut.sol;
}
return tut;
}
public Sehir sil (Sehir kok, int plk) {
if (kok == null) return kok;
if (plk < kok.plaka) kok.sol = sil(kok.sol, plk);
else if (plk > kok.plaka) kok.sag = sil(kok.sag, plk);
else {
Sehir tmp = null;
if (kok.sol == null) {
tmp = kok.sag;
kok = null;
dgm_say--;
return tmp;
}
else if (kok.sag == null) {
tmp = kok.sol;
kok = null;
dgm_say--;
return tmp;
}
tmp = e_kucuk_bul(kok.sag);
kok.plaka = tmp.plaka;
kok.il = tmp.il;
kok.enlem = tmp.enlem;
kok.boylam = tmp.boylam;
kok.sag = sil (kok.sag, tmp.plaka);
}
return kok;
}
public void guncelle(int plaka, int y_plaka, String il, String enlem, String boylam){
Sehir Aranan = bul(plaka);
if (Aranan != null){
if (plaka == y_plaka){
Aranan.il = il;
Aranan.enlem = enlem;
Aranan.boylam = boylam;
System.out.println("Şehir bilgileri başarıyla güncellendi.");
}
else {
ekle(y_plaka, il, enlem, boylam);
System.out.println("Şehir bilgileri başarıyla güncellendi.");
}
}
else System.out.println("Aradığınız şehir sistemde yok...!");
}
public void kss (Sehir k_dgm) {
if (k_dgm != null) {
System.out.println(k_dgm.plaka + "\t" + k_dgm.il + "\t\t" + k_dgm.enlem + "\t" + k_dgm.boylam);
kss(k_dgm.sol);
kss(k_dgm.sag);
}
}
public void sks (Sehir k_dgm) {
if (k_dgm != null) {
sks(k_dgm.sol);
System.out.println(k_dgm.plaka + "\t" + k_dgm.il + "\t\t" + k_dgm.enlem + "\t" + k_dgm.boylam);
sks(k_dgm.sag);
}
}
public void ssk (Sehir k_dgm) {
if (k_dgm != null) {
ssk(k_dgm.sol);
ssk(k_dgm.sag);
System.out.println(k_dgm.plaka + "\t" + k_dgm.il + "\t\t" + k_dgm.enlem + "\t" + k_dgm.boylam);
}
}
public void sks_2 (Sehir k_dgm) {
if (k_dgm != null) {
sks_2(k_dgm.sol);
sehirler[indis] = k_dgm.plaka;
indis++;
sks_2(k_dgm.sag);
}
}
public void ikili_mi(){
sehirler = new int [dgm_say];
sks_2(kok);
int kontrol = 0;
for (int i = 0; i < sehirler.length-1; i++){
if (sehirler[i] >= sehirler[i+1]) kontrol ++;
}
if (kontrol == 0) System.out.println("Ağaç İkili");
}
public void dengeli_mi(Sehir k_dgm){
denge_hesapla(k_dgm);
if(k_dgm.balance == -2 || k_dgm.balance == 2) {
System.out.println("Ağaç Dengesiz");
}
else System.out.println("Ağaç Dengeli");
}
public void denge_hesapla(Sehir k_dgm) {
k_dgm.balance = yukseklik(k_dgm.sag)-yukseklik(k_dgm.sol);
}
public int yukseklik(Sehir k_dgm) {
if(k_dgm==null){
return -1;
}
if(k_dgm.sol==null && k_dgm.sag==null) {
return 0;
}
else if(k_dgm.sol==null) {
return 1+yukseklik(k_dgm.sag);
}
else if(k_dgm.sag==null) {
return 1+yukseklik(k_dgm.sol);
}
else {
return 1+maximum(yukseklik(k_dgm.sol),yukseklik(k_dgm.sag));
}
}
public int maximum(int a, int b) {
if(a>=b) {
return a;
}
else {
return b;
}
}
void gps(Sehir shr, String zoom) throws URISyntaxException{
String site = "https://www.google.com.tr/maps/@";
String baglanti = site + shr.enlem + "," + shr.boylam + "," + zoom + "z";
Desktop d=Desktop.getDesktop();
try {
d.browse(new URI(baglanti));
} catch (IOException ex) {
Logger.getLogger(Agac.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
Son olarak test edelim Ana_Program.java dosya içeriği
public class Ana_Program {
public static void main(String[] args) throws Exception{
Agac A = new Agac();
A.ekle(44, "Sehir 1", "23.165464", "45.65463");
A.ekle(23, "Sehir 2", "38.675093", "39.218749");
A.ekle(61, "Sehir 3", "23.165464", "45.65463");
A.ekle(30, "Sehir 4", "23.165464", "45.65463");
A.ekle(10, "Sehir 5", "23.165464", "45.65463");
A.ekle(80, "Sehir 6", "23.165464", "45.65463");
A.ekle(52, "Sehir 7", "23.165464", "45.65463");
A.ekle(63, "Sehir 8", "23.165464", "45.65463");
A.ekle(67, "Sehir 9", "23.165464", "45.65463");
A.ekle(62, "Sehir 10", "23.165464", "45.65463");
Sehir Aranan = A.bul(61);
if (Aranan != null) {
System.out.println("PLAKA\tŞEHİR\t\tENLEM\t\tBOYLAM");
System.out.println(Aranan.plaka + "\t" + Aranan.il + "\t\t" + Aranan.enlem + "\t" + Aranan.boylam);
}
else System.out.println("ŞEHİR BULUNAMADI");
A.ssk(A.kok);
System.out.println("\n");
A.sil(A.kok, 63);
A.sil(A.kok, 67);
A.sil(A.kok, 62);
System.out.println("Sistemde kayıtlı şehir sayısı :" + A.dgm_say);
A.ikili_mi();
A.dengeli_mi(A.kok);
A.kss(A.kok);
System.out.println("\n");
A.sks(A.kok);
System.out.println("\n");
A.ssk(A.kok);
System.out.println("\n");
A.gps(A.bul(23), "9");
}
}
Ekran Çıktısı PLAKA ŞEHİR ENLEM BOYLAM
61 Sehir 3 23.165464 45.65463
10 Sehir 5 23.165464 45.65463
30 Sehir 4 23.165464 45.65463
23 Sehir 2 38.675093 39.218749
52 Sehir 7 23.165464 45.65463
62 Sehir 10 23.165464 45.65463
67 Sehir 9 23.165464 45.65463
63 Sehir 8 23.165464 45.65463
80 Sehir 6 23.165464 45.65463
61 Sehir 3 23.165464 45.65463
44 Sehir 1 23.165464 45.65463
Sistemde kayıtlı şehir sayısı :7
Ağaç İkili
Ağaç Dengeli
44 Sehir 1 23.165464 45.65463
23 Sehir 2 38.675093 39.218749
10 Sehir 5 23.165464 45.65463
30 Sehir 4 23.165464 45.65463
61 Sehir 3 23.165464 45.65463
52 Sehir 7 23.165464 45.65463
80 Sehir 6 23.165464 45.65463
10 Sehir 5 23.165464 45.65463
23 Sehir 2 38.675093 39.218749
30 Sehir 4 23.165464 45.65463
44 Sehir 1 23.165464 45.65463
52 Sehir 7 23.165464 45.65463
61 Sehir 3 23.165464 45.65463
80 Sehir 6 23.165464 45.65463
10 Sehir 5 23.165464 45.65463
30 Sehir 4 23.165464 45.65463
23 Sehir 2 38.675093 39.218749
52 Sehir 7 23.165464 45.65463
80 Sehir 6 23.165464 45.65463
61 Sehir 3 23.165464 45.65463
44 Sehir 1 23.165464 45.65463
Herkese iyi çalışmalar dilerim... :D
|