יום ראשון, 8 בדצמבר 2013

חלק ב'

למעבר לחלק א' לחצו כאן





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

דוגמה: עבור הרשימה הבאה:  2,4,12,5,6,3,1,7,9
הערך שיחזור הוא 17, והרשימה תראה כך: 2,4,6,3,1,7,9

פתרון:

class Program
    {

        public static int big(List<int> L)
        {
            Node<int> p = L.GetFirst();
            Node<int> t = p;
            int max = p.GetInfo() + p.GetNext().GetInfo();
            while (p.GetNext() != null)
            {
                if (p.GetInfo() + p.GetNext().GetInfo() > max)
                {
                    max = p.GetInfo() + p.GetNext().GetInfo();
                    t = p;
                }

                p = p.GetNext();
            }

            t=L.Remove(t);
            t = L.Remove(t);
                    return max;

        }
        



        static void Main(string[] args)
        {
            List<int> L = new List<int>();
            Node <int> t;
            L.Insert(null, 1);
            L.Insert(null, 100);
            L.Insert(null, 3333);
            L.Insert(null, 2);
            L.Insert(null, 3);
            L.Insert(null, 4);
            L.Insert(null, 6);
            L.Insert(null, 7);
            Console.WriteLine(L.ToString());
            big(L);
            Console.WriteLine(L.ToString());



           Console.WriteLine();
           
            Console.ReadKey();
      


        }
    }




__________________________________________________________________

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

דומגאות:


מצב סיבוכיות
סדר היעילות
פונקצייה הריצה

O(n)
2
10+n
1
O(n^2)
4
n^2+50
2
O(n)
3
30n
3
O(n^3)
5
5n^3+4n
4
O(1)
1
30
5
O(2^n)
6
64+2^n
6
R
__________________________________________________________________

סיבוכיות ליניארית
10m+2n+n → O(m+n) או O(n) 

O(n) - מתאפשר כי אפשר לבטא את אם באמצעות אן


5m*n → O(m*n)  או O(n^2)

O(n^2) - מתאפשר כי אפשר לבטא את אם באמצעות אן

__________________________________________________________________


מדד סיבוכיות



        public static void Remove (List <int> L, int x)
        {
            Node<int> p = L.GetFirst();
            while (p != null)
            {
                if (p.GetInfo() == x)
                    p = L.Remove(p);
                else
                    p = p.GetNext();
            }
        }

מדד הסיבוכיות של הפעולה הזאת הוא
O(n)
n מהווה אתמספר החוליות ברשימה L




__________________________________________________________________


ממשק כל הפעולות החשובות של Node ו List

יצירת רשימה חדשה 
List<type> name = new List<type>();

יצירת מצביע p  אשר מצביע על החולייה הראשונה של הרשימה name
Node <type> p = name.GetFirst();

מחזיר את הערך שהמצביע p מצביע עליו
p.GetInfo();

מקדם את המצביע p צעד אחד קדימה
p = p.GetNext();

מדפיס במחרוזת את כל הרשימה
name.ToString()

מסיר את החולייה שהמצביע שלה הוא t, והמצביע של החולייה אחריו יהיה p.
p = name.Remove(t);

מוסיף ברשימה name את הערך value אחרי המצביע p
name.Insert(p, value);




__________________________________________________________________




מחסנית  stack
מבנה נתונים דינמי המנוהל בשיטת First in Last Out (FILO) הראשון שנכנס הוא האחרון שייצא.
(הערות: אסור לשלוף נתונים ממחסנית  ריקה, אין מגבלה בגודל).

ממשק המחסנית
stack

Stack<type> name = new Stack<type>();

יצירת מחסנית חדשה בשם
name
name.IsEmpty();

מחזיר ערך בוליאני, 'אמת' האם המחסנית ריקה, 'שקר' אם המחסנית לא ריקה.
name.Push(value);

מכניס למחסנית בשם
name
את הערך
value
name.Pop();

שולף מהמכניס את הערך שבראש המכסנית
name.Top();

מחזיר את הערך הבראש המחסנית
name.ToString();

מחזיר מחרוזת של כל המחסנית






__________________________________________________________________

תור Queue

תור - מבנ נתונים דימני המנוהל בשיטת LIFO- Last in first out  הראשון שנכנס הוא הראשון שיוצא.
(הערות: אסור לשלוף נתונים מתור ריק, אין מגבלה בגודל).

