====== Ćwiczenie 6: Pojemniki - drzewo ======

Ćwiczenie to jest częścią większego zadania, które będzie polegać na zaprojektowaniu **szablonów** kilku rodzajów klas pojemnikowych z wykorzystaniem **mechanizmu dziedziczenia** oraz **iteratora** dla tych klas. \\ **Ćwiczenie 6.** polegać będzie na zaprojektowaniu szablonu pojemnika typu **drzewo**. 

===== Po co =====
  * Doskonalenie umiejętności definiowania szablonów.
  * Utrwalenie umiejętności posługiwania się mechanizmami dziedziczenia, polimorfizmu.
  * Zapoznanie się z podstawowymi strukturami danych.

===== Oddawanie ćwiczenia =====
  * Przed oddaniem ćwiczenia, program należy przetestować używając następującego pliku main: {{:pl:dydaktyka:jimp2:2016:part2:ex:ex6main.zip|}}
  * Powyższy plik wymaga istnienia pliku ''aghInclude.h'' poprzez który włączane są wszystkie niezbędne pliki.
 
===== Przebieg ćwiczenia =====
  - Wykonanie ćwiczenia polega na zaimplementowaniu klasy **''aghTree''**, która będzie reprezentować **binarne drzewo przeszukiwań (BST)**  - porównaj drzewo AVL, drzewo czerwono-czarne.
  - Przyjmujemy że w lewym poddrzewie przechowywane są wartości mniejsze lub równe wartości korzenia danego poddrzewa, natomiast w prawym większe.
  - Klasa **''aghTree''** dziedziczy klasę abstrakcyjną opisaną w [[ex3|ćwiczeniu 3]] w sposób **publiczny**.
  - Kolejność (indeksowanie) elementów w drzewie jest określana przez kolejność odwiedzania węzłów metodą **in-order rozpoczynając od lewego poddrzewa**.
  - Klasa powinna implementować wszystkie opisane w [[ex3|ćwiczeniu 3.]] metody, które powinny działać tak samo jak w przypadku poprzednich pojemników (**''aghVector''**, **''aghSlist''**, **''aghDlist''**). Ze względu na ustalony sposób wstawiania elementów do drzewa, implementacja następujących metod jest nieco inna:
    * Metoda **''insert''** - parametr określający **miejsce wstawienia elementu** będzie w tej klasie **ignorowany**.
    * Metoda **''replace''** - usuwa (określony jako parametr metody) element a następnie wstawia nową wartość. Wstawianie odbywa się w typowy dla tego rodzaju drzewa sposób.
  - Nie ma przymusu tworzenia metod czy też klas specjalizowanych.
  - Program powinien mieć budowę modułową.
  - **Nie dublujemy kodu**, tzn. nie piszemy dwa i więcej razy kodu, który wykonuje podobne zadania - **ta kwestia będzie ważnym kryterium oceny**.
  - Do realizacji ćwiczenia **nie można** wykorzystywać już gotowych rozwiązań (STL, Qt, tip).
  - Zaistniałe nieprawidłowe sytuacje powinny zostać obsłużone poprzez wyrzucenie wyjątku przy pomocy klasy **''[[..:org:codepolicy#obsluga_wyjatkow|aghException]]''**.
  - Program powinien się poprawnie kompilować i uruchomić wraz z dostarczonym plikiem {{:pl:dydaktyka:jimp2:2016:part2:ex:ex6main.zip|}}.