עץ בינארי ב-C
ב-C, א עץ בינארי הוא מופע של מבנה נתוני עץ עם צומת אב שעשוי להחזיק במספר מקסימלי של שני צמתים צאצאים; 0, 1 או 2 צמתים צאצאים. כל צומת בודד ב-a עץ בינארי יש ערך משלו ושני מצביעים לילדיו, מצביע אחד לילד השמאלי והשני לילד הימני.
הכרזה על עץ בינארי
א עץ בינארי ניתן להכריז ב-C באמצעות אובייקט שנקרא struct שמתאר את אחד הצמתים בעץ.
struct צוֹמֶת {
סוג נתונים var_name ;
struct צוֹמֶת * שמאלה ;
struct צוֹמֶת * ימין ;
} ;
למעלה הצהרה של אחד עץ בינארי שם הצומת כצומת. הוא מחזיק בשלושה ערכים; האחד הוא משתנה אחסון הנתונים והשניים האחרים הם המצביעים לילד. (ילד משמאל וימין של צומת האב).
עובדות של עץ בינארי
אפילו עבור קבוצות גדולות של נתונים, באמצעות א עץ בינארי עושה את החיפוש קל ומהיר יותר. מספר ענפי העצים אינו מוגבל. בניגוד למערך, ניתן ליצור עצים מכל סוג ולהגדיל בהתאם למה שנדרש מאדם.
יישום עץ בינארי ב-C
להלן מדריך שלב אחר שלב ליישום א עץ בינארי ב-C.
שלב 1: הכרז על עץ חיפוש בינארי
צור צומת struct שיש לו שלושה סוגי נתונים, כגון נתונים, *left_child ו-*right_child, כאשר הנתונים יכולים להיות מסוג מספר שלם, וניתן להכריז על שני צמתים *left_child ו-*right_child כ-NULL או לא.
struct צוֹמֶת{
int נתונים ;
struct צוֹמֶת * ילד נכון ;
struct צוֹמֶת * ילד_שמאלי ;
} ;
שלב 2: צור צמתים חדשים בעץ החיפוש הבינארי
צור צומת חדש על ידי יצירת פונקציה שמקבלת מספר שלם כארגומנט ומספקת את המצביע לצומת החדש שנוצר עם הערך הזה. השתמש בפונקציה malloc() ב-C להקצאת זיכרון דינמית עבור הצומת שנוצר. אתחל את הילד השמאלי והימני ל-NULL והחזר את ה-nodeName.
struct צוֹמֶת * לִיצוֹר ( נתוני סוג נתונים )
{
struct צוֹמֶת * nodeName = malloc ( מידה של ( struct צוֹמֶת ) ) ;
nodeName -> נתונים = ערך ;
nodeName -> ילד_שמאל = nodeName -> ילד נכון = ריק ;
לַחֲזוֹר nodeName ;
}
שלב 3: הכנס ילדים ימני ושמאלי בעץ בינארי
צור פונקציות insert_left ו- insert_right שיקבלו שתי כניסות, שהן הערך שיוכנס והמצביע לצומת אליו יחוברו שני הילדים. קרא לפונקציה create כדי ליצור צומת חדש ולהקצות את המצביע המוחזר למצביע השמאלי של הילד השמאלי או המצביע הימני של הילד הימני של האב השורש.
מבנה צוֹמֶת * insert_left ( מבנה צוֹמֶת * שורש , נתוני סוג נתונים ) {שורש -> שמאלה = לִיצוֹר ( נתונים ) ;
לַחֲזוֹר שורש -> שמאלה ;
}
struct צוֹמֶת * insert_right ( struct צוֹמֶת * שורש , נתוני סוג נתונים ) {
שורש -> ימין = לִיצוֹר ( נתונים ) ;
לַחֲזוֹר שורש -> ימין ;
}
שלב 4: הצג צמתים של עץ בינארי באמצעות שיטות מעבר
אנו יכולים להציג עצים באמצעות שלוש שיטות חצייה ב-C. שיטות חצייה אלו הן:
1: מעבר בהזמנה מראש
בשיטת מעבר זו נעבור דרך הצמתים בכיוון מ parent_node->left_child->right_child .
בָּטֵל הזמנה מראש ( צוֹמֶת * שורש ) {אם ( שורש ) {
printf ( '%d \n ' , שורש -> נתונים ) ;
display_pre_order ( שורש -> שמאלה ) ;
display_pre_order ( שורש -> ימין ) ;
}
}
2: מעבר לאחר הזמנה
בשיטת מעבר זו, נעבור דרך הצמתים בכיוון מה- left_child->right_child->הורה_צומת-> .
בָּטֵל display_post_order ( צוֹמֶת * שורש ) {אם ( עץ_בינארי ) {
display_post_order ( שורש -> שמאלה ) ;
display_post_order ( שורש -> ימין ) ;
printf ( '%d \n ' , שורש -> נתונים ) ;
}
}
3: מעבר בהזמנה
בשיטת מעבר זו נעבור דרך הצמתים בכיוון מ left_node->root_child->right_child .
בָּטֵל display_in_order ( צוֹמֶת * שורש ) {אם ( עץ_בינארי ) {
display_in_order ( שורש -> שמאלה ) ;
printf ( '%d \n ' , שורש -> נתונים ) ;
display_in_order ( שורש -> ימין ) ;
}
}
שלב 5: בצע מחיקה בעץ בינארי
אנחנו יכולים למחוק את היצירה עץ בינארי על ידי מחיקת שני הילדים עם פונקציית צומת האב ב-C באופן הבא.
בָּטֵל delete_t ( צוֹמֶת * שורש ) {אם ( שורש ) {
delete_t ( שורש -> שמאלה ) ;
delete_t ( שורש -> ימין ) ;
חינם ( שורש ) ;
}
}
תוכנית C של עץ חיפוש בינארי
להלן היישום המלא של עץ החיפוש הבינארי בתכנות C:
#include#include
מבנה צוֹמֶת {
int ערך ;
מבנה צוֹמֶת * שמאלה , * ימין ;
} ;
מבנה צוֹמֶת * צומת 1 ( int נתונים ) {
מבנה צוֹמֶת * tmp = ( מבנה צוֹמֶת * ) malloc ( מידה של ( מבנה צוֹמֶת ) ) ;
tmp -> ערך = נתונים ;
tmp -> שמאלה = tmp -> ימין = ריק ;
לַחֲזוֹר tmp ;
}
בָּטֵל הדפס ( מבנה צוֹמֶת * root_node ) // מציג את הצמתים!
{
אם ( root_node != ריק ) {
הדפס ( root_node -> שמאלה ) ;
printf ( '%d \n ' , root_node -> ערך ) ;
הדפס ( root_node -> ימין ) ;
}
}
מבנה צוֹמֶת * insert_node ( מבנה צוֹמֶת * צוֹמֶת , int נתונים ) // הכנסת צמתים!
{
אם ( צוֹמֶת == ריק ) לַחֲזוֹר צומת 1 ( נתונים ) ;
אם ( נתונים < צוֹמֶת -> ערך ) {
צוֹמֶת -> שמאלה = insert_node ( צוֹמֶת -> שמאלה , נתונים ) ;
} אַחֵר אם ( נתונים > צוֹמֶת -> ערך ) {
צוֹמֶת -> ימין = insert_node ( צוֹמֶת -> ימין , נתונים ) ;
}
לַחֲזוֹר צוֹמֶת ;
}
int רָאשִׁי ( ) {
printf ( 'יישום C של עץ חיפוש בינארי! \n \n ' ) ;
struct צוֹמֶת * הוֹרֶה = ריק ;
הוֹרֶה = insert_node ( הוֹרֶה , 10 ) ;
insert_node ( הוֹרֶה , 4 ) ;
insert_node ( הוֹרֶה , 66 ) ;
insert_node ( הוֹרֶה , ארבע חמש ) ;
insert_node ( הוֹרֶה , 9 ) ;
insert_node ( הוֹרֶה , 7 ) ;
הדפס ( הוֹרֶה ) ;
לַחֲזוֹר 0 ;
}
בקוד לעיל, אנו מכריזים תחילה על א צוֹמֶת באמצעות struct . לאחר מכן אנו מאתחלים צומת חדש בתור ' צומת 1 ' ולהקצות זיכרון באופן דינמי באמצעות malloc() ב-C עם נתונים ושני מצביעים הקלידו ילדים באמצעות הצומת המוצהר. לאחר מכן, אנו מציגים את הצומת לפי printf() פונקציה וקוראים לה ב- רָאשִׁי() פוּנקצִיָה. אז ה insertion_node() נוצרת פונקציה, כאשר אם נתוני הצומת הם NULL אז צומת 1 יצא לפנסיה, אחרת הנתונים ממוקמים ב- צוֹמֶת (הורה) של הילד השמאלי והימני. התוכנית מתחילה להפעיל מה- רָאשִׁי() פונקציה, אשר יוצרת צומת באמצעות מספר צמתים לדוגמה בתור ילדים ולאחר מכן משתמשת בשיטות מעבר לפי סדר כדי להדפיס את תוכן הצומת.
תְפוּקָה
סיכום
עצים משמשים לעתים קרובות כדי לשמור נתונים בצורה לא ליניארית. עצים בינאריים הם סוגי עצים שבהם לכל צומת (הורה) יש שני צאצאים, הילד השמאלי והילד הימני. א עץ בינארי היא שיטה רב-תכליתית להעברה ואחסון נתונים. זה יעיל יותר בהשוואה ל-Linked-List ב-C. במאמר לעיל, ראינו את הרעיון של עץ בינארי עם יישום שלב אחר שלב של א עץ חיפוש בינארי ב-C.