אם נכנסים המספרים הבאים לתור (משמאל לימין)
7 , 9 , 14 , 3 , 1
סדר היציאה שלהם הוא:
7
9
14
3
1


הפעולות / הפקודות / הממשק  של מחלקת תור Queue




Queue<type> name = new Queue<type>();
פעולה בונה תור
name.Head();
קבלת הערך של העומד בראש התור
name.Insert(value);
הכנסת ערך כלשהו לתור
name.Remove();
מוחק את הערך שבראש התור
name.IsEmpty();
מחזיר ערך בוליאני, אם התור ריק מחזיר 'אמת' , אם התור לא ריק מחזיר 'שקר'
name.ToString();

מחזיר במחרוזת את  כלהערכים של התור לפי הסדר




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

תשובה:
{
    class Program
    {
        public static int count_del(Queue<int> l, int x)
        {
            Queue<int> temp = new Queue<int>();
            int mone = 0;
   
            while (!l.IsEmpty()) // כל עוד התור "אל" לא ריק בצע
            {
         
                int t = l.Head();
                if (t == x)
                {
                    mone++;
                    l.Remove();
                }
                else
                    temp.Insert(l.Remove()); // גם מוחק וגם מכניס לתור "טמפ" בו זמנית

            }


            while (!temp.IsEmpty()) // כל עוד התור "טמפ" לא ריק בצע          
                l.Insert(temp.Remove());
 
            return mone;


        }


        static void Main(string[] args)
        {

            Queue<int> help = new Queue<int>();

            help.Insert(1);
            help.Insert(3);
            help.Insert(3);
            help.Insert(3);
            help.Insert(5);
            help.Insert(6);
            help.Insert(7);
            help.Insert(1);
            Console.WriteLine("the queue is: " + help.ToString());
            Console.WriteLine("enter value to count and delete");
            int x = int.Parse(Console.ReadLine());

            Console.WriteLine("the count of the num you sent is: "+count_del(help, x));
            Console.WriteLine("the queue now is: " + help.ToString());

            Console.ReadKey();
            help.ToString();


        }
    }
}




__________________________________________________________________


איך ממיינים תור queue בסדר עולה? מהקטן אל הגדול תשובה מלאה פתרון
פעולה שממיינת תור בסדר עולה queue





{
    class Program
    {


        static Queue<int> sortq(Queue<int> q)
        {

            Queue<int> temp = new Queue<int>();
            while (!q.IsEmpty())
            {
                temp.Insert(q.Remove());
            }

            while (!temp.IsEmpty())
            {
                int x = min(temp);
                q.Insert(x);
                count_del(temp, x);

            }
            return q;
        }


        static int min(Queue<int> q)
        {
            int y;
            Queue<int> l = new Queue<int>();
            Queue<int> l2 = new Queue<int>();
            while (!q.IsEmpty())   
            {
                 y=q.Head();
                l.Insert(y);
                l2.Insert(y);
                q.Remove();
            }
            while (!l2.IsEmpty())
                q.Insert(l2.Remove());
  


            int minn = l.Head();
            while (!l.IsEmpty())
            {
                if (l.Head() < minn)
                {
                    minn = l.Head();
                }
                l.Remove();
            }

            return minn;

        }






        public static Queue<int> count_del(Queue<int> l, int x)
        {
            Queue<int> temp = new Queue<int>();
            int mone = 0;

            while (!l.IsEmpty()) 
            {

                int t = l.Head();
                if (t == x && mone != 1)
                {
                    mone++;
                    l.Remove();
                }
                else
                    temp.Insert(l.Remove()); 

            }


            while (!temp.IsEmpty())           
                l.Insert(temp.Remove());

            return l;


        }


        static void Main(string[] args)
        {

            Queue<int> help = new Queue<int>();

            help.Insert(2222);
            help.Insert(32323232);
            help.Insert(3);
            help.Insert(3);
            help.Insert(5);
            help.Insert(6);
            help.Insert(7);
            help.Insert(56565);




            Queue<int> help1 = new Queue<int>();

            help1.Insert(1);
            help1.Insert(3);
            help1.Insert(3);
            help1.Insert(3);
            help1.Insert(5);
            help1.Insert(6);
            help1.Insert(7);
            help1.Insert(1);


            Console.WriteLine("the queue is: " + help.ToString());


            Console.WriteLine("the count of the num you sent is: " + sortq(help).ToString());
       


            Console.ReadKey();
            help.ToString();


        }
    }
}









