İkili Ağaçlar Binary Tree

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

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

Node* yeniDugum(int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(1); }
    n->data  = data;
    n->left  = NULL;
    n->right = NULL;
    return n;
}

/* Referans ağacı oluştur:
 *        1
 *       / \
 *      2   3
 *     / \ / \
 *    4  5 6  7
 */
Node* referansAgac() {
    Node* r = yeniDugum(1);
    r->left        = yeniDugum(2);
    r->right       = yeniDugum(3);
    r->left->left  = yeniDugum(4);
    r->left->right = yeniDugum(5);
    r->right->left = yeniDugum(6);
    r->right->right= yeniDugum(7);
    return r;
}

void inorder(Node* node) {
    if (node == NULL) return;

    inorder(node->left);       // 1. Sol alt ağaç
    printf("%d ", node->data);  // 2. Kökü yazdır
    inorder(node->right);      // 3. Sağ alt ağaç
}
// Çıktı: 4 2 5 1 6 3 7

void preorder(Node* node) {
    if (node == NULL) return;

    printf("%d ", node->data);  // 1. Kökü yazdır ★
    preorder(node->left);      // 2. Sol alt ağaç
    preorder(node->right);     // 3. Sağ alt ağaç
}
// Çıktı: 1 2 4 5 3 6 7

void postorder(Node* node) {
    if (node == NULL) return;

    postorder(node->left);     // 1. Sol alt ağaç
    postorder(node->right);    // 2. Sağ alt ağaç
    printf("%d ", node->data);  // 3. Kökü yazdır ★
}
// Çıktı: 4 5 2 6 7 3 1

/* ── Basit kuyruk (level-order için) ── */
#define QMAX 100
typedef struct {
    Node* items[QMAX];
    int   front, rear, count;
} Queue;

void  qInit(Queue* q)          { q->front=0; q->rear=-1; q->count=0; }
int   qEmpty(Queue* q)         { return q->count==0; }
void  enqueue(Queue* q, Node* n) {
    q->rear = (q->rear+1) % QMAX;
    q->items[q->rear] = n;
    q->count++;
}
Node* dequeue(Queue* q) {
    Node* n = q->items[q->front];
    q->front = (q->front+1) % QMAX;
    q->count--;
    return n;
}

/* ── Level-Order Traversal ── */
void levelOrder(Node* root) {
    if (!root) return;

    Queue q;
    qInit(&q);
    enqueue(&q, root);

    while (!qEmpty(&q)) {
        Node* cur = dequeue(&q);
        printf("%d ", cur->data);       // yazdır

        if (cur->left)  enqueue(&q, cur->left);
        if (cur->right) enqueue(&q, cur->right);
    }
    printf("\n");
}
// Çıktı: 1 2 3 4 5 6 7

Node* insert(Node* root, int deger) {
    Node* yeni = yeniDugum(deger);
    if (!root) return yeni;

    Queue q;
    qInit(&q);
    enqueue(&q, root);

    while (!qEmpty(&q)) {
        Node* cur = dequeue(&q);

        if (!cur->left) {
            cur->left = yeni;  // ilk boş sol → ekle
            return root;
        } else {
            enqueue(&q, cur->left);
        }

        if (!cur->right) {
            cur->right = yeni; // ilk boş sağ → ekle
            return root;
        } else {
            enqueue(&q, cur->right);
        }
    }
    return root; // ulaşılmaz (güvenlik)
}
// Karmaşıklık: O(n) — en kötüde tüm düğümleri dolaşır

/* ── En derin, en sağdaki düğümü sil ── */
void enDerinSil(Node* root, Node* hedef) {
    Queue q;
    qInit(&q);
    enqueue(&q, root);

    while (!qEmpty(&q)) {
        Node* cur = dequeue(&q);

        // Hedefin ebeveynini bul ve bağını kes
        if (cur->left) {
            if (cur->left == hedef) {
                cur->left = NULL;
                free(hedef);
                return;
            }
            enqueue(&q, cur->left);
        }
        if (cur->right) {
            if (cur->right == hedef) {
                cur->right = NULL;
                free(hedef);
                return;
            }
            enqueue(&q, cur->right);
        }
    }
}

