עצים בינאריים ב-C: מדריך שלם למתחילים

Informatec Digital » אלגוריתמים » עצים בינאריים ב-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);
    }
}

פונקציה זו מבצעת חיפוש רקורסיבי בעץ הבינארי. אם הערך של הצומת הנוכחי שווה לערך המבוקש, הצומת מוחזר. אחרת, תת-עץ השמאלי או הימני מתבצע חיפוש על סמך הערך והתהליך חוזר על עצמו עד שנמצא הערך או הגעה לצומת null.

דוגמאות ליישום עצים בינאריים ב-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. בהצלחה במסע הלמידה והפיתוח של תוכנה!