İkili Ağaçlar(Binary Tree)

Merhaba arkadaşlar önceki yazımda genel olarak ağaçlar konusuna değinmiştim. Bu yazımda da Binary Tree dediğimiz ikili ağaçlara detaylı olarak bakacağız.

Düzgün İkili Ağaç (Proper Binary Tree)

Yaprak olmayan düğümlerin iki çocuğu olan ağaçlardır. Düzgün olmayan ağaçlara da improper ağaçlar denilmektedir.

Dolu(Tam) İkili Ağaç (Full Binary Tree)

Yaprak olmayan tüm düğümlerin iki çocuğu olan ve seviyelerinin eşit olduğu ağaçlardır.

Üstteki örnek bir full binary tree örneğidir.

Tamamlanabilir İkili Ağaç (Complete Binary Tree)

Bu ağaç türünde ise yaprak olmayan tüm düğümlerin iki çocuğu olması gerekiyor fakat seviyelerinin aynı olmasına gerek yoktur. Adı da full yapılabilir olmasından dolayı tamamlanabilir ikili ağaçtır.

Binary Tree Düğüm Sayısı Bulma

Aslında mantık yürüterek bulunabilir. Üstte verdiğim örnek üzerinde düşünürsek derinliği 3’dür. Toplam yaprak sayısı da 7 olduğuna göre 2^n-1 bulunur formülü. Ama bu formül sadece full binary tree için geçerlidir. Eğer complate binary olarak düşünürsek derinliğini bir düşük alarak işlem yapılabilir son derinlikteki düğümlerin sayısı eklenebilir.

İkili Ağaç Kodu

Ağacımızın sol, sağ ve veri değerleri olacaktır. Aşağıdaki gibi yeni bir class tanımlayarak bunu yapabiliriz. (Java ve C#)

public class ikiliAgacDugum
    {
        public ikiliAgacDugum sol;
        public int veri;
        public ikiliAgacDugum sag;
}

İlk başta verdiğimiz örneğin düğümlerini kod ile ekleyelim..

        ikiliAgacDugum dugum = null;
        static void Main(string[] args) //java için public static void main
        {

            kok = dugumOlustur(2);
            kok.sol = dugumOlustur(3);
            kok.sag = dugumOlustur(8);
            kok.sol.sol = dugumOlustur(9);
            kok.sol.sag = dugumOlustur(4);
            kok.sag.sol = dugumOlustur(7);
            kok.sag.sag = dugumOlustur(1);
        }

Bu yazımdan sonra İkili Arama Ağaçlarına(Binary Search Tree) bakacağız.

Umarım faydalı olmuştur..