الأشجار والرسوم البيانية في C

الأشجار والرسوم البيانية بنيتا بيانات غير خطيتين تُستخدمان لتمثيل البيانات الهرمية وبيانات الشبكات.

في هذا الدرس، ستتعلمون:

• كيفية تنظيم الأشجار والرسوم البيانية.
• كيفية تنفيذ شجرة ثنائية في C.
• كيفية تمثيل الرسوم البيانية باستخدام قوائم التجاور والمصفوفات.

ما هي الشجرة؟

الشجرة هي بنية بيانات هرمية تتكوّن من عقد.

المصطلحات الأساسية:

• الجذر - العقدة العلوية.
• الأب والابن - عقد متصلة مباشرةً.
• الورقة - عقدة ليس لها أبناء.

مثال: عقدة في شجرة ثنائية

في C، تُعرَّف عقدة الشجرة الثنائية باستخدام struct مع مؤشرين إلى الابن الأيسر والابن الأيمن.

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

اجتياز الشجرة الثنائية

طرق الاجتياز:

• الاجتياز الوسطي (LNR) - الأيسر، العقدة، الأيمن.
• الاجتياز القبلي (NLR) - العقدة، الأيسر، الأيمن.
• الاجتياز البعدي (LRN) - الأيسر، الأيمن، العقدة.

مثال: الاجتياز الوسطي

ينفّذ هذا البرنامج اجتيازًا وسطيًا لشجرة ثنائية.

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

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

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

ما هو الرسم البياني؟

الرسم البياني هو مجموعة من العقد (الرؤوس) المتصلة بالحواف.

يمكن أن تكون الرسوم البيانية:

• موجّهة - للحواف اتجاه.
• غير موجّهة - ليس للحواف اتجاه.

تمثيل الرسم البياني

يمكن تمثيل الرسوم البيانية باستخدام:

• مصفوفة التجاور - مصفوفة ثنائية الأبعاد تمثّل الاتصالات.
• قائمة التجاور - قائمة تشير فيها كل عقدة إلى جيرانها.

اجتياز الرسم البياني

طرق الاجتياز الشائعة:

• البحث بعرض أول (BFS) - يزور جميع الجيران قبل الانتقال إلى مستوى أعمق.
• البحث بعمق أول (DFS) - يستكشف المسار بأقصى عمق ممكن قبل التراجع.

الملخص

في هذا الدرس، تعلّمت:

• كيفية تنظيم الأشجار والرسوم البيانية.
• كيفية تنفيذ اجتيازات الأشجار.
• كيفية تمثيل الرسوم البيانية واجتيازها.

وبهذا نختتم قسم هياكل البيانات في C!