C'de İkili Ağaçlar: Yeni Başlayanlar İçin Eksiksiz Bir Kılavuz

Informatice Digital » Algoritmalar » C Dilinde İkili Ağaçlar: Yeni Başlayanlar İçin Eksiksiz Bir Kılavuz

C'deki ikili ağaçlara dair bu kapsamlı rehbere hoş geldiniz. Bu makalede, ikili ağaçların temellerini ve bunların C programlama dilinde nasıl uygulanacağını inceleyeceğiz. Programlamaya yeni başlıyorsanız veya sadece C becerilerinizi geliştirmek istiyorsanız, bu rehber tam size göre.

İkili ağaçlar, bilgisayar biliminde temel veri yapılarıdır ve çok çeşitli uygulamalarda kullanılırlar. Nasıl çalıştıklarını ve nasıl uygulanacaklarını anlamak, karmaşık problemleri daha verimli ve şık bir şekilde çözmenize yardımcı olacaktır.

Bu makale boyunca, ikili ağaçların yapısı, düğüm ekleme ve silme işlemleri, ağaçta gezinme ve eleman arama gibi temellerini inceleyeceğiz. Ayrıca, bu kavramların pratikte nasıl uygulandığını görebilmeniz için C programlama dilinde pratik örnekler sunacağız.

Öyleyse başlayalım!

İkili ağaçlar nelerdir?

İkili ağaçlar, birbirine bağlı düğümlerden oluşan hiyerarşik veri yapılarıdır. Her düğümün en fazla iki alt düğümü olabilir: biri solda, biri sağda. İkili ağaçları diğer veri yapılarından ayıran şey bu iki dallı yapıdır.

İkili bir ağaçta ilk düğüme kök düğüm adı verilir. Çocuk düğümlere çocuk düğümler, çocuğu olmayan düğümlere ise yaprak düğümler denir. Aynı seviyedeki düğümlere kardeş düğümler denir.

İkili Ağaçların Faydaları

İkili ağaçlar, verimli veri depolama ve arama açısından çeşitli avantajlar sunmaktadır. Başlıca faydalarından bazıları şunlardır:

1. Verimli aramaİkili ağaçlar, bağlı listeler gibi diğer veri yapılarına kıyasla, öğelerin çalışma zamanında daha hızlı aranmasına olanak tanır. Bu, ağacın hiyerarşik yapısından ve veri kümesini hızlı bir şekilde bölümlendirebilme yeteneğinden kaynaklanmaktadır.
2. Esnek yerleştirme ve çıkarmaİkili ağaçlar düğüm ekleme ve silme işlemlerine oldukça uyumludur. Diziler gibi statik veri yapılarından farklı olarak ikili ağaçlar dinamik olarak büyüyebilir ve yapılarını değiştirebilirler.
3. Hiyerarşik ilişkilerin temsiliİkili ağaçlar özellikle elemanlar arasındaki hiyerarşik ilişkileri göstermek için kullanışlıdır. Örneğin, bir dosya dizin yapısında, her dizin ağaçtaki bir düğüm olarak temsil edilebilir ve alt dizinler ve dosyalar da onun alt düğümleridir.

İkili ağacın yapısı

C'de ikili ağaçların uygulanmasına dalmadan önce, bunların temel yapısını anlamak önemlidir. İkili ağaçtaki her düğüm bir değer ve varsa sol ve sağ alt düğümlerine referanslar içerir.

Aşağıdaki tabloda ikili ağaçtaki bir düğümün yapısı gösterilmektedir:

İkili düğüm
değer
Sol düğüm
Sağ düğüm

Her düğüm, tam sayılar, karakterler veya daha karmaşık yapılar gibi her türlü veriyi depolayabilir. Kök düğüm ağacın başlangıç ​​noktasıdır ve buradan diğer tüm düğümlere erişebiliriz.

C'de ikili ağaçların uygulanması

İkili ağaçlar hakkında temel bir anlayışa sahip olduğumuza göre, artık bunları C programlama dilinde uygulamaya geçme zamanı geldi . Sonraki bölümde, C dilinde bir ikili ağaç yapısını nasıl tanımlayacağımızı ve kullanacağımızı göreceğiz.

İkili ağaç yapısının bildirilmesi

C'de ikili ağacın yapısını bir yapı ve işaretçiler kullanarak tanımlayabiliriz. Yapının temel bildirimi şu şekildedir:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

Bu yapıda, valor düğümde depolanan değeri temsil eder ve izquierdo y derecho sırasıyla sol ve sağ alt düğümlere işaretçilerdir.

Yeni bir düğüm oluşturma

İkili ağaçta yeni bir düğüm oluşturmak için, düğüm için bellek ayırmamız ve değerlerini ayarlamamız gerekir. İşte yeni bir düğüm oluşturan bir C fonksiyonu:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

