Trie — Önek Ağacı

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

#define ALFABE_BOYUTU 26  // a-z (küçük İngilizce harf)

typedef struct TrieNode {
    struct TrieNode* children[ALFABE_BOYUTU];
    bool             isEndOfWord;  // ★ kelime sonu mu?
} TrieNode;

TrieNode* yeniDugum() {
    TrieNode* node = (TrieNode*)calloc(1, sizeof(TrieNode));
    // calloc ile tüm children = NULL, isEndOfWord = false
    return node;
}

/* Karakter → indeks dönüşümü */
int charIndex(char c) {
    return c - 'a';
}

void trieEkle(TrieNode* root, const char* kelime) {
    TrieNode* curr = root;

    for (int i = 0; kelime[i]; i++) {
        int idx = charIndex(kelime[i]);

        if (!curr->children[idx])
            curr->children[idx] = yeniDugum();  // yeni düğüm

        curr = curr->children[idx];              // ilerle
    }
    curr->isEndOfWord = true;                   // ★ kelime sonu
}

bool trieAra(TrieNode* root, const char* kelime) {
    TrieNode* curr = root;

    for (int i = 0; kelime[i]; i++) {
        int idx = charIndex(kelime[i]);
        if (!curr->children[idx])
            return false;   // karakter yok → kelime yok
        curr = curr->children[idx];
    }
    return curr->isEndOfWord;   // düğüm var ama kelime mi?
}

bool onekVar(TrieNode* root, const char* onek) {
    TrieNode* curr = root;

    for (int i = 0; onek[i]; i++) {
        int idx = charIndex(onek[i]);
        if (!curr->children[idx])
            return false;
        curr = curr->children[idx];
    }
    return true;   // isEndOfWord kontrol etmiyoruz!
}

bool cocuguVar(TrieNode* node) {
    for (int i = 0; i < ALFABE_BOYUTU; i++)
        if (node->children[i])
            return true;
    return false;
}

/* Dönüş: bu düğüm silinmeli mi? */
bool trieSilHelper(TrieNode* node, const char* kelime, int derinlik) {
    if (!node) return false;

    // Kelimenin sonuna ulaştık
    if (derinlik == strlen(kelime)) {
        if (!node->isEndOfWord)
            return false;   // kelime yok

        node->isEndOfWord = false;  // ★ işareti kaldır

        // Çocuğu yoksa silinebilir
        return !cocuguVar(node);
    }

    int idx = charIndex(kelime[derinlik]);
    bool silmeli = trieSilHelper(
        node->children[idx], kelime, derinlik + 1
    );

    if (silmeli) {
        free(node->children[idx]);
        node->children[idx] = NULL;

        // Bu düğüm de silinebilir mi?
        return !node->isEndOfWord && !cocuguVar(node);
    }

    return false;
}

void trieSil(TrieNode* root, const char* kelime) {
    trieSilHelper(root, kelime, 0);
}

/* DFS ile alt ağaçtaki tüm kelimeleri topla */
void dfsTara(TrieNode* node, char* buffer, int derinlik) {
    if (!node) return;

    if (node->isEndOfWord) {
        buffer[derinlik] = '\0';
        printf("  → %s\n", buffer);
    }

    for (int i = 0; i < ALFABE_BOYUTU; i++) {
        if (node->children[i]) {
            buffer[derinlik] = 'a' + i;
            dfsTara(node->children[i], buffer, derinlik + 1);
        }
    }
}

void otomatikTamamla(TrieNode* root, const char* onek) {
    TrieNode* curr = root;

    // Adım 1: Önekin son düğümüne git
    for (int i = 0; onek[i]; i++) {
        int idx = charIndex(onek[i]);
        if (!curr->children[idx]) {
            printf("'%s' öneki bulunamadı.\n", onek);
            return;
        }
        curr = curr->children[idx];
    }

    // Adım 2: DFS ile tüm sonuçları topla
    char buffer[256];
    strcpy(buffer, onek);
    printf("'%s' ile başlayanlar:\n", onek);
    dfsTara(curr, buffer, strlen(onek));
}

