الأشجار الثنائية في لغة C: دليل كامل للمبتدئين

إنفورماتيك ديجيتال » خوارزميات » الأشجار الثنائية في لغة C: دليل كامل للمبتدئين

مرحبًا بك في هذا الدليل الشامل حول الأشجار الثنائية في لغة C. في هذه المقالة، سنستكشف أساسيات الأشجار الثنائية وكيفية تنفيذها في لغة البرمجة C. إذا كنت مبتدئًا في البرمجة أو كنت ترغب فقط في تحسين مهاراتك في لغة C، فهذا الدليل مناسب لك.

تُعدّ الأشجار الثنائية من هياكل البيانات الأساسية في علوم الحاسوب، وتُستخدم في نطاق واسع من التطبيقات. إن فهم كيفية عملها وكيفية تطبيقها سيساعدك على حلّ المشكلات المعقدة بكفاءة وفعالية أكبر.

سنتناول في هذه المقالة أساسيات الأشجار الثنائية، بما في ذلك بنيتها، وإضافة وحذف العقد، والتنقل فيها، والبحث عن العناصر. كما سنقدم أمثلة عملية بلغة البرمجة C لتتمكن من رؤية كيفية تطبيق هذه المفاهيم عمليًا.

اذا هيا بنا نبدأ!

ما هي الأشجار الثنائية؟

الأشجار الثنائية هي هياكل بيانات هرمية مكونة من عقد مترابطة. يمكن أن تحتوي كل عقدة على ما يصل إلى عقدتين فرعيتين: واحدة على اليسار وواحدة على اليمين. هذا الهيكل ذو الفرعين هو ما يميز الأشجار الثنائية عن هياكل البيانات الأخرى.

في الشجرة الثنائية، تسمى العقدة الأولى بالعقدة الجذرية. تُسمى العقد الفرعية بالعقد الفرعية، وتُسمى العقد التي لا تحتوي على أطفال بالعقد الورقية. تُسمى العقد الموجودة على نفس المستوى بالعقد الشقيقة.

فوائد الأشجار الثنائية

توفر الأشجار الثنائية العديد من المزايا من حيث تخزين البيانات والبحث بكفاءة. تتضمن بعض الفوائد الرئيسية ما يلي:

1. بحث فعالتسمح الأشجار الثنائية بالبحث عن العناصر في وقت التشغيل بشكل أسرع من هياكل البيانات الأخرى، مثل القوائم المرتبطة. ويرجع ذلك إلى الهيكل الهرمي للشجرة وقدرتها على تقسيم مجموعة البيانات بسرعة.
2. إدخال وإزالة مرنةتتمتع الأشجار الثنائية بقدرة عالية على التكيف مع عمليات إدراج العقد وحذفها. على عكس هياكل البيانات الثابتة مثل المصفوفات، يمكن للأشجار الثنائية أن تنمو وتغير بنيتها بشكل ديناميكي.
3. تمثيل العلاقات الهرميةتُعد الأشجار الثنائية مفيدة بشكل خاص لتمثيل العلاقات الهرمية بين العناصر. على سبيل المثال، في بنية دليل الملف، يمكن تمثيل كل دليل كعقدة في الشجرة، مع الدلائل الفرعية والملفات كعقد تابعة لها.

بنية الشجرة الثنائية

قبل أن نتعمق في تنفيذ الأشجار الثنائية في لغة C، من المهم أن نفهم بنيتها الأساسية. تحتوي كل عقدة في الشجرة الثنائية على قيمة ومراجع لعقدها الفرعية اليمنى واليسرى، إذا كان لديها أي منها.

يوضح الجدول التالي بنية العقدة في الشجرة الثنائية:

عقدة ثنائية
بسالة
العقدة اليسرى
العقدة اليمنى

يمكن لكل عقدة تخزين أي نوع من البيانات، مثل الأعداد الصحيحة، أو الأحرف، أو الهياكل الأكثر تعقيدًا. العقدة الجذرية هي نقطة البداية للشجرة، ومن خلالها يمكننا الوصول إلى جميع العقد الأخرى.

تنفيذ الأشجار الثنائية في لغة C

بعد أن اكتسبنا فهمًا أساسيًا للأشجار الثنائية، حان الوقت لتطبيقها في لغة البرمجة C. سنرى لاحقًا كيفية تعريف واستخدام بنية الشجرة الثنائية في C.

إعلان بنية الشجرة الثنائية

في لغة C، يمكننا إعلان بنية شجرة ثنائية باستخدام بنية ومؤشرات. وهنا الإعلان الأساسي للهيكل:

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

في هذا الهيكل، valor يمثل القيمة المخزنة في العقدة، و izquierdo y derecho هي مؤشرات إلى العقد الفرعية اليسرى واليمنى على التوالي.

إنشاء عقدة جديدة

لإنشاء عقدة جديدة في الشجرة الثنائية، نحتاج إلى تخصيص ذاكرة للعقدة وتعيين قيمها. فيما يلي دالة C التي تقوم بإنشاء عقدة جديدة:

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;
}