İşlevi malloc Düğüme dinamik bellek tahsis etmek için kullanılır. Daha sonra node değerlerini ayarlayıp oluşturulan node'u döndürüyoruz.

Düğüm ekleme

Düğüm ekleme ikili ağaçlarda temel bir işlemdir. Düğüm değerine bağlı olarak ağaca doğru konumda yeni elemanlar eklemenize olanak tanır. Aşağıda ikili bir ağaca düğüm eklemek için bir C fonksiyonu bulunmaktadır:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

Bu fonksiyon ağacın köküne bir işaretçi ve eklenecek düğümün değerini alır. Eğer kök null ise ağaç boş demektir ve kökte yeni bir düğüm oluştururuz. Aksi takdirde düğümün değerini kök değeriyle karşılaştırırız ve düğümün sola mı yoksa sağa mı yerleştirileceğine karar veririz.

Düğümleri silme

İkili bir ağaçtaki düğümleri silmek biraz daha karmaşık olabilir. Silinecek düğümün çocuklarının olup olmaması gibi birkaç duruma bağlıdır. Aşağıda ikili bir ağaçtaki bir düğümü silmek için bir C fonksiyonu bulunmaktadır:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

Bu fonksiyonda düğümün değerinin geçerli kök değerinden küçük, büyük veya eşit olup olmadığını kontrol ediyoruz. Duruma göre aşağıdaki işlemleri gerçekleştiriyoruz:

• Eğer değer küçükse ağacın soluna doğru gidiyoruz.
• Eğer değer büyükse ağacın sağına doğru gidiyoruz.
• Değer eşitse, düğümün en yakın halefini (sağ alt ağaçtaki en küçük düğüm) buluruz ve onu geçerli düğümle değiştiririz. Daha sonra sağ alt ağaçtan halefi kaldırıyoruz.

İkili ağaçlarda gezinmeler

Gezinmeler, ikili bir ağacın tüm düğümlerini belirli bir sırayla ziyaret etmemizi sağlayan işlemlerdir. Üç yaygın tur türü vardır:

Sıralı geçiş : Önce sol alt ağacı, sonra mevcut düğümü ve son olarak sağ alt ağacı ziyaret eder. İşte ikili bir ağacın sıralı geçişini gerçekleştiren bir C fonksiyonu:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Öncelikli geçiş (Pre-order traversal ): Önce mevcut düğümü, sonra sol alt ağacı ve son olarak sağ alt ağacı ziyaret eder. İşte ikili bir ağacın öncelikli geçişini gerçekleştiren bir C fonksiyonu:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Ardışık geçiş (Post-order traversal ): Önce sol alt ağacı, sonra sağ alt ağacı ve son olarak da mevcut düğümü ziyaret eder. İşte ikili bir ağacın ardışık geçişini gerçekleştiren bir C fonksiyonu:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Öğeleri ara

İkili bir ağaçtaki elemanları aramak, veri yapısı içerisinde belirli bir değeri hızlı bir şekilde bulmamızı sağlar. İkili bir ağaçta bir elemanı aramak için bir C fonksiyonu şöyledir:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

Bu fonksiyon ikili ağaçta yinelemeli bir arama gerçekleştirir. Geçerli düğümün değeri aranan değere eşitse düğüm döndürülür. Aksi takdirde, değere göre sol veya sağ alt ağaç aranır ve değer bulunana veya boş bir düğüme ulaşılana kadar işlem tekrarlanır.

C'de ikili ağaçların uygulanmasına ilişkin örnekler

İkili ağaçların temellerini ve bunların C'de nasıl uygulanacağını ele aldığımıza göre, şimdi bazı pratik örneklere bakalım.

Örnek 1: İkili ağaç oluşturma

Diyelim ki şu değerlere sahip bir ikili ağaç oluşturmak istiyoruz: 10, 5, 15, 3, 7, 13, 18. Bunu C'de şu şekilde yapabiliriz:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

Bu örnekte, ağacın köküne bir işaretçi oluşturuyoruz ve ardından şu işlevi kullanıyoruz: insertarNodo değerleri ağaca eklemek için.

Örnek 2: İkili ağacın sıralı dolaşımı

İkili ağacın değerlerini sırayla yazdırmak için şu fonksiyonu çağırabiliriz: inOrden aşağıdaki gibi:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Bu örnek ağaçtaki değerleri artan sırada yazdıracaktır.

Sık sorulan sorular

1. İkili ağaç ile ikili arama ağacı arasındaki fark nedir?

