**Termin zajęć:** 24/25.04.2012

====== Listy i drzewa BST ======
===== 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 - omawiana tematyka
  - Każdy powinien przynieść na zajęcia zaimplementowane szkielety następujących struktur (struct, not <del>class</del>)
    - lista jednokierunkowa
    - lista dwukierunkowa
    - drzewo binarne BST

===== Dodatek =====
**Struktury w postaci klas:**

Przykładowy 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>