__________________________________________________________________



איך ממיינים תור queue בסדר יורד? מהגדול אל הקטן תשובה מלאה פתרון
פעולה שממיינת תור בסדר יורד queue

{
    class Program
    {


        static Queue<int> sortq(Queue<int> q)
        {

            Queue<int> temp = new Queue<int>();
            while (!q.IsEmpty())
            {
                temp.Insert(q.Remove());
            }

            while (!temp.IsEmpty())
            {
                int x = max(temp);
                q.Insert(x);
                count_del(temp, x);

            }
            return q;
        }


        static int max(Queue<int> q)
        {
            int y;
            Queue<int> l = new Queue<int>();
            Queue<int> l2 = new Queue<int>();
            while (!q.IsEmpty())
            {
                 y=q.Head();
                l.Insert(y);
                l2.Insert(y);
                q.Remove();
            }
            while (!l2.IsEmpty())
                q.Insert(l2.Remove());



            int maxx = l.Head();
            while (!l.IsEmpty())
            {
                if (l.Head() > maxx)
                {
                    maxx = l.Head();
                }
                l.Remove();
            }

            return maxx;

        }






        public static Queue<int> count_del(Queue<int> l, int x)
        {
            Queue<int> temp = new Queue<int>();
            int mone = 0;

            while (!l.IsEmpty()) // כל עוד התור "אל" לא ריק בצע
            {

                int t = l.Head();
                if (t == x && mone != 1)
                {
                    mone++;
                    l.Remove();
                }
                else
                    temp.Insert(l.Remove());
            }


            while (!temp.IsEmpty())        
                l.Insert(temp.Remove());

            return l;


        }


        static void Main(string[] args)
        {

            Queue<int> help = new Queue<int>();

            help.Insert(2222);
            help.Insert(32323232);
            help.Insert(3);
            help.Insert(3);
            help.Insert(5);
            help.Insert(6);
            help.Insert(7);
            help.Insert(56565);




            Queue<int> help1 = new Queue<int>();

            help1.Insert(1);
            help1.Insert(3);
            help1.Insert(3);
            help1.Insert(3);
            help1.Insert(5);
            help1.Insert(6);
            help1.Insert(7);
            help1.Insert(1);


            Console.WriteLine("the queue is: " + help.ToString());


            Console.WriteLine("the count of the num you sent is: " + sortq(help).ToString());
     


            Console.ReadKey();
            help.ToString();


        }
    }
}




__________________________________________________________________

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


using System;
//using System.Collections.Generic;
using System.Linq;
using System.Text;
using Unit4.CollectionsLib;


namespace ConsoleApplication1
{
    class Program
    {


        static int count(Queue<int> q)
        {
            int y;
            Queue<int> l = new Queue<int>();
            Queue<int> l2 = new Queue<int>();
            int mone = 0;
            while (!q.IsEmpty())  
            {
                mone++;
                 y=q.Head();
                l.Insert(y);
                l2.Insert(y);
                q.Remove();
            }
            while (!l2.IsEmpty())
                q.Insert(l2.Remove());


            return mone;

        }








        static void Main(string[] args)
        {

            Queue<int> help = new Queue<int>();

            help.Insert(2222);
            help.Insert(32323232);
            help.Insert(3);
            help.Insert(3);
            help.Insert(5);
            help.Insert(6);
            help.Insert(7);
            help.Insert(56565);




            Queue<int> help1 = new Queue<int>();

            help1.Insert(1);
            help1.Insert(3);
            help1.Insert(3);
            help1.Insert(3);
            help1.Insert(5);
            help1.Insert(6);
            help1.Insert(7);
            help1.Insert(1);


            Console.WriteLine("the queue now is: " + help.ToString());


            Console.WriteLine("the count of the numbers in the queue is "+count(help)) ;

            Console.WriteLine("the queue now is: " + help.ToString());

            Console.ReadKey();
            help.ToString();


        }
    }
}




__________________________________________________________________



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

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

1. 

עץ ריק

2. 

3. 



4.


5. 








עץ בינארי - מושגים