İkili arama ağacı (BST), elemanların daha küçük değerlerin solda, daha büyük değerlerin sağda yer alacağı şekilde düzenlendiği özel bir ikili ağaç türüdür. Bu, normal ikili ağaca kıyasla öğelerin daha verimli bir şekilde aranmasını sağlar.

2. İkili ağaçta yinelenen değerlere sahip düğümlerim olabilir mi?

Evet, ikili bir ağaçta yinelenen değerlere sahip düğümlerin olması mümkündür. Ancak, ikili ağacın uygulanmasına ve özel kurallarına bağlı olarak, yinelenen düğümlerle başa çıkmanın farklı yolları olabilir. Bazı uygulamalar kopyalara izin verebilir ve bunları herhangi bir sırayla saklayabilirken, diğerleri kopya değerlerin özel olarak işlenmesini veya atılmasını gerektirebilir.

3. İkili ağaçtan belirli bir düğümü nasıl kaldırabilirim?

İkili ağaçtan belirli bir düğümü kaldırmak için şu adımları izlemeniz gerekir:

1. Silmek istediğiniz düğümü ağaç araması kullanarak bulun.
2. Elemenin farklı durumlarını ele alalım:
   • Eğer düğümün çocuğu yoksa, onu silip belleğini boşaltabilirsiniz.
   • Eğer düğümün sadece bir çocuğu varsa, düğümü onun çocuğuyla değiştirebilirsiniz.
   • Eğer düğümün iki çocuğu varsa, en yakın halefi (sağ alt ağaçtaki en küçük düğüm) bulmalı ve silinecek düğümün değerini halefin değeriyle değiştirmelisiniz. Daha sonra halefi ağaçtan çıkarın.
3. Doğru ağaç yapısını korumak için gerektiği gibi bağlantıları ve işaretçileri ayarlar.

4. Tam ikili ağaç nedir?

Tam ikili ağaç, sonuncusu hariç tüm seviyelerin tamamen doldurulduğu ve son seviyenin düğümlerinin mümkün olduğunca sola yerleştirildiği özel bir ikili ağaç türüdür. Bu, muhtemelen en son seviyedeki düğümler hariç tüm düğümlerin iki çocuğa sahip olduğu anlamına gelir; son seviyedeki düğümlerin bir çocuğu olabilir veya hiç çocuğu olmayabilir.

5. İkili ağacın yüksekliği nedir?

İkili bir ağacın yüksekliği, kökten yaprağa kadar olan en uzun yolun uzunluğudur. Başka bir deyişle, ağaçtaki kök ile herhangi bir yaprak arasındaki kenar sayısının maksimum olmasıdır. Yükseklik, seviye sayısı cinsinden ölçülür, bu nedenle yalnızca bir düğümü olan bir ağacın yüksekliği 0'dır ve boş bir ağacın yüksekliği yoktur.

6. Programlarımda ikili ağaç ne zaman kullanmalıyım?

İkili ağaçlar çeşitli durumlarda kullanışlıdır. İkili ağaçları kullanabileceğiniz bazı yaygın durumlar şunlardır:

• Verimli eleman arama: Bir veri yapısındaki elemanları hızlı bir şekilde aramanız gerekiyorsa, ikili ağaç verilere verimli bir erişim sağlayabilir.
• Hiyerarşik ilişkileri temsil etme: İkili ağaçlar, bir veritabanındaki dizin yapısı gibi hiyerarşik ilişkileri temsil etmek için idealdir. dosya sistemi.
• Veri Sıralama: Verileri verimli bir şekilde sıralamak ve logaritmik sürede arama, ekleme ve silme işlemleri gerçekleştirmek için ikili arama ağaçlarını kullanabilirsiniz.

Programlarınızda ikili ağaçları kullanmaya karar vermeden önce gereksinimlerinizi değerlendirmeyi ve ikili ağaçlardaki işlemlerin karmaşıklığını göz önünde bulundurmayı unutmayın.

Sonuç

Bu kapsamlı rehberde, C'deki ikili ağaçların temel kavramlarını inceledik. Yapılarını, düğümlerin nasıl eklenip çıkarılacağını, gezinmelerin nasıl gerçekleştirileceğini ve ikili ağaçta öğelerin nasıl aranacağını öğrendik.

Bu kılavuzun size ikili ağaçlar ve bunların C'de nasıl uygulanacağı konusunda sağlam bir anlayış kazandırmasını umuyoruz. İkili ağaçlar, programlamada çok çeşitli sorunları çözmenize yardımcı olabilecek çok yönlü ve güçlü veri yapılarıdır.

C'deki ikili ağaçlara ilişkin anlayışınızı güçlendirmek için verilen örneklerle pratik yapmayı ve deney yapmayı unutmayın. Yazılım öğrenme ve geliştirme yolculuğunuzda iyi şanslar!