int kelimeSayisi(TrieNode* node) {
    if (!node) return 0;
    int sayac = node->isEndOfWord ? 1 : 0;
    for (int i = 0; i < ALFABE_BOYUTU; i++)
        sayac += kelimeSayisi(node->children[i]);
    return sayac;
}

int main() {
    TrieNode* root = yeniDugum();

    // ── Kelime Ekleme ──
    printf("=== Trie Demo ===\n\n");
    const char* kelimeler[] = {
        "araba", "ara", "arı", "bal",
        "bak", "balık", "can", "canan"
    };
    int n = 8;

    printf("--- Ekleme ---\n");
    for (int i = 0; i < n; i++) {
        trieEkle(root, kelimeler[i]);
        printf("  insert(\"%s\")\n", kelimeler[i]);
    }
    printf("Toplam: %d kelime\n", kelimeSayisi(root));

    // ── Kelime Arama ──
    printf("\n--- Arama ---\n");
    const char* aramalar[] = {"ara","araba","ar","bal","bala","can"};
    for (int i = 0; i < 6; i++)
        printf("  search(\"%s\") → %s\n", aramalar[i],
               trieAra(root, aramalar[i]) ? "Bulundu ✓" : "Yok ✗");

    // ── Önek Sorgulama ──
    printf("\n--- Önek Arama ---\n");
    const char* onekler[] = {"ar", "ba", "ca", "de"};
    for (int i = 0; i < 4; i++)
        printf("  startsWith(\"%s\") → %s\n", onekler[i],
               onekVar(root, onekler[i]) ? "Var ✓" : "Yok ✗");

    // ── Otomatik Tamamlama ──
    printf("\n--- Otomatik Tamamlama ---\n");
    otomatikTamamla(root, "ar");
    otomatikTamamla(root, "ba");
    otomatikTamamla(root, "c");

    // ── Silme ──
    printf("\n--- Silme ---\n");
    trieSil(root, "ara");
    printf("  delete(\"ara\")\n");
    printf("  search(\"ara\")   → %s\n", trieAra(root,"ara")?"Var":"Yok ✗");
    printf("  search(\"araba\") → %s\n", trieAra(root,"araba")?"Var ✓":"Yok");

    trieSil(root, "arı");
    printf("  delete(\"arı\")\n");

    printf("\n  Silme sonrası autocomplete(\"ar\"):\n");
    otomatikTamamla(root, "ar");
    printf("Kalan: %d kelime\n", kelimeSayisi(root));

    return 0;
}

=== Trie Demo ===

--- Ekleme ---
  insert("araba")
  insert("ara")
  insert("arı")
  insert("bal")
  insert("bak")
  insert("balık")
  insert("can")
  insert("canan")
Toplam: 8 kelime

--- Arama ---
  search("ara")   → Bulundu ✓
  search("araba") → Bulundu ✓
  search("ar")    → Yok ✗        ← önek var ama kelime değil
  search("bal")   → Bulundu ✓
  search("bala")  → Yok ✗        ← bu kelime eklenmedi
  search("can")   → Bulundu ✓

--- Önek Arama ---
  startsWith("ar") → Var ✓       ← ara, araba, arı başlar
  startsWith("ba") → Var ✓       ← bak, bal, balık başlar
  startsWith("ca") → Var ✓       ← can, canan başlar
  startsWith("de") → Yok ✗       ← hiçbir kelime "de" ile başlamıyor

--- Otomatik Tamamlama ---
'ar' ile başlayanlar:
  → ara
  → araba
  → arı
'ba' ile başlayanlar:
  → bak
  → bal
  → balık
'c' ile başlayanlar:
  → can
  → canan

--- Silme ---
  delete("ara")
  search("ara")   → Yok ✗        ← silindi
  search("araba") → Var ✓        ← etkilenmedi
  delete("arı")

  Silme sonrası autocomplete("ar"):
'ar' ile başlayanlar:
  → araba                          ← sadece araba kaldı
Kalan: 6 kelime