[WikiDyd] [TitleIndex] [WordIndex

AiSD Zajęcia 6

Zagadnienia związane z drzewami:

1. Binarne drzewa wyszukiwania.

2. Metody chodzenia po drzewach.

3. Określanie szybkości działania drzewa na podstawie jego wysokości.

4. Wywarzanie drzewa (drzewa czerwono-czarne). (Material nieobowiązkowy!)

Przykładowa klasa drzewa binarnego

   1     class TreeElem
   2     {
   3         public double number = 0;
   4         public TreeElem left = null;
   5         public TreeElem right = null;
   6     }
   7 
   8     class Tree
   9     {
  10         const int MAXLEVEL = 5;
  11 
  12         protected TreeElem head = null;
  13 
  14         /* Dodaje nowa wartosc.
  15          * Na poczatku sprawdza czy korzen drzewa jest juz wykorzystywany.
  16          * jezeli korzen juz istnieje wyowylawan jest rekurencyjna procedura 
  17          * dodawania: addRecur. */
  18         public void add(double newValue)
  19         {
  20             if (head == null)
  21             {
  22                 head = new TreeElem();
  23                 head.number = newValue;
  24             }
  25             else
  26             {
  27                 addRecur(newValue, head);
  28             }
  29         }
  30 
  31         /* Rekurencyjna procedura dodawania. Jezeli nowa wartosc
  32          * jest wieksza od wartosci przechowywanej w danym elemencie
  33          * to jest ona dodawana do prawej strony podrzewa, w przeciwnym
  34          * razie dodawana jest do lewej.
  35          */
  36         protected void addRecur(double newValue, TreeElem elem)
  37         {
  38             if (newValue > elem.number) // nowa wart. jest wieksza 
  39                                         // od przechowywanej w biezacym wezle -> dodajemy do prawego pod-drzewa
  40             {
  41                 if (elem.right == null)
  42                 { // nie ma 'dziecka' z prawej strony, to tworzymy nowego.
  43                     elem.right = new TreeElem();
  44                     elem.right.number = newValue;
  45                 }
  46                 else
  47                 { // jest dziecko, to wywolujemy rekurencyjnie procedure, przekazujac
  48                   // dziecko jako nowy argument. Czyli schodzimy o jeden
  49                   // poziom drzewa nizej.
  50                     addRecur(newValue, elem.right);
  51                 }
  52             }
  53             else // nowa wartosc jest mniejsza lub rowna -> dodajemy do lewego
  54             {
  55                 if (elem.left == null)
  56                 { 
  57                     elem.left = new TreeElem();
  58                     elem.left.number = newValue;
  59                 }
  60                 else
  61                 {
  62                     addRecur(newValue, elem.left);
  63                 }
  64             }
  65         }
  66 
  67         /* Wypisujemy na ekranie wartosci rosnaca.
  68          * Funkcja jest stworzna dlatego, ze nie mozemy wywolac bezposrednio
  69          * funkcji rekurencyjnej PrintToScreenRecur z zewnatrz klasy,
  70          * poniewaz z zewnatrz nie mamy dostepu do elementu TreeElem head (poniewaz
  71          * jest protected)
  72          */
  73         public void PrintToScreen()
  74         {
  75             PrintToScreenRecur(head);
  76         }
  77 
  78         /* W sposob rekurencyjny wypisujemy na ekranie,
  79          * wartosci drzewa rosnaco.
  80          * 
  81          * Prosze wzrocic uwage na kolejnosc rekurencji oraz
  82          * miejsce gdzie wywolujemy wypisywanie na ekranie.
  83          * Manipulujac kolejnoscia tych trzech linii mozemy wypisywac
  84          * rosnaca, malejaco, przechodzic przez korzen, itp...
  85          */
  86         protected void PrintToScreenRecur(TreeElem elem)
  87         {
  88             if (elem != null)
  89             {
  90                 Console.WriteLine("{0}, ", elem.number);
  91                 PrintToScreenRecur(elem.right);
  92                 PrintToScreenRecur(elem.left);
  93             }
  94         }
  95 
  96         /* Ponizsze dwa atrybuty wykorzystywane sa wypisywania elementow listy 
  97          * na odpowiednim poziomie. Schodzac do nizszego poziomu drzewa
  98          * zwiekszamy wartosc zmiennej level.
  99          * Zamiast wypisywania na ekranie, procedura PrintToScreenLevelRecur
 100          * dodaje wartosci elementow listy do napisow (stringow) w tablicy strLevels.
 101          * Na koncu wypisywane sa napisy z tablicy strLevels.
 102          * */
 103         int level;
 104         String[] strLevels = new String[MAXLEVEL];
 105 
 106         public void PrintToScreenLevel()
 107         {
 108             level = 0;
 109             PrintToScreenLevelRecur(head);
 110             for (int i =0; i < MAXLEVEL; i++)
 111                 Console.WriteLine("({0}): {1}",i,strLevels[i]);
 112         }
 113 
 114         protected void PrintToScreenLevelRecur(TreeElem elem)
 115         {
 116             if (elem != null)
 117             {
 118                 // dodajemy do tablicy na odpowiednim poziomie liczbe 
 119                 if (level < MAXLEVEL)
 120                     strLevels[level] = String.Format("{0} {1}", strLevels[level], elem.number);
 121                 // zwiekszamy poziom
 122                 level++;
 123 
 124                 PrintToScreenLevelRecur(elem.right);
 125                 PrintToScreenLevelRecur(elem.left);
 126 
 127                 //teraz zmniejszamy poziom wracajac z rekurencji...
 128                 level--;
 129             }
 130             else
 131             {
 132                 // jezeli dany element jest pusty, zaiast liczby wypisujemy znak 
 133                 // podkreslenia: _
 134                 if (level < MAXLEVEL)
 135                     strLevels[level] = String.Format("{0} _", strLevels[level]);
 136             }
 137         }
 138 
 139         public TreeElem find(double v)
 140         {
 141             return null;
 142         }
 143 
 144         public TreeElem addElem(TreeElem elem)
 145         {
 146             return null;
 147         }
 148 
 149         public int getMaxLevel()
 150         {
 151             return 0;
 152         }
 153 
 154         public int getElemCount()
 155         {
 156             return 0;
 157         }
 158     }

Program testujący

   1 class Program
   2     {
   3         static void Main(string[] args)
   4         {
   5             // Na poczatku budujemy drzewo z danych testowych
   6             Tree t = new Tree();
   7             t.add(5);
   8             t.add(3);
   9             t.add(2);
  10             t.add(3);
  11             t.add(3);
  12             t.add(7);
  13             t.add(8);
  14 
  15             // Wypisujemy w sposob posortowany elementy drzewa
  16             t.PrintToScreen();
  17 
  18             // wypisujemy na ekranie elementy uwzgledniajac poziomy na ktorych
  19             // sie znajduja
  20             t.PrintToScreenLevel();
  21 
  22             // czekamy az ktos wcisnie Enter.
  23             Console.ReadLine();
  24         }
  25     }

Przykładowe zadania

  1. Proszę zaimplementować funkcję wypisującą elementy drzewa malejąco.
  2. Proszę zaimplementować funkcję zwracającą maksymalny poziom drzewa.
  3. Proszę zaimplementować funkcję zwracającą liczbę elementów w drzewie.
  4. Napisz funkcję wypisującą elementy przechodząc przez korzeń.
  5. Wykorzystaj program przykładowy do przechowywania w drzewie wskazaną przez prowadzącego klasę (np. klasę Osoba z Zajęć 5).
  6. Zaimplementuj wskazaną przez prowadzącego regułę przechowywania elementów w drzewie (lewy mniejszy od prawego lub odwrotnie).
  7. Przetestuj głębokość drzewa w zależności od różnych kolejności dodawania nowych elementów.

2015-09-23 06:32