الوظيفة malloc يتم استخدامه لتخصيص الذاكرة الديناميكية للعقدة. ثم نقوم بتعيين قيم العقدة وإرجاع العقدة التي تم إنشاؤها.

إدراج العقد

يعد إدراج العقدة عملية أساسية في الأشجار الثنائية. يسمح لك بإضافة عناصر جديدة إلى الشجرة في الموضع الصحيح استنادًا إلى قيمة العقدة. فيما يلي دالة C لإدراج عقدة في شجرة ثنائية:

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;
}

تتلقى هذه الوظيفة مؤشرًا إلى جذر الشجرة وقيمة العقدة التي سيتم إدراجها. إذا كان الجذر فارغًا، فهذا يعني أن الشجرة فارغة وسنقوم بإنشاء عقدة جديدة في الجذر. وإلا فإننا نقارن قيمة العقدة بقيمة الجذر ونقرر ما إذا كان سيتم إدراج العقدة إلى اليسار أو اليمين.

حذف العقد

قد يكون حذف العقد في شجرة ثنائية أكثر تعقيدًا بعض الشيء. يعتمد ذلك على عدة حالات، مثل ما إذا كانت العقدة التي سيتم حذفها لها أبناء أم لا. فيما يلي دالة C لحذف عقدة في شجرة ثنائية:

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;
}

في هذه الوظيفة، نتحقق مما إذا كانت قيمة العقدة أقل من أو أكبر من أو تساوي قيمة الجذر الحالي. اعتمادًا على الحالة، نقوم بالإجراءات التالية:

• إذا كانت القيمة أصغر، ننتقل إلى يسار الشجرة.
• إذا كانت القيمة أكبر ننتقل إلى يمين الشجرة.
• إذا كانت القيمة متساوية، فإننا نبحث عن الخليفة الأقرب للعقدة (أصغر عقدة في الشجرة الفرعية اليمنى) ونستبدلها بالعقدة الحالية. ثم نقوم بإزالة الخليفة من الشجرة الفرعية اليمنى.

التنقلات في الأشجار الثنائية

عمليات العبور هي عمليات تسمح لنا بزيارة جميع عقد شجرة ثنائية بترتيب معين. هناك ثلاثة أنواع شائعة من الجولات:

المرور الترتيبي : يزور الشجرة الفرعية اليسرى أولاً، ثم العقدة الحالية، وأخيراً الشجرة الفرعية اليمنى. إليك دالة بلغة C تُنفذ المرور الترتيبي لشجرة ثنائية:

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

اجتياز الترتيب المسبق : يزور العقدة الحالية أولاً، ثم الشجرة الفرعية اليسرى، وأخيراً الشجرة الفرعية اليمنى. إليك دالة بلغة C تُجري اجتياز الترتيب المسبق لشجرة ثنائية:

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

اجتياز ما بعد الترتيب : يزور الشجرة الفرعية اليسرى أولاً، ثم الشجرة الفرعية اليمنى، وأخيراً العقدة الحالية. إليك دالة بلغة C تُجري اجتياز ما بعد الترتيب لشجرة ثنائية:

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

البحث عن العناصر

يتيح لنا البحث عن العناصر في شجرة ثنائية العثور بسرعة على قيمة محددة داخل بنية البيانات. فيما يلي دالة C للبحث عن عنصر في شجرة ثنائية:

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);
    }
}

تقوم هذه الوظيفة بإجراء بحث متكرر في الشجرة الثنائية. إذا كانت قيمة العقدة الحالية تساوي القيمة التي تم البحث عنها، فسيتم إرجاع العقدة. وإلا، يتم البحث في الشجرة الفرعية اليسرى أو اليمنى استنادًا إلى القيمة ويتم تكرار العملية حتى يتم العثور على القيمة أو الوصول إلى عقدة فارغة.

أمثلة على تنفيذ الأشجار الثنائية في لغة C

الآن بعد أن قمنا بتغطية أساسيات الأشجار الثنائية وكيفية تنفيذها في لغة C، دعونا نلقي نظرة على بعض الأمثلة العملية.

المثال 1: إنشاء شجرة ثنائية

لنفترض أننا نريد إنشاء شجرة ثنائية بالقيم التالية: 10، 5، 15، 3، 7، 13، 18. إليك كيفية القيام بذلك بلغة C:

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;
}

في هذا المثال، نقوم بإنشاء مؤشر إلى جذر الشجرة ثم نستخدم الدالة insertarNodo لإضافة القيم إلى الشجرة.

المثال 2: التنقل بالترتيب في الشجرة الثنائية

لطباعة قيم الشجرة الثنائية بالترتيب يمكننا استدعاء الدالة inOrden كالآتي:

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

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

    return 0;
}

سيقوم هذا المثال بطباعة القيم الموجودة في الشجرة بترتيب تصاعدي.

الأسئلة الشائعة

1. ما هو الفرق بين الشجرة الثنائية وشجرة البحث الثنائية؟

