יום שבת, 26 באפריל 2014

חומר עזר עצים בינאריים בשפה סי שארפ (C#) מה שצריך לדעת על עצים בינאריים, תנאי עצירה, דרכי חשיבה, שאלות עם פתרונות

חומר עזר עצים בינאריים בשפה סי שארפ (C#) מה שצריך לדעת על עצים בינאריים, תנאי עצירה, דרכי חשיבה, שאלות עם פתרונות 




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


תבניות
מותאם לסביבות  JAVA ,C#


כתיבה ועריכה:
רחל לודמר
זיוה קונצמן
שירלי רוזנברג-כהן

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

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

מכיון שרוב האלגוריתמים הם רקורסיביים, גם המבנה הכללי הוא תבנית רקורסיבית.
המבנה הכללי – לכל פעולה 3 חלקים:
    • תנאי עצירה
    • טיפול בצומת
    • קריאות רקורסיביות  – המשך המעבר מהצומת לצאצאים שלה.

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

חלוקת העצים לתבניות בסיסיות:

                    

פעולות מבצעות:

Text Box: דוגמה 1: 	
פעולה המקבלת עץ בינארי ומעדכנת את ערכי הצמתים הזוגיים לחצי מערכם. 
המאפיין – פעולות שאינן מחזירות דבר. פעולות שעוברות על העץ ומטפלות בצמתים, ז.א. מעדכנות משהו בצמתי העץ, או רק בצמתים מסויימים, מדפיסות , מוסיפות משהו וכו'.

              לפני:                                                                             אחרי:
 







התבנית:
·           תנאי עצירה:  אם אין צומת – אין לעשות דבר. ומכיוון שזו פעולה שמחזירה void – נכנסים לפעולה רק אם יש צומת, כלומראם  t != null. הפעולה תעצור כאשר  t = null.
·            טיפול בצומת:  אם הצומת מקיים את  התנאי– מעדכנים, מדפיסים וכו' לפי המשימה בשאלה.
·            רקורסיה שמאלה
·            רקורסיה ימינה

הפתרון:
    public static void Update(BinTreeNode<int> t)
    {  
               if (t != null)
            {     if (t.GetInfo() % 2 == 0)
                         t.SetInfo(t.GetInfo() /2);
                    Update(t.GetLeft());
                 Update(t.GetRight());
            }
   }

Text Box: דוגמה 2: 	
פעולה המקבלת עץ בינארי ומוסיפה אח לכל צומת שהוא בן יחיד. ערך האח יהיה 0.
התבנית:
* הפעולה עובדת דרך האב. משתמשת בפעולת עזר.
·           תנאי עצירה:  אם האב הוא עלה אין צורך לעשות דבר.
·            טיפול בצומת:  אם לצומת רק בן ימני – מוסיפים בן שמאלי, אם לצומת רק בן שמאלי – מוסיפים בן ימני. (אם יש לו שני בנים לא עושים דבר – הרקורסיה ממשיכה). אין  צורך לטפל בהגעה לnull כיוון שבמצב של בן יחיד מתווסף צומת שהוא עלה ואז הוא ייעצר בתנאי העצירה – עלה.
·            רקורסיה שמאלה
·            רקורסיה ימינה
פעולת עזר שימושית במיוחד:
פעולה המקבלת צומת ומחזירה קוד המציין מספר הבנים: 0 – אם הוא עלה, 1 – אם יש רק בן שמאלי, 2 – אם יש רק בן ימני, 3 – אם יש שני בנים.
שים ©: הפעולה אינה רקורסיבית, עובדת על צומת בודד.
public static int ChildKod (BinTreeNode<int> t)
{      if (t.GetLeft() == t.GetRight() )  return 0;
מכיון שמדובר בהפניות, הערכים זהים רק כאשר שניהם null  //      
        if (t.GetLeft() != null && t.GetRight != null )    return 3;
        if (t.GetLeft() !=  null )   return 1;
        return 2;
}
פתרון:
public static void AddBro(BinTreeNode<int> t )
{          int ck = ChildKod(t);
            if (ck != 0 )
            {          if ( ck == 1)
                                    t.SetLeft(new BinTreeNode<int>(0));
                        if (ck == 2)
                                    t.SetRight(new BinTreeNode<int>(0));
                        AddBro(t.GetLeft());
                        AddBro(t.GetRight());
            }
}
פעולות מחזירות ערך:

Text Box: דוגמה 3:  
פעולה המחזירה את מספר הצמתים בעץ שיש להם תוכן זוגי.



התבנית:
·         תנאי עצירה: – אם t=null  - החזר 0. אין צומת, אין מה לבדוק ובוודאי שאין מה לספור.
·         טיפול בצומת:  אם ערך הצומת זוגי (מקיים את תנאי השאלה) – החזר
                                          1+ רקורסיה שמאלה + רקורסיה ימינה. (סופרים את הצומת).
·         אם הצומת לא מקיים את התנאי – לא סופרים אותו , אך ממשיכים  לצאצאים. ז.א.
       החזר  רקורסיה שמאלה + רקורסיה ימינה.

הפתרון:
public static int NumInfoZugi(BinTreeNode<int> t)
{  if (t == null)   return 0;
   if (t.GetInfo() % 2 == 0)
         return 1 + NumInfoZugi(t.GetLeft())+ NumInfoZugi(t.GetRight());// הוספת 1 לסכום
   return NumInfoZugi(t.GetLeft()) + NumInfoZugi(t.GetRight());
}
Text Box: דוגמה 4: 
הפעולה מקבלת עץ בינארי ומחזירה את סכום ערכי הצמתים שהם בנים ימניים.
התבנית:
* הפעולה עובדת דרך האב.
·         תנאי עצירה: – אם t=null  - החזר 0. אין צומת, אין מה לבדוק ובוודאי שאין מה לסכם.
·         טיפול בצומת:  אם יש לצומת בן ימני – החזר
                                 ערך הבן הימני+  רקורסיה שמאלה + רקורסיה ימינה.
·         אם אין בן ימני  החזר  רקורסיה שמאלה.


פתרון:
public static int SumRightChild(BinTreeNode<int> t)
{          if (t == null ) return 0;
            if (t.GetRight() != null )
                        return t.GetRight().GetInfo() + SumRightChild(t.GetLeft()) +                                                                                                                     SumRightChild(t.GetRight);
            return SumRightChild(t.GetLeft());
Text Box: דוגמה 5: 
פעולה המקבלת עץ בינארי ומספר שהוא ערך צומת בעץ, ומחזירה הפניה לאביו בעץ. אם המספר אינו נמצא בעץ – יוחזר null	
הנחה: הערכים בעץ שונים זה מזה.
}
           
תבנית:
·         תנאי עצירה – הגענו ל null – פירושו שהמספר לא נמצא בשלב זה – יוחזר null
·         אם הגענו לצומת שאחד הבנים שלה  ערכו x , תוחזר ההפניה לצומת.
·         נחפש את צומת האב בענף השמאלי. אם נמצא שם – תוחזר ההפניה לאב. אם לא נמצא – נחפש בענף הימני והתוצאה שלו תוחזר.

public static BinTreeNode<int> Aba(BinTreeNode<int> bt,  int  x)
{
            if (bt == null)   
                                                 return null;
            if (bt.GetRight() != null && bt.GetRight()== x)
                                    return bt;
            if (bt.GetLeft() != null && bt.GetLeft()== x)
                                    return bt;
              BinTreeNode<int> temp = Aba(bt.GetLeft(), x)
            if (temp == null)
                                                return Aba(bt.GetRight(), x);
            return temp;
}


פעולות המחזירות ערך בוליאני:

Text Box: דוגמה 6 : 
פעולה המקבלת עץ ותו ומחזירה 'אמת' אם התו נמצא בעץ ו'שקר' אחרת.
"האם יש"

התבנית:
·         תנאי עצירה –אם t=null  - החזר 'שקר'. אם הגענו לnull  סימן שלא מצאנו עדיין את מה שחיפשנו, כי אם היינו מוצאים כבר היינו מפסיקים לפני ה- null  ומחזירים 'אמת'
·         טיפול בצומת – אם הצומת מקיים את התנאי של השאלה – החזר 'אמת',  מצאנו.
      אם הצומת אינו מקיים את התנאי של השאלה – נמשיך לחפש באחד הצאצאים שלה – לא חובה שנמצא בשניהם.
·         החזר רקורסיה שמאלה או רקורסיה ימינה.

הפתרון:
public static bool IsInTree(BinTreeNode<char> t, char  x)
 {         if (t == null)   
                        return false;
            if (t.GetInfo() == x)   
                        return true;
            return IsInTRee(t.GetLeft(),x) || IsInTRee(t.GetRight(),x);
 }
Text Box:         דוגמה 7:
 פעולה המחזירה 'אמת' אם כל צמתי העץ תוכנם זוגי ו'שקר' אחרת.
"האם כל"

 התבנית:
·         תנאי עצירה - אם t=null  - החזר 'אמת' . אם הגענו לnull  פירושו שלא "עפנו" בדרך עם  ,false על ידיע  צומת שלא מקיים את התנאי.
·         טיפול בצומת – אם הצומת לא מקיים את התנאי– החזר 'שקר'. אין מה להמשיך בעץ, מספיק שצומת אחת מפר את התנאים .
·         אם הצומת מקיים את התנאי, עדיין צריך לבדוק את צאצאיה –
            החזר רקורסיה שמאלה וגם רקורסיה ימינה.
                                                                                                                                   
הפתרון:
public static bool AllZugi(BinTreeNode<int> t)
{          if (t == null)
                         return true;
            if (t.GetInfo()%2!=0)
                        return false;
            return AllZugi(t.GetLeft()) && AllZugi(t.GetRight());
 }


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

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

תבנית:
·         תנאי עצירה – אם עלה יחזיר 'אמת'.
·         טיפול בצומת – אם קיים בן יחיד – יחזיר שקר.
·         אם ערכי הצומת ובניו אינם עונים על התנאים – נחזיר שקר.
·         רקורסיה שמאלה וגם רקורסיה ימינה.


פתרון:
public static bool Hilkiyahoo(BinTreeNode<Integer> t)
{          int sons = ChildKod(t);
            if (sons == 0)   return true; // עלה
            if (sons <3)   return false; //בן יחיד
            if ((t.getLeft().getInfo() %  t.getRight().getInfo() != 0) ||
               t.getLeft().getInfo() / t.getRight().getInfo() != t.getInfo())
                                    return false;
            return Hilkiyahoo(t.getLeft() && Hilkiyahoo(t.getRight());
}
Text Box: דוגמה 9: 
כתוב פעולה המקבלת עץ בינארי ומחזירה את "סכום השרשרת המקסימלי". 
שרשרת היא מסלול מהשורש עד עלה. הפעולה תחזיר את הסכום של השרשרת המקסימלית.
 

דוגמא:

אם  T הוא העץ הנתון, אז יוחזר  31
6+5+7+8+3+2 =31 ( לעומת 6+5+7+10=28)

Oval: 8ועבור העץ 
יוחזר 8.



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

פתרון:
public static int maxSharsheret(BinTreeNode<Integer> bt)
  {    
         int k=ChildKod(bt);
        if (k==0)
           return bt.getInfo();
         //  יש לו רק בן שמאלי
        if (k==1)
                return bt.getInfo()+maxSharsheret(bt.getLeft());
         //יש לו רק בן ימני
         if (k==2 )
                return bt.getInfo()+maxSharsheret(bt.getRight());  
          // יש לו שני בנים
              return  bt.getInfo()+Math.max(maxSharsheret(bt.getLeft()),    
                                                                                        maxSharsheret(bt.getRight()));  
        }
Text Box: דוגמה 10:
פעולה המקבלת עץ בינארי של תווים ,ומחזירה רשימה של עצמים מטיפוס Pair. 
אין חשיבות לסדר התווים ברשימה, אך כל תו לא יופיע  יותר מפעם אחת.
Pair
תכונות	private char tav // תו המופיע בעץ
private int num // מספר הופעותיו בעץ
פעולות	הנח קיום פעולות בונות ומאחזרות

ניתוח הפתרון:
נצטרך מחלקה עבור העצמים שהם איברי הרשימה.
נצטרך פעולה עוטפת – בה תאותחל הרשימה.
נצטרך פעולה הבודקת שהאיבר (התו) אינו מופיע כבר ברשימה. existInList
פעולה הסופרת את מס ההופעות של התו x בעץ. (לפי דוגמה 4 כאן) numTav


פתרון ב-java:
Public static boolean existInList( List<Pair> lst, char tav)
{          Node<Pair> pos= lst.getFirst();
            while(pos!=null)
            {    if (pos.getInfo().getTav()==tav)
                        return true;
                  pos=pos.getNext();
          }
          return false;
 }
public static void update(BinTreeNode<Integer> t, List<Pair> lst)
{          if (t!=null)
            {          if (!existInList(lst,t.getInfo())
                        {          int num= numTav(t, t.getInfo());  // פעולת עזר בדוגמה 4
                        lst.insert(null, new Pair(t.getInfo(), num);
                         }
                        update(t.getLeft(),lst);  
                        update(t.getRight(),lst);
            }
}
public static List<Pair> update(BinTreeNode<Integer> t)
{// פעולה עוטפת
            List<Pair> lst = new List<Pair>();
            update(t, lst);
            return lst;
}
Text Box: דוגמה 11: 
עץ בינארי שאיבריו מטיפוס Pair ,ייקרא "תו_ועוד" , אם בכל אחד מהצמתים שלו מתקיים:
הערך המספרי num שבצומת, הוא מספר ההופעות של  האות tav בכל הצאצאים שלו, וגם האות tav שבצומת גדולה או שווה מערכי האותיות של הצאצאים שלו.
כתוב פעולה המקבלת עץ בינרי  bt מטיפוס InfoTree, ומחזירה 'אמת' אם הוא מסוג "תו_ועוד" ו'שקר' אחרת.

ברעיון דומה אפשר ליצור את השאלה הבאה:

דוגמא לעץ "תו_ועוד":








ניתוח הפתרון:
כל צומת בעץ צריך לקיים את התנאים . לכן נשתמש בתבנית "האם כל".
כדי לבדוק את קיום התנאים נצטרך לפרק לשני תנאים שונים. כל אחד מהם יהווה פעולת עזר רקורסיבית לפי התבניות הבוליאניות:
numTav – המונה כמה פעמים מופיע התו. נקרא לפעולה כל פעם מתת-עץ אחר.
checkBig – תחזיר אמת אם התו הוא הגדול בתת-העץ שלו.
פתרון ב- java:
  public static boolean checkBig(BinTreeNode<InfoTree> bt, char tav)
 {//מחזיר אמת אם התו הוא הגדול ביותר בעץ
            if (bt==null)  return true; //תנאי עצירה – הכל בסדר
            if (tav < bt.getInfo().getTav())
                        return false;
            return checkBig(bt.getLeft(),tav)  && checkBig(bt.getRight(),tav);
   }
public static boolean tavPlus(BinTreeNode<InfoTree> bt)
{      boolean ok1, ok2;
       if (bt==null)   return true; תנאי עצירה // 
      char tav=bt.getInfo().getTav();
      ok1= bt.getInfo().getNum() ==numTav(bt.getLeft(),tav) +numTav(bt.getRight(),tav);
      ok2= checkBig( bt, tav);
       if(!ok1 || !ok2)   return false;
       return tavPlus(bt.getLeft()) && tavPlus(bt.getRight());
  }




Text Box: דוגמה 12: סבא רבא    ( בגרות תש"ס)
"סבא-רבא" של שני עלים שונים בעץ בינרי הוא האב הקדמון המשותף לשני העלים ברמה הגבוהה ביותר בעץ. 
כתוב פעולה המחזירה את הצומת שהוא "סבא-רבא" של העלים ale1, ale2 בעץ.
(ציטוט חלקי)
ניתוח הפתרון:
לפי המוצע בשאלה מומלץ להשתמש בשתי פעולות עזר:
הורהAba (דוגמה 5 כאן)
האם צאצא -  המחזירה 'אמת' אם x הוא צאצא של y בעץ ו'שקר' אחרת.
            לצורך הפעולה נשתמש בפעולה  המקבלת עץ בינארי t והפניה לצומתbtn . הפעולה מחזירה 'אמת' אם הצומת btn נמצא בעץ t. לפי תבנית "האם יש".
            נמצא את x ואחר כך נבדוק אם y מופיע בתת-העץ מתחתיו.
public static bool IsIn (BinTreeNode<int> t, BinTreeNode<int> btn)
{          if (t == null ) return false; // יצאנו ולא מצאנו
            if (t == bt ) return true; // הפניות זהות – מצאנו
            return IsIn(t, t.GetLeft()) || IsIn(t, t.GetRight());
}
public static bool IsZeeza(BinTreeNode<int> bt, BinTreeNode<int> x,                                                                                                                                                           BinTreeNode<int>  y)
{          if (bt == null)    return false;
         if (bt == x)
                if (IsIn(bt.GetLeft(), y) ||  IsIn(bt.GetRight(), y))
                        return true;
            return IsZeeza(bt.GetLeft(), x, y) ||  IsZeeza(bt.GetRight(), x, y);
}

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

  public static BinTreeNode<int> SabaRaba( BinTreeNode<int> t,  
                                                                        BinTreeNode<int> leaf1, BinTreeNode<int> leaf2)
   {       BinTreeNode<int> father= Aba(t,leaf1);
         if (father == t) return t;
         if (IsZeeza(t, leaf2,father) return father;
         return SabaRaba(t,father, leaf2);
Text Box: דוגמא 13:
פעולה המקבלת עץ בינארי של מספרים, ומוסיפה בו צמתים עד שיהיה עץ מאוזן מלא. ערכו של כל צומת  שנוסף יהיה 0.
   }

העץ לפני:                                                                                                העץ אחרי:

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

public static void meuzan((BinTreeNode<Integer> t)
{// פעולה עוטפת
            int h=hightTree(t);// פעולת עזר לחישוב גובה העץ
            helpMeuzan(t,h,0);
}


public static void helpMeuzan(BinTreeNode<Integer> t, int h, int rama)
{          if (rama<h)
            {          if (t.getLeft()==null)
                                 t.setLeft(new BinTreeNode<Integer>(0));
                        if (t.getRight()==null)
                                t.setRight(new BinTreeNode<Integer>(0));
                        helpMeuzan(t.getLeft(), h, rama+1);
                        helpMeuzan(t.getRight(), h, rama+1);
            }
Text Box: דוגמה 14: בגרות תשס"א
א.	לפניך כותרת הפעולה:public static void Leaves(BinTreeNode<int> t, Stack<int> s)
	הפעולה מקבלת עץ בינרי לא ריק t של מספרים שלמים ומחסנית ריקה s של מספרים שלמים.
	הפעולה מכניסה למחסנית את ערכי כל העלים של העץ t , על פי סדר סריקה מימין לשמאל.

}

הפעולה היא פעולת void שסורקת את העץ ומטפלת רק בעלים, המחסנית מופיעה בפרמטר – לכן מתאימה לתבנית הראשונה של הסריקה. 
בטיפול בצומת מבררים אם הצומת הוא עלה, אם כן, מכניסים אותו למחסנית. 
לפי בקשת השאלה ברקורסיה פונים קודם לתת העץ הימני לפני השמאלי, וכך מקבלים את העלים בסדר מימין לשמאל ולא משמאל לימין, כפי שזה מופיע בתבנית.
        public static void Leaves(BinTreeNode<int> t, Stack<int> s)
        {   if (t != null)
            {     if (Ale(t))              s.Push(t.GetInfo());
                        Leaves(t.GetRight(), s);
                      Leaves(t.GetLeft(), s);
            }
Text Box: המשך השאלה:
 ב.	כתוב פעולה בוליאנית שתקבל 2 עצים בינריים לא ריקים של מספרים שלמים, ותחזיר  true 	אם מתקיימים שני התנאים האלה:
•	יש להם אותו מספר עלים
•	על פי סדר הסריקה מימין לשמאל, ערכי העלים שווים 
   אחרת, הפעולה תחזיר false.
        }

נכתוב פעולה היוצרת שתי מחסניות בעזרת הפעולה מסעיף א'. נחזיר 'אמת' אם ערכיהן זהים והן מסתיימות יחד. 
        public static bool IsEqual(BinTreeNode<int> t1, BinTreeNode<int> t2)
        {  Stack<int>  s1 = new Stack<int>();
                        Stack<int> s2 = new Stack<int>();
                        Leaves(t1, s1);
                        Leaves(t1, s1);
                        while (!s1.IsEmpty() && !s2.IsEmpty())
                        {    if (s1.Pop() != s2.Pop())
                                                 return false;
                        }
                        return s1.IsEmpty() && s2.IsEmpty();
        }


אין תגובות:

הוסף רשומת תגובה