Selçuk Sinan KIRAT | Kişisel Web Sitesi

Ana Sayfa

Hakkımda

Projeler

Yazılar

Öğrenci Girişi

İletişim

Veri Yapıları İkili Arama Ağacı / Binary Search Tree | 2019-12-08 tarihinde oluşturuldu.

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.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sskirat
 */
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;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sskirat
 */

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) { // Düğümün alt ağacındaki en küçük düğüm
        Sehir tut = dugum;
        while (tut.sol != null) {
            tut = tut.sol;
        }
        return tut;
    }
    
    public Sehir sil (Sehir kok, int plk) {
        
        if (kok == null) return kok; // Kök boş ise işlemi direkt bitir
        
        if (plk < kok.plaka) kok.sol = sil(kok.sol, plk);   // plaka
        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) { // PreOrder Kök - Sol - Sağ = kss
        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) { // InOrder Sol - Kök - Sağ = sks
        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) { // PostOrder Sol - Sağ - Kök = ssk
        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) { // InOrder Sol - Kök - Sağ = sks
        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){
        // Düğümün dengesini hesaplayalım
        denge_hesapla(k_dgm);

        // Balans her bir düğüm için mutlak değer 2 olmuş ise dengesizlik vardır.
        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

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sskirat
 */

 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); // Preorder
       System.out.println("\n");
       
       A.sks(A.kok); // Inorder
       System.out.println("\n");
       
       A.ssk(A.kok); // Postorder
       System.out.println("\n");
       
       // HARİTADA GÖSTER (BONUS)
       // A.gps(plaka, "zoom_orani")
       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