1-) VERİYAPILARI - AĞAÇ

Ağaç veri modeli, düğümlerden ve dallardan oluşur; düğümlerde  verilerin kendileri veya bir kısmı tutulurken, dallar diğer  düğümlere olan bağlantı ilişkilerini gösterir. Ağaç veri modeli,  özellikle kümenin büyük olduğu ve arama işleminin çok  kullanıldığı uygulamalarda etkin bir çözümsunar.

En üstteki düğüm kök (root), kendisine alttan hiçbir bağlantının  olmadığı düğüm yaprak (leaf), diğerleri de ara düğüm (internal  node) olarak adlandırılır. Bir düğüme alttan bağlı düğümlere  çocuk (child), üsten bağlı düğüme de o düğümün ailesi(parent)  denilir.

Ebeveyn (Parent): Bir c duğumunden koke olan yol uzerindeki ilk duğumdur. Bu c duğumu p’nin cocuğudur (child).

Yaprak (Leaf): Cocuğu olmayan duğumdur.

Kardeş (Sibling): Ebeveyni aynı olan duğumlerdir.

Ata (Ancestor): Bir d duğumunun ataları, d’den koke olan yol uzerindeki tum duğumlerdir.

Descendant: Bir duğumun cocukları, torunları vs. gibi sonraki neslidir.

Yol Uzunluğu: Yol uzerindeki ayrıt sayısıdır.

n Düğümünün Derinliği: Bir n duğumunden koke olan yolun uzunluğudur. Kokun derinliği sıfırdır.

n Düğümünün Yüksekliği: Bir n duğumunden en alttaki descendant duğumune olan yolun uzunluğudur. Başka bir deyişle neslinin en sonu olan duğumdur.

Bir Ağacın Yüksekliği: Kokun yuksekliğine ağacın yuksekliği de denir.

n Düğümünde Köklenen Alt Ağaç (Subtree Rooted at n): Bir n duğumu ve n duğumunun soyu (descendant) tarafından oluşan ağactır.

Binary Tree (İkili Ağaç): İkili ağacta bir duğumun sol cocuk ve sağ cocuk olmak uzere en fazla iki cocuğu olabilir.

D (level) / Derinlik (depth): Kok ile duğum arasındaki yolun uzerinde bulunan ayrıtların sayısıdır. Bir duğumun kok duğumden olan uzaklığıdır. Kokun duzeyi sıfırdır (bazı yayınlarda 1 olarak da belirtilmektedir).

İkili Ağaç

Eğer bir ağactaki her duğumun en fazla 2 cocuğu varsa bu ağaca ikili ağac denir.Diğer bir deyişle bir ağactaki her duğumun derecesi en fazla 3 ise o ağaca ikili ağac denir. İkili ağacların onemli ozelliği eğer dengeli ise cok hızlı bir şekilde ekleme, silme ve arama işlemlerini yapabilmesidir. Ağac veri yapısı uzerinde işlem yapan fonksiyonların bircoğu kendi kendini cağıran (recursive) fonksiyonlardır. Cunku bir ağacı alt ağaclara bolduğumuzde elde edilen her parca yine bir ağac olacaktır ve fonksiyonumuz yine bu ağac uzerinde işlem yapacağı icin kendi kendini cağıracaktır.

İkili ağac veri yapısının tanımında ağac veri yapısının tum tanımları gecerlidir, farklı olan iki nokta ise şunlardır:

i. Ağacın derecesi (degree of tree) 2'dir.

ii. Sol ve sağ alt ağacın yer değiştirmesiyle cizilen ağac aynı ağac değildir.

İkili bir ağac icin veri yapısı aşağıdaki gibi tanımlanabilir;

n tane düğümden oluşan BTA

• min derinlik: logn,
• max derinlik: n

Tüm düğümlerin iki çocuğu varsa düzgün BT denir.

İhtiyac olduğunda yapı icerisinde bir de parent tanımlanabilir. Ağacların yapısının da bağlı liste olduğu tanımdan anlaşılabilir. Fakat normal bağlı listelerden farkı nonlinear olmasıdır. Yani doğrusal değildir

İkili Ağaçlar Üzerinde Dolaşma

İkili Ağaca Sıralı Veri Eklemek

İkili bir ağaca veri ekleme işleminde sol cocuğun verisi (data) ebeveyninin verisinden kucuk olmalı, sağ cocuğun verisi ise ebeveyninin verisinden buyuk ya da eşit olmalıdır. Altta insert isimli ekleme fonksiyonunun nasıl yazıldığını goruyorsunuz. Fonksiyon, veri eklendikten sonra ağacın kok adresiyle geri donmektedir

Bir Ağacın Düğümlerinin Sayısını Bulmak

Inorder sıralama bicimine biraz benzemektedir. Sıralamada once sol taraf yazdırılıyor, ardından kok ve sonra da sağ taraf yazdırılarak işlem tamamlanıyordu. Bu benzetimle ağac uzerinde dolaşılarak tum duğumlerin sayısı bulunabilir. Fonksiyon rekursif olarak modellendiğinde algoritma daha kolay bir şekil almaktadır. Geri donuş değeri tamsayı olacağı icin int turden olmalı, input parametresi olarak ağacın kokunu almalıdır. Rekursif fonksiyonlarda mutlaka bir cıkış yolu vardır ve cıkış yolu olarak if-else bloğunun kullanıldığından bahsetmiştik. Şimdi bir ağacın duğumlerinin sayısını veren size isimli fonksiyonu yazalım.

Bir Ağacın Yüksekliğini Bulmak

Bir Ağacın Yapraklarını Gezmek

void yaprakGez(BTREE* root)

{

    if (root->left != NULL)

    { yaprakGez(root->left); }

    if (root->right != NULL)

    { yaprakGez(root->right); }

    if (root->right == NULL && root->left == NULL)

    { printf("%d-", root->değer); }

}

İkili Arama Ağacından Bir Düğüm Silmek

İkili bir arama ağacında bir duğumun en fazla iki cocuğu olabileceğini duşunduğumuzde bunlar;

1- Silinecek olan duğumun cocuğu yok ise,

2- Silinecek olan duğumun sadece bir cocuğu var ise,

3- Silinecek olan duğumun iki cocuğu var ise, nasıl bir algoritma kurmamız gerektiğidir.

İkili Arama Ağacında Bir Düğümü Bulmak

İkili Arama Ağacı Kontrolü