Termin zajęć: 24/25.04.2012
Listy i drzewa BST
Do przygotowania
Znajomość budowy i zasad działania podstawowych struktur danych:
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 class)
lista jednokierunkowa
lista dwukierunkowa
drzewo binarne BST
Dodatek
Struktury w postaci klas:
Przykładowy szkielet klasy listy dwukierunkowej:
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);
};
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):
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
};