Forum: Diğer Konular RSS
İkili Ağaç (veri yapısı)
Binary Tree (data structure)
Avatar
Salih Dinçer #1
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: İkili Ağaç (veri yapısı)
Merhaba,

Bu sanki yığın ağacına çok benziyor! Ama ilk kökün (root) sağında daha büyük eleman olması şart değilmiş gibi. Zaten aşağıda Ali hocam çeşitlerine değinmiş. Basit bir şekilde resim ile ifade edersek Wikipedia şekli şu:

[Resim: http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/300px-Binary_tree.svg.png]

Bu yabancı siteler iyice kafamı karıştırdı! Türkiye'den bağlantılara bakayım dedim. Şurada şöyle bir görsel buldum:

[Resim: http://www.ubenzer.com/deepo/2009/12/oben-agac-3.png]

acehreli:
"Binary heap" veri yapısı:

  http://en.wikipedia.org/wiki/Binary_heap

İlk eleman en üsttedir ve hemen kullanıma hazırdır. Bu veri yapısı "öncelikli kuyruk" diye çevirebileceğim "priority queue" uygulamalarına elverişlidir.

Salih Dinçer:
Bu durumda ikili ağaç (bitree) yapısından çok farklı görünüyor, yanılıyor muyum?

Tam anlamıyla bakarsak "binary tree" sırasız da olabilir. Böyle bir anlamda "binary heap" tam ve dengeli bir "binary tree"dir. (Ayrıca ben "bitree" diye bir kısaltmasını hiç duymadım ve Google'da da yok.)

Eğer "binary tree"yi çok tanınmış olan "binary tree data structure" anlamında kullanıyorsak o zaman aslında onun da çeşitleri var: sıralı, sırasız, dengeli, dengesiz, vs.

Sanırım Javacılar kullanıyor, şurada bir sınıf var:

http://www.clear.rice.edu/elec301/Projects01/bytes_dust/co…

Ayrıca kullandığımız kodlara benzer bir sınıf olduğunu karşılaştırmak için aşağıya yapıştırıyorum. Bir sonraki iletide D için C++'dan derlediğim kodu nakledeceğim...
public class BiTree{
    private BiTreeNode root;
    
    private void preOrder(BiTreeNode t, Visit vs){
        if(t != null){
            vs.print(t.data);
            preOrder(t.getLeft(),vs);
            preOrder(t.getRight(),vs);
        }
    }
    
    private void inOrder(BiTreeNode t, Visit vs){
        if(t != null){
            inOrder(t.getLeft(),vs);
            vs.print(t.data);
            inOrder(t.getRight(),vs);
        }
    }
    
    private void postOrder(BiTreeNode t, Visit vs){
        if(t != null){
            postOrder(t.getLeft(),vs);
            postOrder(t.getRight(),vs);
            vs.print(t.data);
        }
    }
    
    BiTree(){                        
        root = null;
    }
    
    BiTree(Object item, BiTree left, BiTree right){
        BiTreeNode l, r;
        if(left == null) 
            l = null;
        else
            l = left.root;
        if(right == null) 
            r = null;
        else 
            r = right.root;        
        root = new BiTreeNode(item, l, r);    
    }
    
    public void preOrder(Visit vs){
        preOrder(root, vs);
    }
    
    public void inOrder(Visit vs){
        inOrder(root, vs);
    }
    
    public void postOrder(Visit vs){
        postOrder(root,vs);
    }
}
Kaynak: http://www.codeforge.com/read/53827/BiTree.java__html

Bir de BTree diye bir şey varmış ama zaten şöyle bir uyarısı da var...:)

Not to be confused with Binary tree.

Başarılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bu veri yapısındaki denemelerimi Oben Işık'ın şu D uyarlamasıyla yaptım:
struct dugum{
    int sayi;
    dugum *sol, sag;
}
 
struct agac{
    dugum *kok;
    int elemansayisi;
 
    void preorder (dugum *p) {
        if(p) {
            writef("%d, ", p.sayi);
            preorder(p.sol);
            preorder(p.sag);
        }
    }
 
    void inorder (dugum *p) {
        if(p) {
            inorder(p.sol);
            writef("%5d", p.sayi);
            inorder(p.sag);
        }
    }
 
    void postorder (dugum *p) {
        if(p) {
            postorder(p.sol);
            postorder(p.sag);
            writef("%5d", p.sayi);
        }
    }
 
    void ekle(dugum *eklenecek){
        bool eklendi;
        dugum *tara = this.kok;
        dugum *yeni = new dugum();
        *yeni = *eklenecek;
      
        if(kok == null){
            kok = yeni;
            writefln("Ilk eleman eklendi ! (%d)", kok.sayi);
            this.elemansayisi++;
            return;
        }
 
        while(tara && !eklendi) {
            if(yeni.sayi < tara.sayi) {
                if(tara.sol != null) {
                    tara = tara.sol;
                } else {
                    writefln("%d dugumunun soluna %d elemanini ekledim, sanirim :D",
                                                              tara.sayi, yeni.sayi);
                    tara.sol = yeni;
                    eklendi = true;
                }
            } else if(yeni.sayi > tara.sayi) {
              if(tara.sag != null) {
                    tara = tara.sag;
              } else {
                    writefln("%d dugumunun sagina %d elemanini ekledim, sanirim :D",
                                                              tara.sayi, yeni.sayi);
                    tara.sag = yeni;
                    eklendi = true;
              }
            } else {
                writeln("Kopya");
                return;
            }
        }
        
        debug (yaz) {
            if(eklendi == true) {
                this.elemansayisi++;
            }
            writeln("Eleman sayisi : ", elemansayisi);
            write("PREORDER :\t");
            preorder(kok); writeln();
            
            write("INORDER :\t");
            inorder(kok); writeln();
            
            write("POSTORDER :\t");
            postorder(kok); writeln();
        }
    }
 
    void ara (dugum *eklenecek) {
        dugum *tara = this.kok;
        bool bulundu;
        int kacinci = 1;
 
        writeln("ARADIGIM: ", eklenecek.sayi);
 
        while(tara && !bulundu) {
            if(eklenecek.sayi < tara.sayi) {
                tara = tara.sol;
                kacinci++;
            } else if(eklenecek.sayi > tara.sayi) {
                tara = tara.sag;
                kacinci++;
            } else {
                writefln("Siz %d girdiniz ve ben de %d elemanini %d. denemede buldum",
                                                  eklenecek.sayi, tara.sayi, kacinci);
                return;
            }
        }
        writeln("Olmayan deger aradin eline ne gecti ? ");
    }
}
//debug = yaz; 
import std.stdio;
import std.container;
 
void main(){
    agac kayit;
    dugum yenikayit;
    auto veri = [ 30, 20, 50, 10, 40, 60, 35, 45, 75 ];
    //* togle-code
    foreach(i; veri) {
        debug (yaz) writeln("Eleman : ", i);
        yenikayit.sayi = i;/*/
    for(int i=1;i<10 ;i++) {
       debug (yaz) write("Eleman : ");
       readf(" %s", &yenikayit.sayi);//*/
       kayit.ekle(&yenikayit);
       debug (yaz) writeln();
    }
 
    while(true) {
        write("Hangi elemani ariyorsunuz ?  : ");
        readf(" %s", &yenikayit.sayi);
        kayit.ara(&yenikayit);
    }
}
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-22, 02:58:07 (UTC -08:00)