1. A הוא בן שמאלי של C
2. G הוא בן יחיד של A
3. F ו-M הם צמתים אחים של G
4. G הוא צאצא של A ו-C.
5. E,D,F,M צמתים עלים
6. הבן הימני של A ריק
7.העץ הנתון הוא בגובה / ברמה 3
8. עץ ריק יהיה ברמה 1- (מינוס אחת)
9. ברמה שתיים יש שלושה צמתים 
10. כל אב, הוא אב קדמון של הצמתים שמתחתיו
- A הוא אב קדמון של G, F ,E




מבנה השורש






שיטות סריקה של עץ בינארי

1. סריקת תחילית PreOrder - מבקרת בצומת ומבצעת עליו עיבוד, לאחר מכן פונה לבן השמאלי בסריקה תחילית, ולבסוף פונה לבן הימני בסריקה תחילית. הסריקה התחילית היא סריקה רקורסיבית.

2. סריקה תוכית InOrder  - בסריקה תוכית פונים לבן השמאלי, כשאין בן שמאלי במעבר על הבן הימני מבצעים ביקור בצומת ועיבוד בצומת ולבסוף פונים לבן הימני בסריקה תוכית. הסריקה היא סריקה רקורסיבית.

3. סריקה סופית PostOrder - בסריקה סופית פונים אל הבן השמאלי, וכשאין בין שמאלי פונם לבן הימני בסריקה סופית. לבסוף מבקרים בצומת.

4. סריקת רמות - Level - סריקת רמות סורקת את העץ הבינארי החל מרמה אפס משמאל לימן


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




סריקה תחילית:
A G F E B C D


סריקה תוכית:
F E G A C B D


סריקה סופית:
E F G C D B A


סריקת רמות:
A G B F C D E




__________________________________________________________________


סרוק לפי שרטוט העץ לפי ארבעת שיטות הסריקה





סריקה בשיטת תחילית:
D C B A E F G I H


סריקה בשיטה תוכית:

B C A D I G H F E

סריקה בשיטה סופית:
B A C I H G F E D


סריקה בשיטת רמות

D C E B A F G I H





__________________________________________________________________


עץ בינארי
סרוק את העץ הבינארי הזה בארבעת הסריקות

סריקה תחילית:
C A B E D

סריקה תוכית:
C B E A D

סריקה סופית:

E B DA C

סריקת רמות:
C A B D E




__________________________________________________________________

בניית עץ מסריקות

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

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

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




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

למשל אם נתונות לנו הסריקות הבאות (סתם דומגא)
  A C B D G E - סריקה תוכית
C A B E G D - סריקה סופית

אפשר להסיק שהשורש, הכי למעלה יהיה D כי הוא בסוף של הסריקה התוכית, ומימין לו יהיו G E ומשאל לו יהיו A C B

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

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

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



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

למשל אם נתונות לנו הסריקות הבאות (סתם דומגא)
  A C B D G E - סריקה תוכית
C A B E G D - סריקה תחילית

אפשר להסיק שהשורש, הכי למעלה יהיה C כי הוא בהתחלה של הסריקה התחילית, ומימין לו יהיו B D G E ומשאל לו יהיו A 

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

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

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



__________________________________________________________________


מחלקת עצים בינאריים - הממשק המלא של המחלקה
(כדי להשתמש במחלקה יש להוריד unit4.dll זה נמצא בחלק א', בראש העומד מופיע קישור לחלק א')
ויש לכתוב את הדבר הבא בראש התוכנית
using System;
//using System.Collections.Generic;
using System.Linq;
using System.Text;
using Unit4.CollectionsLib;


BinTreeNode <type> name = new BinTreeNode<type>(value);

בונה עץ בינארי בערך החולה ובטיפוס/סוג שהזנתה, אין לו בנים המצביעים שלו מצביעים על שני ערכים של
Null
המצביע הוא
name
BinTreeNode<type> name = new BinTreeNode<type>(name1, x, null);

משמאל לימין: מצביע שמאלי, ערך החולייה, מצביע ימני
name.ToString();

מחזיר במחרוזת את ערך החולייה (לפני השם)
name.GetInfo();
מחזיר את ערך החולייה
name.GetLeft();

מחזיר את הערך של הבן השמאלי של החולייה
name.GetRight();

מחזיר את הערך של הבן הימני של החולייה
name.SetLeft(pointer);

משנה את המצביע של החולייה השמאלית / מחליפה את הילד השמאלי
name.SetRight(pointer);

משנה את המצביע של החולייה הימנית / מחליפה את הילד הימני
name.SetInfo(value);
משנה את הערך למצביע שהזנת



