עצים בינאריים ב#c

[שניצל]

TreeNode זו מחלקה שמייצגת צומת בעץ. יש לה שלושה שדות - ה-data שמייצג את המידע שבצומת (נניח מטיפוס int, אבל יכול להיות כל דבר), ושני בנים - left_son ו-right_son שהם גם צמתים - כלומר מטיפוס TreeNode.

איך בונים אותם? פשוט יוצרים את כל האובייקטים שצריך ומקשרים ביניהם ע"י השמה פשוטה... אם יצרת אבא x ובן y ואתה רוצה לקשר ביניהם אז תעשה לדוגמה x.left_son = y.

[eido300]

TreeNode זו מחלקה שמייצגת צומת בעץ. יש לה שלושה שדות - ה-data שמייצג את המידע שבצומת (נניח מטיפוס int, אבל יכול להיות כל דבר), ושני בנים - left_son ו-right_son שהם גם צמתים - כלומר מטיפוס TreeNode.

איך בונים אותם? פשוט יוצרים את כל האובייקטים שצריך ומקשרים ביניהם ע"י השמה פשוטה... אם יצרת אבא x ובן y ואתה רוצה לקשר ביניהם אז תעשה לדוגמה x.left_son = y.

נראה לי שסוף סוף הבנתי.

אם לדוגמא יש לי 10 מספרים שאני צריך להכניס, אז אני אמור לבנות 10 אובייקטים מהמחלקה, לשים בכל אובייקט מספר ולחבר כל אחד מהאובייקטים לאובייקט אחר בהתאמה של מקום=מספר?

תודה רבה על התשובה המהירה.

[שניצל]

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

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

[eido300]

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

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

ואם הבנתי נכון הקוד אמור להראות כך:

ככה בונים מחלקת עץ:

[LEFT]
class TreeNode
{
int data;
TreeNode left;
TreeNode right;
}[/LEFT]

וככה בונים את העץ עצמו:

[LEFT]TreeNode a=new TreeNode();
TreeNode b=new TreeNode();
TreeNode c=new TreeNode();
a.data=0;
b.data=1;
c.data=2;
b.left=a;
b.right=c;
[/LEFT]

נכון?

תודה.

[שניצל]

[Gil28]

בערך. רק חבל לבזבז משתנים נוספים.

TreeNode root = new TreeNode();
root.left = new TreeNode();
root.right = new TreeNode();

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

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

בכל בן איך שהוא רוצה.

[eido300]

בערך. רק חבל לבזבז משתנים נוספים.

קוד:

TreeNode root = new TreeNode();

root.left = new TreeNode();

root.right = new TreeNode();

לא ממש הבנתי מה עשית בפקודה הזאת? יצרת אובייקט root, ומה הגדת בתור left וright?

תודה רבה לכולם.

[Gil28]

הבן הימני הוא אובייקט TreeNode חדש וכך גם השמאלי.

זאת בהנחה וקיים בנאי ריק (שלא מקבל פרמטרים).

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

כך בערך זה אמור להיות:

class Node
{
    int data;
    Node right;
    Node left;

    public Node(int value)
    {
        data = value;
    }
}

class SearchTree
{
    Node root;

    public SearchTree()
    {
        root == null או כל דבר אחר...
    }

    public add(int value)
    }
        if root = null
        {
            root = new Node(value);
        }
        else
        {
            כאן תבוצע בדיקה של האם value גדול מהשורש או לא ובהתאם ללכת ימינה או שמאלה.
            ממשיכים ללכת ימינה ושמאלה עד הערך של הבן הימני (או השמאלי) הוא אינו Node כלשהו אלא null ושם יוצרים Node חדש.
        {
    {

    עוד מתודות...
{

[שניצל]

לא ממש הבנתי מה עשית בפקודה הזאת? יצרת אובייקט root, ומה הגדת בתור left וright?

תודה רבה לכולם.

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

[eido300]

את הפקודות הבנתי (אני חושב)

הבנתי שהוא יצר אובייקט חדש שנקרא root, ולשדה שנקרא left/right הוא עשה השמה תוך כדי שהוא יוצר אובייקט חדש,

אבל לאובייקט החדש אין שם אז איך אני אמור לשים בו משהו? או לקרוא לו?

אני מאמין שפיספסתי משהו אז אשמח אם תגידו לי מה פיספסתי.

[Gil28]

כמו רשימה מקושרת, לא לכל איבר יש שם, רק לראש (שורש).

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

[שניצל]

כמו בת'רד האחר שבו דיברנו, אתה שוב צריך להפריד בין משתנה ואובייקט.

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

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

[eido300]

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

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

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

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

נכון, אבל אני חשבתי שחייב להיות לאובייקטים האלה שם אחרת איך ישתמשו בהם? ומתברר שיש מה שנקרא רשימה מקושרת ששם לא צריך, לכן טעיתי.

בכל אופן תודה רבה לכולם.

[Gil28]

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

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

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

[eido300]

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

ומה זה adt?