/* ── Düğüm silme ── */
Node* deleteNode(Node* root, int deger) {
    if (!root) return NULL;

    // Tek düğümlü ağaç
    if (!root->left && !root->right) {
        if (root->data == deger) {
            free(root);
            return NULL;
        }
        return root;
    }

    Queue q;
    qInit(&q);
    enqueue(&q, root);

    Node* hedef = NULL;   // silinecek düğüm
    Node* enDerin = NULL; // en derin sağdaki

    while (!qEmpty(&q)) {
        enDerin = dequeue(&q);

        if (enDerin->data == deger)
            hedef = enDerin;

        if (enDerin->left)  enqueue(&q, enDerin->left);
        if (enDerin->right) enqueue(&q, enDerin->right);
    }
    // Döngü bittiğinde enDerin = son dequeue edilen = en derin sağdaki

    if (hedef) {
        hedef->data = enDerin->data;  // veriyi takas et
        enDerinSil(root, enDerin);     // yaprak düğümü sil
    }
    return root;
}
// Karmaşıklık: O(n) — iki BFS geçişi

void agaciSil(Node* node) {
    if (!node) return;

    agaciSil(node->left);   // 1. Sol alt ağacı sil
    agaciSil(node->right);  // 2. Sağ alt ağacı sil
    free(node);              // 3. Kendini sil (postorder!)
}
// Silme sırası: 4→5→2→6→7→3→1 (postorder)

int height(Node* node) {
    if (!node) return -1;  // NULL → -1 (kenar sayısı)

    int solH = height(node->left);
    int sagH = height(node->right);

    return (solH > sagH ? solH : sagH) + 1;
}
// Referans ağaç → height = 2
// Karmaşıklık: O(n) — her düğüm tam 1 kez ziyaret edilir

int dugumSayisi(Node* node) {
    if (!node) return 0;
    return 1 + dugumSayisi(node->left)
               + dugumSayisi(node->right);
}
// Referans ağaç → 7
// Karmaşıklık: O(n)

int yaprakSayisi(Node* node) {
    if (!node) return 0;
    if (!node->left && !node->right)
        return 1;  // yaprak!
    return yaprakSayisi(node->left)
         + yaprakSayisi(node->right);
}
// Referans ağaç → 4
// Karmaşıklık: O(n)

int main() {
    Node* root = referansAgac();

    printf("=== İkili Ağaç Demo ===\n\n");

    printf("Inorder:     "); inorder(root);    printf("\n");
    printf("Preorder:    "); preorder(root);   printf("\n");
    printf("Postorder:   "); postorder(root);  printf("\n");
    printf("Level-order: "); levelOrder(root);

    printf("\nYükseklik:    %d\n", height(root));
    printf("Düğüm sayısı: %d\n", dugumSayisi(root));
    printf("Yaprak sayısı: %d\n", yaprakSayisi(root));

    printf("\n--- insert(8) ---\n");
    root = insert(root, 8);
    printf("Level-order: "); levelOrder(root);
    printf("Düğüm sayısı: %d\n", dugumSayisi(root));

    printf("\n--- delete(2) ---\n");
    root = deleteNode(root, 2);
    printf("Level-order: "); levelOrder(root);
    printf("Düğüm sayısı: %d\n", dugumSayisi(root));

    agaciSil(root);
    printf("\nAğaç silindi (bellek temiz).\n");
    return 0;
}

=== İkili Ağaç Demo ===

Inorder:     4 2 5 1 6 3 7
Preorder:    1 2 4 5 3 6 7
Postorder:   4 5 2 6 7 3 1
Level-order: 1 2 3 4 5 6 7

Yükseklik:    2
Düğüm sayısı: 7
Yaprak sayısı: 4

--- insert(8) ---
Level-order: 1 2 3 4 5 6 7 8
Düğüm sayısı: 8

--- delete(2) ---
Level-order: 1 8 3 4 5 6 7
Düğüm sayısı: 7

Ağaç silindi (bellek temiz).