**Termin zajęć:** 19/20.04.2011

**Do przygotowania:**
  - Znajomość budowy i zasad działania podstawowych struktur danych:
     * lista jedno- i dwukierunkowa
     * drzewo BST
  - Zakres wiadomości: //Cormen - Wprowadzenie do algorytmów, Część III: Wprowadzenie, Rozdział 10 i 12//
  - Każdy powinien przynieść na zajęcia zaimplementowane następujące klasy
    - lista jednokierunkowa
    - lista dwukierunkowa
    - drzewo binarne BST
//Poniższe szkielety klas powinny być dla Państwa pomocą, nie są natomiast wiążącą specyfikacją (szczegóły mogą Państwo wykonać wg uznania - to nie zajęcia z programowania).//

{{http://akolacz.tarchomin.pl/images/ListaJednokierunkowa.png}}\\
{{http://akolacz.tarchomin.pl/images/ListaDwukierunkowa.png}}

Szkielet klasy listy dwukierunkowej:
<code c++>
typedef ElementType int; // typ elementu na liście

class ListNode {
  public:
	ElementType value;
	ListNode *prev, *next;
        ListNode(){
          prev = NULL;
          next = NULL;
        }
};

class List{
  private:
        ListNode *head, *tail;
        
  public:
        List(){ 
          head = tail = NULL;
        }
        
        //poniższe metody należy zaimplementować samodzielnie
        
        ~List(); // należy zdefiniować tak, aby usuwał wszystkie elementy

        ElementType getValue(int index);
        void setValue(const ElementType& element);
        

        void insert(int index, ElementType value);
        bool remove(int index);
        bool remove(ElementType value);
        ListNode* search(ElementType value);

};
</code>


Szkielet klas węzła drzewa i samego drzewa (rodzica danego węzła można zrealizować jako pole klasy ''TreeNode'' lub wskaźnik na niego pozyskiwać za pomocą odpowiedniej metody ''parent(TreeNode x)'' klasy TreeBST):

<code c++>
class TreeNode {
  public:
	ElementType key;
	TreeNode *left, *right, *parent;
};

class TreeBST{
	private:
		TreeNode * root;
	public:
		TreeBST();
		~TreeBST();
		TreeNode* search(ElementType key);  // wyszukaj element o kluczu ''key'' w drzewie
		bool insert(ElementType key);  // wstaw element o kluczu ''key'' do drzewa
		bool remove(ElementType key);  // usuń element o kluczu ''key'' z drzewa
		bool member(ElementType key);  // sprawdź czy element o kluczu ''key'' należy do drzewa
};
</code>