شجرة البحث الثنائية (BST) هي نوع خاص من الشجرة الثنائية حيث يتم ترتيب العناصر بحيث تكون القيم الأصغر على اليسار والقيم الأكبر على اليمين. يتيح هذا إمكانية البحث عن العناصر بكفاءة أكبر مقارنة بالشجرة الثنائية العادية.

2. هل يمكنني الحصول على عقد ذات قيم مكررة في شجرة ثنائية؟

نعم، من الممكن أن يكون هناك عقد ذات قيم مكررة في شجرة ثنائية. ومع ذلك، اعتمادًا على التنفيذ والقواعد المحددة للشجرة الثنائية، قد تكون هناك طرق مختلفة للتعامل مع العقد المكررة. قد تسمح بعض التنفيذات بالتكرارات وتخزينها بأي ترتيب، بينما قد تتطلب التنفيذات الأخرى التعامل مع القيم المكررة بشكل خاص أو التخلص منها.

3. كيف يمكنني إزالة عقدة معينة من شجرة ثنائية؟

لإزالة عقدة معينة من شجرة ثنائية، يجب عليك اتباع الخطوات التالية:

1. ابحث عن العقدة التي تريد حذفها باستخدام بحث الشجرة.
2. خذ بعين الاعتبار حالات الإزالة المختلفة:
   • إذا لم يكن للعقدة أي أبناء، فيمكنك ببساطة حذفها وتحرير ذاكرتها.
   • إذا كانت العقدة تحتوي على طفل واحد فقط، فيمكنك استبدال العقدة بطفلها.
   • إذا كانت العقدة تحتوي على طفلين، فيجب عليك العثور على الخليفة الأقرب (أصغر عقدة في الشجرة الفرعية اليمنى) واستبدال قيمة العقدة التي سيتم حذفها بقيمة الخليفة. ثم قم بإزالة الخليفة من الشجرة.
3. ضبط الروابط والمؤشرات حسب الحاجة للحفاظ على بنية الشجرة الصحيحة.

4. ما هي الشجرة الثنائية الكاملة؟

الشجرة الثنائية الكاملة هي نوع خاص من الشجرة الثنائية حيث يتم ملء جميع المستويات، باستثناء المستوى الأخير ربما، بالكامل، وتقع عقد المستوى الأخير في أقصى اليسار قدر الإمكان. يعني هذا أن جميع العقد لها طفلان، باستثناء العقد الموجودة في المستوى الأخير ربما، والتي قد يكون لها طفل واحد أو لا يوجد لها أطفال.

5. ما هو ارتفاع الشجرة الثنائية؟

ارتفاع الشجرة الثنائية هو طول أطول مسار من الجذر إلى الورقة. بمعنى آخر، هو الحد الأقصى لعدد الحواف بين الجذر وأي ورقة في الشجرة. يتم قياس الارتفاع من حيث عدد المستويات، لذلك فإن الشجرة التي تحتوي على عقدة واحدة فقط يكون ارتفاعها 0، والشجرة الفارغة ليس لها ارتفاع.

6. متى يجب عليّ استخدام شجرة ثنائية في برامجي؟

تعتبر الأشجار الثنائية مفيدة في مجموعة متنوعة من المواقف. تتضمن بعض الحالات الشائعة التي يمكنك فيها استخدام الأشجار الثنائية ما يلي:

• البحث عن العناصر بشكل فعال: إذا كنت بحاجة إلى البحث بسرعة عن العناصر في بنية البيانات، فيمكن أن توفر الشجرة الثنائية وصولاً فعالاً إلى البيانات.
• تمثيل العلاقات الهرمية: تعتبر الأشجار الثنائية مثالية لتمثيل العلاقات الهرمية، مثل بنية الدليل في نظام الملفات.
• فرز البيانات: يمكنك استخدام أشجار البحث الثنائية لفرز البيانات بكفاءة وإجراء عمليات البحث والإدراج والحذف في وقت لوغاريتمي.

تذكر أنه يجب عليك تقييم متطلباتك والنظر في مدى تعقيد العمليات على الأشجار الثنائية قبل أن تقرر استخدامها في برامجك.

اختتام

في هذا الدليل الشامل، استكشفنا المفاهيم الأساسية للأشجار الثنائية في لغة C. وتعلمنا عن بنيتها، وكيفية إدراج العقد وإزالتها، وإجراء عمليات التنقل، والبحث عن العناصر في شجرة ثنائية.

نأمل أن يمنحك هذا الدليل فهمًا قويًا للأشجار الثنائية وكيفية تنفيذها في لغة C. الأشجار الثنائية هي هياكل بيانات متعددة الاستخدامات وقوية يمكنها مساعدتك في حل مجموعة واسعة من المشكلات في البرمجة.

تذكر أن تمارس وتجرب الأمثلة المقدمة لتعزيز فهمك للأشجار الثنائية في لغة C. حظًا سعيدًا في رحلة التعلم والتطوير الخاصة بك!