__________________________________________________________________


הפעולה של סריקה תחילית / הקוד המלא של סריקה תחילית


  public static void PreOrder(BinTreeNode<char> t)

        {

            if (t != null)

            {

                Console.WriteLine(t.GetInfo() + " ,");

                PreOrder(t.GetLeft());

                PreOrder(t.GetRight());
            }

         }



__________________________________________________________________


הפעולה של סריקה תוכית/ הקוד המלא של סריקה תוכית




  public static void PreOrder(BinTreeNode<char> t)
        {
            if (t != null)
            {
                PreOrder(t.GetLeft());
                Console.WriteLine(t.GetInfo() + " ,");
                PreOrder(t.GetRight());
            }

         }








__________________________________________________________________


הפעולה של סריקה סופית/ הקוד המלא של סריקה סופית




  public static void PreOrder(BinTreeNode<char> t)
        {
            if (t != null)
            {
                PreOrder(t.GetLeft());
                PreOrder(t.GetRight());
                Console.WriteLine(t.GetInfo() + " ,");
            }

         }


__________________________________________________________________


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

פעולה שמחזירה שסופרת את כמות העלים בעץ


        public static int alim(BinTreeNode<int> t)

        {

            if (t == null) return 0;

            if (t.GetLeft() == t.GetRight()) return 1;

            return alim(t.GetLeft()) + alim(t.GetRight());

        }





__________________________________________________________________

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

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

תשובות פתרונות

א.




ב.

 public static bool piramida(BinTreeNode<int> t)
        {
            if ( (t==null )|| t.GetLeft() == t.GetRight()) return true;
            if (t.GetLeft() == null || t.GetRight() == null) return false;
            return piramida (t.GetLeft()) && piramida (t.GetRight());
        }



__________________________________________________________________


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



ועבור כל ערך חדש מתקיים הדבר עבור כל תת עץ.

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






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







__________________________________________________________________



משימה:

              public static bool sTosearchTree(BinTreeNode<int> t, int x)

// טענת כניסה: הפעולה מקבלת עץ חיפוש וערך מספרי
// טענה יציאה: הפעולה מחזירה "אמת" אם הערך המספרי קיים בעץ ושקר אחרת

פתרון:



using System;
//using System.Collections.Generic;
using System.Linq;
using System.Text;
using Unit4.CollectionsLib;

namespace ConsoleApplication1
{
    class Program
    {
        


              public static void AddTosearchTree(BinTreeNode<int> t, int x)
      {
     if (t.GetRight() == t.GetLeft())
             {
                    if (t.GetInfo() > x)
                        t.SetLeft(new BinTreeNode<int>(x));
                    else
                        t.SetRight(new BinTreeNode<int>(x));
             }
                else
                {
                    if (t.GetLeft() == null)
                    {
                        if (t.GetInfo() > x)
                            t.SetLeft(new BinTreeNode<int>(x));
                        else
                            AddTosearchTree(t.GetRight(), x);
                    }
                    else
                    {
                        if (t.GetRight() == null)
                        {
                            if (t.GetInfo() <= x)
                                t.SetRight(new BinTreeNode<int>(x));
                            else
                                AddTosearchTree(t.GetLeft(), x);
                        }
                        else
                            if (t.GetInfo() > x)
                                AddTosearchTree(t.GetLeft(), x);
                            else
                                AddTosearchTree(t.GetRight(), x);

                    }

              }
        }


              public static bool sTosearchTree(BinTreeNode<int> t, int x)
              {
                  if (t == null) return false;
                  if (t.GetInfo() == x) return true;
                  if (t.GetInfo() <= x) return sTosearchTree(t.GetRight(), x);
                  else return sTosearchTree(t.GetLeft(), x);
              }




        static void Main(string[] args)
        {
            BinTreeNode<int> name = new BinTreeNode<int>(66);

            int[] arr = new int[4];
            arr[0] = 523;
            arr[1] = 555;
            arr[2] = 4;
            arr[3] = -3;

            for (int i = 0; i < 4; i++)
            {
                AddTosearchTree(name, arr[i]);
               
            }
            Console.WriteLine(sTosearchTree(name, 4));
            Console.WriteLine(sTosearchTree(name, 444444));

            BinTreeUtils.ShowTree(name);
        }
    }
}


אין תגובות:

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