Ağaç Temelleri Tree Fundamentals

Neden Ağaç?

Şimdiye kadar incelediğimiz yapılar — dizi, bağlı liste, stack, kuyruk — hep doğrusal (linear) yapılardı: elemanlar bir sıra halinde dizilir, her birinin en fazla bir önceki ve bir sonraki vardır. Ancak gerçek dünya verilerinin büyük kısmı doğrusal değil hiyerarşiktir: dosya sistemi (klasörler içinde klasörler), organizasyon şeması (müdür → şefler → çalışanlar), HTML DOM (etiketler içinde etiketler), soyağacı...

Ağaç, doğrusal yapılardan farklı olarak bir düğümün birden fazla alt düğüme sahip olmasına izin verir. Bu dallanma yapısı arama, sıralama ve organizasyon işlemlerini dramatik olarak hızlandırır. 1.000.000 elemanlı sıralı bir dizide ikili arama 20 adım alır — aynı veri ağaç yapısında da ~20 adımda bulunur, ama ekleme ve silme O(log n)'de kalır (dizide O(n)).

Tanım — Özyinelemeli (Recursive)

Biçimsel olarak: bir ağaç T ya boş kümedir (T = ∅) ya da bir kök düğüm r ve sıfır veya daha fazla boş olmayan alt ağaç T₁, T₂, ..., Tₖ'dan oluşur. Her Tᵢ'nin kökü r'ye bir kenarla (edge) bağlıdır.

Ağaç Terminolojisi

Aşağıdaki ağaç üzerinde tüm temel terimleri tanımlayacağız:

Temel Terimler

Derinlik, Yükseklik ve Seviye

Bu üç kavram sıkça karıştırılır. Aşağıdaki görsel ve tablo ayrımı netleştirir:

Derece (Degree)

Derece kavramı iki düzeyde kullanılır:

Temel Özellikler

Ağaç Oluşturma

Ağaç düğümlerini bellekte temsil etmenin iki temel yolu vardır: bağlı yapı (linked — her düğüm pointer ile çocuklarına bağlı) ve dizi (array — indeks aritmetiği ile ebeveyn-çocuk ilişkisi). Bu bölümde ikili ağaç (binary tree) üzerinden her iki yöntemi göreceğiz.

Yöntem 1 — Bağlı Yapı (Linked)

Her düğüm bir struct'tır: veri + sol çocuk pointer + sağ çocuk pointer. Çocuğu olmayan yönler NULL'dur. Bu en yaygın ve en esnek gösterimdir.

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

typedef struct Node {
    int           data;
    struct Node*  left;
    struct Node*  right;
} Node;

/* ── Yeni düğüm oluştur ── */
Node* yeniDugum(int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    if (!n) { fprintf(stderr, "Bellek hatası!\n"); exit(1); }
    n->data  = data;
    n->left  = NULL;
    n->right = NULL;
    return n;
}

Şimdi referans ağacımızı elle oluşturalım:

int main() {
    // Düğümleri oluştur
    Node* kok  = yeniDugum(1);
    Node* n2   = yeniDugum(2);
    Node* n3   = yeniDugum(3);
    Node* n4   = yeniDugum(4);
    Node* n5   = yeniDugum(5);
    Node* n6   = yeniDugum(6);

    // Bağlantıları kur
    kok->left  = n2;      //     1
    kok->right = n3;      //    / \
    n2->left   = n4;      //   2   3
    n2->right  = n5;      //  / \   \
    n3->right  = n6;      // 4   5   6

    printf("Kök: %d\n", kok->data);
    printf("Sol: %d\n", kok->left->data);
    printf("Sağ: %d\n", kok->right->data);
    printf("Sol-Sol: %d\n", kok->left->left->data);
    printf("Sol-Sağ: %d\n", kok->left->right->data);
    printf("Sağ-Sağ: %d\n", kok->right->right->data);

    return 0;
}

/* Çıktı:
   Kök: 1
   Sol: 2
   Sağ: 3
   Sol-Sol: 4
   Sol-Sağ: 5
   Sağ-Sağ: 6
*/

Yöntem 2 — Dizi Gösterimi (Array)

İkili ağaç bir dizide saklanabilir. Kök indeks 0'da bulunur. Herhangi bir i indeksindeki düğüm için:

Ağaç Türlerine Genel Bakış

Ağaç yapısının çeşitli özelleşmiş türleri vardır. Her biri belirli bir problemi çözmek için tasarlanmıştır. Önce ikili ağaç (binary tree) alt türlerini, sonra ileri düzey yapıları tanıyalım.

İkili Ağaç (Binary Tree) Alt Türleri

İleri Düzey Ağaç Yapıları — Yol Haritası

İkili ağaç temel yapıdır; üzerine inşa edilen özelleşmiş yapılar farklı problemleri çözer:

Ağaçların Gerçek Dünya Kullanımları

Sonuç

Ağaç, doğrusal veri yapılarından hiyerarşik dünyaya geçiştir. Kök, yaprak, derinlik, yükseklik ve derece gibi temel terimler ağaç ailesi boyunca kullanılır. Bağlı yapı (pointer tabanlı) esneklik sağlarken, dizi gösterimi heap gibi complete ağaçlar için idealdir.

İkili ağacın beş alt türü — full, complete, perfect, dejenere ve dengeli — farklı yapısal garantiler sunar. Bu temeller üzerine BST, AVL, heap, B-tree, Red-Black tree ve trie gibi güçlü yapılar inşa edilir. Bir sonraki bölümde ikili ağacı derinlemesine inceleyeceğiz: dolaşma (traversal) yöntemleri, ekleme, silme ve ağaç ölçümleri.