אני לומד #c והגעתי לקטע של עצים בינאריים ולא ממש הצחלתי להבין איך כותבים אותם ואיך מחפשים בהם אשמח אם משהו יוכל להסביר לי את הרעיון של העצים.

תודה.

נ.ב. אני לא יודע אם זה המקום הנכון - אז אם לא, אשמח אם יעבירו אתה זה למקום הנכון.

באיזו מסגרת אתה לומד, ומה למדתם עד כה?

אני לומד את זה לבד, בעזרת ספר שנקרא סדנת לימד 3.0 #visual c של מייקרוסופט.

ולמדתי די הרבה אני לו חושב שאני יכול לכתוב את כל החומר הזה.

אולי זה יעזור- הגעתי עד פרק 17 מתוך 19 השאר כבר על ישומי windows forms)windows, תפריטים ותיבות דו שיח, בדיקת תקינות) ניהול נתונים, בניית ישומי WEB, מבוא LINQ' ואז LINQ TOSQL וLINQ TO XML.

תודה

אין לי את הספר אז אני לא יודע עד כמה נכנסים בו לעומק להגדרה של עץ בינארי, אבל אתה יכול לנסות לקרוא בויקיפדיה כדי להבין מה זה ברמה התיאורטית:

http://he.wikipedia.org/wiki/%D7%A2%D7%A5_%D7%91%D7%99%D7%A0%D7%90%D7%A8%D7%99

הרעיון הכללי הוא להגדיר מחלקה שתייצג צומת/קודקוד. למחלקה הזו יש שני שדות - בן ימני ובן שמאלי, גם הם מאותו טיפוס של המחלקה (כלומר אם למחלקה שלך קוראים Node אז יהיו לה שני שדות מטיפוס Node גם כן).

עץ זה פשוט אוסף של צמתים כאלה שמחוברים ככה שכל צומת הוא בן של צומת אחר (לא לכל צומת חייבים להיות בן ימני ושמאלי - הם יכולים להיות null), פרט לצומת אחד שאין לו "אבא" - צומת זה נקרא השורש של העץ. לעיתים נהוג גם להגדיר טיפוס מיוחד עבור העץ עצמו, כלומר מגדירים מחלקה Tree שיש לו שדה אחד מטיפוס Node, המצביע לשורש העץ.

וכמובן חוץ מהבנים יש לכל צומת גם איזשהו Data

כמו שהבנתי עץ בינארי היא מחלקה שמסודרת בצורת עץ, זאת אומרת שיש תא שמחוברים אליו שני תאים,

ואל כ"א מהתאים או שמחוברים שני תאים או שלא מחובר אף תא וכן הלאה, ואם מסדרים בעץ הזה נתונים

בצורה הנכונה מאוד קל לעשות בו חיפוש.

השאלה היא איך בונים אותו בצורה כזאת הרי סתם כך מחלקה זה אוסף של תאים, אז איך בונים את זה בצורה הזאת?

לעץ בינארי רגיל אין איזשהו מבנה מיוחד - לכל צומת יש שני בנים וזהו.

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

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

הבנתי ,תודה רבה.

תוכל אולי להביא לי דוגמא בקוד כדי שאני אוכל גם לראות את התהליך?

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

bool find_in_tree(TreeNode node, int x) {
  while (node != null) {
    if (node.data == x) 
       return true;
    else if (node.data < x)
       node = node.right_son;
    else
       node = node.left_son;
  }
  return false
}

או לחילופין, ברקורסיה:

bool find_in_tree(TreeNode node, int x) {
  if (node == null)
     return false;
  else if (node.data == x)
     return true;
  else if (node.data < x)
     return find_in_tree(node.right_son, x);
  else
    return find_in_tree(node.left_son, x);
}

תודה, אבל נראה לי שזה יעבוד רק בעץ שעשוי מאב ושני בנים שאז אפשר לשלוח אותו לבן שנקרא right_son/left_son אבל איך אני שולח אותו לבנים שלהם?

מה? לא הבנתי את השאלה. הבנים (right_son ו-left_son) הם שדות מטיפוס TreeNode גם כן.

עד כמה שהבנתי החיפוש יהיה רק באב ובשני הבנים אבל אם יש "עץ"שלם שבו כל בן הוא ג"כ אב איך אני עושה שהחיפוש יעבור על כולם.

אתה רץ בלולאה \ רקורסיה עד שלצומת הנוכחית אין בנים או עד שמצאת.

עד כמה שהבנתי החיפוש יהיה רק באב ובשני הבנים אבל אם יש "עץ"שלם שבו כל בן הוא ג"כ אב איך אני עושה שהחיפוש יעבור על כולם.

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

מממ... נראה לי שפיספסתי משהו.

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

בשביל לבנות עץ אני צריך ליצור מחלקה חדשה, נקרא לה נגיד TreeNode, אחר כך אני יוצר משתנה/אובייקט שהוא בעצם האב,

עכשיו, איך אני יוצר את ה"בנים" שלו ומקשר אותם אליו?

תודה