בקשה עצים בינריים במבני נתונים

[sac]

יש לי כל מיני שאלות על העצים בינריים ואני לא כ'כ מצילחה לפתור אותם

 

[sac]

למשהי יש פוקציה בג'אוה שבונה עץ בינרי?

 

[שלמה וייס]

יש לי כל מיני שאלות על העצים בינריים ואני לא כ'כ מצילחה לפתור אותם

מה השאלות?

 

[sac]

לדוגמא: כתבי פונקציה המקבלת עץ בינארי של מספרים שלמים ומספר שלם x ומחזירה true אם יש בעץ מסלול מהשורש עד אחד העלים שלאורך כל המסלול ערך הצמתים הוא x ו false אם לא.
איך אני יודעת איך להסתכל על כזה תרגיל?

 

[שלמה וייס]

דווקא בג'אווה?
בעיקרון זה נשמע רקורסיה
מתחילים מהשורש, ושולחים את שני העלים לפונקציה.
בתכנית שכתבתי הנחתי שהעץ מורכב מצמתים שלהם יש את הערך value left right.

public class Main
{
    public static boolean isSame(Node x, double i)
    {
        if (x == null)
           {
                return true;
           }
        if (x.value != i)
            {
                return false;
            }
        return (isSame(x.left, i) || isSame(x.right, i))  
               
           
    }
    public static void main(String[] args) {
        System.out.println(isSame(root, someNumber));
    }
}

 

[sac]

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

 

[שלמה וייס]

קצת הסבר:
מתחילים מהשורש (במיין), ובודקים התאמה למספר הנתון.
אם אין התאמה, מחזירים false.
אם יש התאמה, בודקים האם לפחות אחד מהילדים יחזיר true.
החזרת true קוראת שמגיעים לצומת null - סוף הענף.

 

[sac]

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

 

[שלמה וייס]

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

עץ בינארי או עץ חיפוש בינארי?

 

[sac]

עץ בינארי או עץ חיפוש בינארי?

עץ בינארי

 

[שלמה וייס]

עץ בינארי

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

 

[#1]

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

 

[sac]

public static void tree(BinNode<Integer> t)
{
if(t==null)
return;
tree1(t.getLeft());
tree1(t.getRight());
if(t.getVal()<0)
System.out.println(t.getVal());
}זה קוד תקין?

 

[#1]

public static void tree(BinNode<Integer> t)
{
if(t==null)
return;
tree1(t.getLeft());
tree1(t.getRight());
if(t.getVal()<0)
System.out.println(t.getVal());
}זה קוד תקין?

נכון

 

[sac]

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

 

[שלמה וייס]

תעלו בתוך לשונית של קוד

 

[sac]

צפה בקובץ המצורף 1484966
תעלו בתוך לשונית של קוד

מה?

 

[#1]

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

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

 

[sac]

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

public<T> void printLeft()
{
if(val==null)
return;
if(left==null)
return;
System.out.println(left.val);
printLeft();
} מה הבעיה בזה?

 

[#1]

בסוף את לא צריכה לקרוא לprintLeft();
אלא לleft.printLeft();
right.printLeft();
אחרת את קוראת שוב ושוב לפונקציה עם השורש