Veri Yapıları ve Programlama

10 - Ağaç (Tree) Veri Yapısı

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2026

Ağaç (Tree)

Ağaç, düğümler ve bu düğümler arasındaki bağlantılardan oluşan, doğrusal olmayan hiyerarşik bir veri yapısıdır.

Neden Ağaç Veri Yapısı?

Bazı veriler doğal olarak hiyerarşik yapıdadır.

Dosya ve klasör yapıları
Kurum şemaları
Web sayfası bileşenleri
Matematiksel ifadeler
Karar yapıları

Bu tür verileri dizilerde de tutmak teknik olarak mümkündür; ancak üst-alt ilişkisini ve dallanmayı doğrudan modellemek hem güçleşir hem de gereksiz karmaşıklık yaratır.

Ağaçların Kullanım Alanları

Dosya sistemleri: Klasörler ve alt klasörler
Derleyiciler: Sözdizim ağaçları ve ifade ağaçları
Web teknolojileri: HTML/DOM yapısı
Veritabanları: B-ağacı ve B+ ağacı gibi indeks yapıları
Yapay zeka: Karar ağaçları

Bu derste, temel kavramları tanımak için özellikle ikili ağaç (binary tree) yapısına odaklanacağız.

Temel Kavramlar

Bir ağaçta genellikle şu terimler kullanılır:

Kök (root): En üstte bulunan düğüm
Ebeveyn (parent): Altında çocuk düğüm bulunan düğüm
Çocuk (child): Bir ebeveynin altında yer alan düğüm
Kardeş (sibling): Aynı ebeveyne sahip düğümler
İç düğüm (internal node): En az bir çocuğu olan, yani yaprak olmayan düğüm
Yaprak (leaf): Çocuğu olmayan düğüm
Alt ağaç (subtree): Bir düğüm ve onun altındaki tüm düğümlerden oluşan yapı

İkili ağaçta bir düğümün en fazla iki çocuğu olabilir: sol çocuk ve sağ çocuk.

Örnek Ağaç

Aşağıdaki ikili ağaçta:

     10
   /    \
  4      13
 / \    /  \
3   7  11  15

10 kök düğümdür.
4 ve 13, 10’un çocuklarıdır.
4 ile 13 kardeştir.
3, 7, 11 ve 15 yaprak düğümlerdir.
10, 4 ve 13 iç düğümlerdir.

Kenar, Derinlik ve Düzey

Kenar (edge): Bir ebeveyn düğüm ile onun çocuğu arasındaki bağlantıdır.

Derinlik (depth): Bir düğümün derinliği, kökten o düğüme kadar olan yol üzerindeki kenar sayısıdır.

Düzey (level): Aynı derinliğe sahip düğümler aynı düzeydedir. Bu derste düzey numarasını derinlikle aynı kabul edeceğiz; yani kök 0. düzeydedir.

Bu nedenle:

kökün derinliği 0’dır
kökün çocukları 1. düzeydedir
torunları 2. düzeydedir

Yukarıdaki örnekte ağaçta toplam 7 düğüm ve 6 kenar vardır.

Derinlik Örneği

Yandaki ağaç için:

2’nin derinliği 2’dir.
1’in derinliği 0’dır.
11’in derinliği 3’tür.

Yükseklik

Yükseklik (height): Ağacın yüksekliği, kökten en derin yaprağa kadar olan en uzun yol üzerindeki kenar sayısıdır.

Başka bir ifadeyle, ağacın yüksekliği en derin düğümün derinliğine eşittir.

Yandaki ağaçta en derin yaprağa giden yolda 3 kenar bulunduğu için ağacın yüksekliği 3’tür.

C Dilinde Gösterimi

İkili ağaçtaki her düğümde veri tutulur ve sol/sağ alt ağacı gösteren iki işaretçi bulunur.

typedef struct TreeNode {
    int item;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

item: düğümde tutulan veri
left: sol çocuğu gösteren işaretçi
right: sağ çocuğu gösteren işaretçi

Bir düğümün sol veya sağ çocuğu yoksa ilgili işaretçi NULL olur.

Düğüm Oluşturma Örneği

Bellekte bir düğüm şu şekilde oluşturulur:

TreeNode *root = malloc(sizeof(TreeNode));
root->item  = 10;
root->left  = NULL;
root->right = NULL;

malloc çağrısı bellekte bir TreeNode için yer ayırır. left ve right alanları başlangıçta NULL olarak atanır; çocuk düğümler eklendikçe bu işaretçiler güncellenir.

Not: Gerçek programlarda malloc çağrısının başarısız olup olmadığı da kontrol edilmelidir; bellek yetersizse NULL döndürür.

Dolu Ağaç

Dolu ikili ağaç (full binary tree): Her iç düğümün tam olarak iki çocuğu olduğu, yaprakların ise hiç çocuğu olmadığı ağaçtır.

Başka bir ifadeyle, bir düğümün ya 0 ya da 2 çocuğu vardır.

Dolu ağaç:

Dolu değil (tek çocuklu iç düğüm var):

Tam Ağaç

Tam ikili ağaç (complete binary tree): Son düzey dışında tüm düzeylerin tamamen dolu olduğu ve son düzeydeki düğümlerin soldan sağa boşluksuz yerleştirildiği ağaçtır.

Tam ağaç (son düzey sola dayalı):

Tam değil (son düzeyde boşluk var):

      1
    /   \
   2     3
  / \     \
 4   5     7

Tam olmak da her iç düğümün mutlaka iki çocuğu olduğu anlamına gelmez.

Örnek Ağaç

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int item;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int value) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (node == NULL) {
        printf("Bellek ayirma hatasi!\n");
        exit(1);
    }

    node->item = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Örnek Ağaç

int main(void) {
    TreeNode *root = createNode(10);

    root->left = createNode(4);
    root->right = createNode(13);

    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(11);
    root->right->right = createNode(15);

    printf("Kok: %d\n", root->item);
    printf("Sol cocuk: %d, Sag cocuk: %d\n", root->left->item, root->right->item);
    printf("Yapraklar: %d, %d, %d, %d\n",
           root->left->left->item,
           root->left->right->item,
           root->right->left->item,
           root->right->right->item);

    return 0;
}

Alıştırmalar

8 kök düğüm müdür?
8’in çocukları hangileridir?
Hangi düğümler yaprak düğümdür?
Hangi düğümler kardeştir?

Alıştırmaların Devamı

8’in derinliği kaçtır?
5’in derinliği kaçtır?
4’ün derinliği kaçtır?
2’nin derinliği kaçtır?
Ağacın yüksekliği kaçtır?
Bu ağaç dolu mudur?
Bu ağaç tam mıdır?

Kısa Değerlendirme

Aşağıdaki ifadelerden hangisi yanlıştır?

Ağaçlar hiyerarşik ilişkileri göstermek için kullanılabilir.
Ağaç yapısında düğümler bulunur; düğümler arasındaki bağlantılar kenarlarla gösterilir.
Her düğüm bir veriyi ya da nesneyi temsil edebilir.
Her kenar doğrudan bağlı iki düğüm arasındaki bağlantıyı gösterir.
Ağaçlarda arama işlemi, bağlı listelere göre her durumda daha hızlıdır.

Özet

Ağaç, doğrusal olmayan hiyerarşik bir veri yapısıdır.
Düğümler ve bu düğümler arasındaki bağlantılardan oluşur.
İkili ağaçta her düğümün en fazla iki çocuğu vardır.
Derinlik, kökten ilgili düğüme kadar olan kenar sayısıdır.
Yükseklik, kökten en derin yaprağa kadar olan en uzun yol üzerindeki kenar sayısıdır.
Dolu ağaç ve tam ağaç aynı şey değildir.
NULL kontrolü zorunludur: boş bir düğüme erişim tanımsız davranışa (undefined behavior) yol açar.

Çalışma Sorusu

Basit bir ikili ağaç yapısını C dilinde elle oluşturup aşağıdaki işlemleri deneyin:

Toplam düğüm sayısını hesaplama
Yaprak düğümleri bulma
Ağacın yüksekliğini hesaplama
Ağacı girintili biçimde (her düzey için bir sekme kaydırarak) ekrana yazdırma