Drzewo poszukiwań binarnych BST (ang. Binary Search Tree) jest dynamiczną strukturą danych zbudowaną z węzłów (ang. node). Każdy węzeł może posiadać dwóch potomków (left - lewy i right - prawy) oraz jednego przodka (p - parent). Z każdym węzłem dodatkowo związany jest klucz (key).
Dla każdego węzła w drzewie BST zachodzą następujące własności:
- Wartości kluczy węzłów leżących w lewym poddrzewie węzła są mniejsze lub równe wartości klucza danego węzła.
- Wartości kluczy węzłów leżących w prawym poddrzewie węzła są większe lub równe wartości klucza danego węzła.
To jest drzewo BST
To nie jest drzewo BSTStrukturę węzłów drzewa BST deklarujemy następująco:
struct BSTNode { BSTNode * p, * left, * right; int key; }Oczywiście oprócz powyższych "obowiązkowych" pól węzeł może zawierać również inne dane, potrzebne w danej implementacji.
Umówmy się, iż liściem (ang. leaf) drzewa BST będziemy nazywali węzeł zewnętrzny - wskazywany przez pola left lub right zawierające adres pusty - NULL. Czyli adres liścia ma wartość NULL. Z oczywistych względów liść nie będzie reprezentowany w pamięci - jest tworem umownym.
Wybór wariantu algorytmu dodawania węzła do drzewa BST zależy od tego, czy dopuszczamy występowanie w drzewie BST węzłów o równych kluczach, czy nie.
Algorytm wstawiania nowego węzła bez powtórzeń kluczy
Wejście:
root - korzeń drzewa BST n - wstawiany węzeł Wyjście:
true, jeśli węzeł został dodany do drzewa BST
false, jeśli węzeł nie został dodany. W takim przypadku węzeł jest usuwany z pamięciDane pomocnicze:
x, y - węzły drzewa BST key(w) - klucz węzła w left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w p(w) - rodzic węzła w Lista kroków
K01: y ← NIL ; y wskazuje rodzica aktualnie przeglądanego węzła K02: x ← root ; wyszukiwanie rozpoczynamy od korzenia drzewa BST K03: left(n) ← NIL; right(n) ← NIL ; zerujemy pola left i right wstawionego elementu K04: Dopóki x ≠ NIL wykonuj kroki K05...K07 ; przeszukujemy drzewo BST K05: Jeśli key(n) = key(x), usuń węzeł i zakończ z false ; natrafiliśmy na węzeł o tym samym kluczu, co klucz wstawianego elementu K06: y ← x ; zapamiętujemy adres bieżąco odwiedzanego elementu K07: Jeśli key(n) < key(x), to x ← left(x)
inaczej x ← right(x); jeśli klucz wstawianego elementu jest mniejszy od klucza bieżącego elementu,
to wybieramy lewego potomka jako następny do odwiedzenia element.
Inaczej wybieramy prawego potomka.K08: p(n) ← y ; y zawsze pamięta rodzica K09: Jeśli y = NIL, to root ← n i idź do K11 ; drzewo BST jest puste, wstawiamy pierwszy element K10: Jeśli key(n) < key(y), to left(y) ← n
inaczej right(y) ← n; porównujemy klucz n z kluczem y. W zależności od wyniku węzeł
n dowiązujemy do pola left lub right jego rodzica.K11: Zakończ z true Algorytm wstawiania z powtórzeniami nie posiada jedynie kroku K04 - zawsze przechodzimy do liścia drzewa.
bool BSTinsert(BSTNode * &root, BSTNode * n) { BSTNode * y = NULL, * x = root; n->left = n->right = NULL; while(x) { if(n->key == x->key) { delete n; return false; } y = x; x = (n->key < x->key) ? x->left : x->right; } n->p = y; if(!y) root = n; else if(n->key < y->key) y->left = n; else y->right = n; return true; }
W zależności od kolejności wprowadzania danych do drzewa BST mogą powstać różne konfiguracje węzłów. Dla 3 wartości klucza otrzymujemy pięć różnych drzew BST:
1 - 2 - 3 1 - 3 - 2 2 - 1 - 3
2 - 3 - 13 - 1 - 2 3 - 2 - 1 Szczególnie niekorzystne jest wprowadzanie wartości uporządkowanych rosnąco lub malejąco - w takim przypadku otrzymujemy zdegenerowane drzewo BST do listy liniowej (pierwszy i ostatni przykład).
Wejście:
root - korzeń drzewa BST key - klucz poszukiwanego węzła Wyjście:
Węzeł zawierający klucz key lub NULL, jeśli drzewo BST nie posiada takiego węzła.
Dane pomocnicze
x - węzeł drzewa BST key(w) - klucz węzła w left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w Lista kroków
K01: x ← root ; wyszukiwanie rozpoczynamy od korzenia drzewa BST K02: Dopóki (x ≠ NIL) i (key(x) ≠ key) wykonuj krok K03 ; przechodzimy przez poszczególne węzły drzewa BST K03: Jeśli key < key(x), x ← left(x)
inaczej x ← right(x); wybierając lewego lub prawego potomka K04: Zwróć x i zakończ
BSTNode * BSTsearch(BSTNode * root, int key) { BSTNode * x = root; while((x) && (x->key != key)) x = (key < x->key) ? x->left : x->right; return x; }Złożoność obliczeniowa operacji wyszukiwania zależy liniowo od ilości poziomów w drzewie BST - O(k). W drzewie BST zrównoważonym jest to O(log n), gdzie n oznacza liczbę wierzchołków drzewa, natomiast w drzewie losowym (wartości kluczy węzłów wstawianych do drzewa były losowe) otrzymujemy O(√n).
Przy wyszukiwaniu najmniejszego klucza poruszamy się po lewych krawędziach węzłów aż osiągniemy węzeł, którego lewy potomek jest pustym liściem. Klucz tego węzła posiada wartość minimalną, co wynika bezpośrednio z własności drzewa BST.
Wejście:
root - korzeń drzewa BST Wyjście:
Wartość minimalnego klucza w drzewie BST. Drzewo nie może być puste.
Dane pomocnicze:
x - węzeł drzewa BST key(w) - klucz węzła w left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w Lista kroków
K01: x ← root ; wyszukiwanie rozpoczynamy od korzenia drzewa BST K02: Dopóki (left(x) ≠ NIL) wykonuj krok K03 ; przechodzimy przez poszczególne węzły drzewa BST K03: x ← left(x) ; wybierając zawsze lewego potomka K04: Zwróć key(x) i zakończ
int BSTminkey(BSTNode * root) { BSTNode * x = root; while((x->left) x = x->left; return x->key; }Przy wyszukiwaniu największego klucza drzewa BST zmieniamy jedynie gałęzie z lewych na prawe:
int BSTmaxkey(BSTNode * root) { BSTNode * x = root; while(x->right) x = x->right; return x->key; }Zamiast klucza, obie powyższe funkcje mogą zwracać adresy węzłów w drzewie BST:
BSTNode * BSTminnode(BSTNode * root) { BSTNode * x = root; while(x->left) x = x->left; return x; } BSTNode * BSTmaxnode(BSTNode * root) { BSTNode * x = root; while(x->right) x = x->right; return x; }
Poprzednikiem węzła x na drzewie BST będziemy nazywali węzeł, którego klucz jest bezpośrednio mniejszy od klucza węzła x. Oznacza to tyle, iż na drzewie BST nie istnieją węzły, których klucze wpadają w przedział pomiędzy wartością klucza poprzednika a wartością klucza węzła x. Z własności drzewa BST wyciągamy następujące wnioski:
Jeśli węzeł x posiada lewego potomka, to poprzednikiem węzła x będzie element o największym kluczu w lewym poddrzewie BST węzła x (czyli drzewie BST, którego korzeniem jest lewy potomek węzła x).
Jeśli węzeł x nie posiada lewego potomka, to poprzednikiem węzła x będzie pierwszy rodzic, dla którego węzeł x leży w prawym poddrzewie. Jeśli dwa powyższe warunki nie są spełnione, to węzeł x posiada minimalny klucz w drzewie BST i nie istnieje jego poprzednik. Wejście:
x - zawiera adres węzła drzewa BST, dla którego szukamy poprzednika Wyjście:
Adres poprzednika węzła x w drzewie BST. Jeśli nie istnieje poprzednik węzła x, to wynikiem jest NULL.
Dane pomocnicze:
y - węzeł drzewa BST key(w) - klucz węzła w left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w p(w) - rodzic węzła w BSTmaxnode(w) - zwraca węzeł o największym kluczu w poddrzewie o korzeniu w Lista kroków
K01: Jeśli left(x) ≠ NIL, to zwróć BSTmaxnode(left(x)) i zakończ ; poprzednikiem jest maksymalny element lewego poddrzewa K02: y ← x ; zapamiętujemy adres dziecka K03: x ← p(x) ; przenosimy się do rodzica K04: Jeśli (x ≠ NIL) i (right(x) ≠ y), idź do kroku K02 ; przerywamy pętlę przy wyjściu poza drzewo BST lub przy znalezieniu poprzednika K05: Zwróć x ; zwracamy poprzednik lub NULL K06: Zakończ
BSTNode * BSTpred(BSTNode * x) { if(x->left) return BSTmaxnode(x->left); BSTNode * y; do { y = x; x = x->p; } while(x && (x->right != y)); return x; }Następnik znajdujemy wg identycznego schematu - odwracamy jedynie warunki: jeśli węzeł x posiada prawego potomka, to następnikiem jest węzeł minimalny w prawym poddrzewie BST węzła x. Jeśli węzeł x nie posiada prawego potomka, to następnikiem będzie pierwszy rodzic, dla którego węzeł x leży w lewym poddrzewie.
BSTNode * BSTsucc(BSTNode * x) { if(x->right) return BSTminnode(x->right); BSTNode * y; do { y = x; x = x->p; } while(x && (x->left != y)); return x; }
Usuwanie węzła w drzewie BST wymaga sprawdzenia kilku warunków. Jeśli węzeł nie posiada dzieci, to po prostu odłączamy go od struktury drzewa:
 |
→ |  |
Jeśli węzeł posiada dzieci, to nie można go tak po prostu usunąć, gdyż w strukturze drzewa pojawiłyby się dziury. Mogą wystąpić dwa przypadki:
Węzeł posiada tylko lewego lub tylko prawego potomka - usuwany węzeł zastępujemy potomkiem
 |
→ |
 |
Węzeł posiada obu potomków - lewego i prawego. Aby nie degenerować struktury drzewa, usuwany węzeł zastępujemy losowo raz przez jego poprzednikiem, a raz przez jego następnikiem. Do zrealizowania tej operacji wykorzystujemy rekurencyjnie procedurę usuwania dla poprzednika lub następnika, a następnie zastępujemy usuwany węzeł następnikiem lub poprzednikiem.
 |
→ |
 |
Jeśli następnik lub poprzednik posiada dziecko, to zostaje on nim zastąpiony w strukturze drzewa, co wynika z rekurencyjnego charakteru tej operacji.
 |
→ |
 |
Z powyższych rozważań wynika następujący algorytm usuwania węzła w drzewie BST:
Wejście:
root - korzeń drzewa BST x - węzeł drzewa BST, który należy usunąć Wyjście:
Węzeł usunięty ze struktury drzewa BST
Dane pomocnicze:
y, z - węzły drzewa BST key(w) - klucz węzła w left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w p(w) - rodzic węzła w BSTsucc(w) - zwraca następnik węzła w BSTpred(w) - zwraca poprzednik węzła w random(a,b) - zwraca liczbę pseudolosową z przedziału <a,b> BSTremove(root,w) - usuwa węzeł w z drzewa - do wywołań rekurencyjnych Lista kroków
K01: y ← p(x) ; węzeł y jest rodzicem usuwanego węzła K02: Jeśli left(x) = 0 lub right(x) = 0, idź do K09 ;sprawdzamy, czy węzeł ma obu potomków K03: Jeśli random(0,1) = 0, to z ← BSTremove(root,BSTpred(x))
inaczej z ← BSTremove(root,BSTsucc(x)); ma, z drzewa rekurencyjnie usuwamy poprzednik lub następnik
zapamiętując go w zK04: left(z) ← left(x) ; z wstawiamy do drzewa w miejsce x K05: right(z) ← right(x) K06: Jeśli left(z) ≠ NIL, to p(left(z)) ← z ; ustawiamy z jako rodzica lewego potomka, o ile istnieje K07: Jeśli right(z) ≠ NIL, to p(right(z)) ← z ; ustawiamy z jako rodzica prawego potomka, o ile istnieje K08: Idź do K10 K09: Jeśli left(x), to z ← left(x)
inaczej z ← right(x); z staje się lewym lub prawym potomkiem
; który z nich istnieje lub NIL, jeśli nie istnieje żadenK10: Jeśli z ≠ NIL, to p(z) ← y ; jeśli węzeł z istnieje, ustawiamy ego rodzica K11: Jeśli y ≠ NIL, idź do K13 ; sprawdzamy, czy z nie jest korzeniem drzewa K12: root ← z i idź do K14 ; jeśli tak, ustawiamy korzeń i kończymy K13: Jeśli left(y) = x, to left(y) ← z
inaczej right(y) ← z; jeśli nie, to z podpinamy pod odpowiednie dziecko rodzica x K14: Zwróć x i zakończ
BSTNode * BSTremove(BSTNode * &root, BSTNode * x) { BSTNode * y = x->p, * z; if((x->left) && (x->right)) { z = (rand() % 2) ? BSTremove(root, BSTpred(x)) : BSTremove(root, BSTsucc(x)); z->left = x->left; if(z->left) z->left->p = z; z->right = x->right; if(z->right) z->right->p = z; } else z = (x->left) ? x->left : x->right; if(z) z->p = y; if(!y) root = z; else if(y->left == x) y->left = z; else y->right = z; return x; }
Istnieje wiele algorytmów przechodzenia przez drzewo BST.
Algorytm inorder
W algorytmie inorder przetwarzamy kolejno: lewą gałąź drzewa BST, węzeł, prawą gałąź drzewa BST. W efekcie rozpoczynamy od minimalnego węzła drzewa i odwiedzamy kolejne węzły w porządku rosnącym ich kluczy, kończąc na węźle maksymalnym. Jeśli posiadamy losowy ciąg kluczy, to utworzenie z nich drzewa BST oraz przeglądnięcie go algorytmem inorder jest operacją sortowania.
Wejście:
root - korzeń drzewa BST Wyjście:
Przejście przez węzły drzewa BST w kolejności od węzła minimalnego (o najmniejszym kluczu) do maksymalnego.
Dane pomocnicze:
left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w BSTinorder(x) - procedura przeglądania inorder do rekurencyjnych wywołań Lista kroków
K01: Jeśli root = NIL, zakończ ; kończymy jeśli doszliśmy do liścia K02: BSTinorder(left(root)) ; przetwarzamy lewą gałąź drzewa BST K03: ... ; tutaj przetwarzamy bieżący węzeł K04: BSTinorder(right(root)) ; przetwarzamy prawą krawędź drzewa BST K05: Zakończ
void BSTinorder(BSTNode * root) { if(root) { BSTinorder(root->left); // tutaj przetwarzamy bieżący węzeł BSTinorder(root->right); } }Głębokość rekurencji zależy od wysokości drzewa BST. Należy zatem uważać, aby przetwarzane drzewo BST nie było drzewem zdegenerowanym, w przeciwnym razie przy dużej liczbie węzłów może dochodzić do przepełnienia stosu. Alternatywą jest zastąpienie algorytmu rekurencyjnego algorytmem iteracyjnym ze stosem, na który odkładamy wierzchołki.
Algorytm preorder
W algorytmie preorder przetwarzamy kolejno: węzeł, lewą gałąź drzewa BST, prawą gałąź drzewa BST.
Wejście:
root - korzeń drzewa BST Wyjście:
Przejście przez węzły drzewa BST w kolejności preorder
Dane pomocnicze:
left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w BSTpreorder(x) - procedura przeglądania preorder do rekurencyjnych wywołań Lista kroków
K01: Jeśli root = NIL, zakończ ; kończymy jeśli doszliśmy do liścia K02: ... ; tutaj przetwarzamy bieżący węzeł K03: BSTpreorder(left(root)) ; przetwarzamy lewą gałąź drzewa BST K04: BSTpreorder(right(root)) ; przetwarzamy prawą krawędź drzewa BST K05: Zakończ
void BSTpreorder(BSTNode * root) { if(root) { // tutaj przetwarzamy bieżący węzeł BSTpreorder(root->left); BSTpreorder(root->right); } }Algorytm postorder
W algorytmie postorder przetwarzamy kolejno: lewą gałąź drzewa BST, prawą gałąź drzewa BST, węzeł .
Wejście:
root - korzeń drzewa BST Wyjście:
Przejście przez węzły drzewa BST w kolejności postorder.
Dane pomocnicze:
left(w) - lewy potomek węzła w right(w) - prawy potomek węzła w BSTpostorder(x) - procedura przeglądania postorder do rekurencyjnych wywołań Lista kroków
K01: Jeśli root = NIL, zakończ ; kończymy jeśli doszliśmy do liścia K02: BSTpostorder(left(root)) ; przetwarzamy lewą gałąź drzewa BST K03: BSTpostorder(right(root)) ; przetwarzamy prawą krawędź drzewa BST K04: ... ; tutaj przetwarzamy bieżący węzeł K05: Zakończ
void BSTpostorder(BSTNode * root) { if(root) { BSTpostorder(root->left); BSTpostorder(root->right); // tutaj przetwarzamy bieżący węzeł } }
Program umożliwia przetestowanie poszczególnych operacji na drzewie BST.
// Test procedur obsługi drzewa BST // (C)2008 mgr Jerzy Wałaszek // Koło informatyczne I LO w Tarnowie //----------------------------------- #include <iostream> using namespace std; // definicja typu danych reprezentującego węzeł drzewa BST //-------------------------------------------------------- struct BSTNode { BSTNode * p, * left, * right; int key; // tutaj można umieszczać inne pola danych }; // Definicja klasy obsługującej drzewo BST //---------------------------------------- class BST { public: BSTNode * root; // korzeń drzewa int count; // liczba węzłów BST(); ~BST(); bool insert(BSTNode * n); BSTNode * search(int key); int maxKey(BSTNode * x); int minKey(BSTNode * x); BSTNode * maxNode(BSTNode * x); BSTNode * minNode(BSTNode * x); BSTNode * pred(BSTNode * x); BSTNode * succ(BSTNode * x); BSTNode * remove(BSTNode * x); void preorder(BSTNode * x); void inorder(BSTNode * x); void postorder(BSTNode * x); void walk(BSTNode * x); void coutBSTcount(); }; // ********************************************** // *** Definicje funkcji składowych klasy BST *** // ********************************************** // Konstruktor klasy BST //---------------------- BST::BST() { root = NULL; count = 0; } // Destruktor klasy BST //--------------------- BST::~BST() { while(root) delete(remove(root)); } // Wstawia element do struktury BST //--------------------------------- bool BST::insert(BSTNode * n) { BSTNode * y, * x = root; y = n->left = n->right = NULL; while(x) { if(n->key == x->key) { delete n; return false; } y = x; x = (n->key < x->key) ? x->left : x->right; } n->p = y; if(!y) root = n; else if(n->key < y->key) y->left = n; else y->right = n; count++; return true; } // Wyszukuje element wg wartości klucza //------------------------------------- BSTNode * BST::search(int key) { BSTNode * x = root; while((x) && (x->key != key)) x = (key < x->key) ? x->left : x->right; return x; } // Zwraca masymalną wartość klucza //-------------------------------- int BST::minKey(BSTNode * x) { while(x->left) x = x->left; return x->key; } // Zwraca minimalną wartość klucza //-------------------------------- int BST::maxKey(BSTNode * x) { while(x->right) x = x->right; return x->key; } // Zwraca węzeł z maksymalnym kluczem //----------------------------------- BSTNode * BST::minNode(BSTNode * x) { while(x->left) x = x->left; return x; } // Zwraca węzeł z minimalnym kluczem //---------------------------------- BSTNode * BST::maxNode(BSTNode * x) { while(x->right) x = x->right; return x; } // Zwraca węzeł poprzednika //------------------------- BSTNode * BST::pred(BSTNode * x) { if(x->left) return maxNode(x->left); BSTNode * y; do { y = x; x = x->p; } while(x && (x->right != y)); return x; } // Zwraca węzeł następnika //------------------------ BSTNode * BST::succ(BSTNode * x) { if(x->right) return minNode(x->right); BSTNode * y; do { y = x; x = x->p; } while(x && (x->left != y)); return x; } // Usuwa element x ze struktury BST. Zwraca usunięty węzeł //-------------------------------------------------------- BSTNode * BST::remove(BSTNode * x) { BSTNode * y = x->p, * z; if((x->left) && (x->right)) { z = (rand() % 2) ? remove(pred(x)) : remove(succ(x)); z->left = x->left; if(z->left) z->left->p = z; z->right = x->right; if(z->right) z->right->p = z; count++; } else z = (x->left) ? x->left : x->right; if(z) z->p = y; if(!y) root = z; else if(y->left == x) y->left = z; else y->right = z; count--; return x; } // Przechodzi przez BST metodą preorder //------------------------------------- void BST::preorder(BSTNode * x) { if(x) { cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł preorder(x->left); preorder(x->right); } } // Przechodzi przez BST metodą inorder //------------------------------------ void BST::inorder(BSTNode * x) { if(x) { inorder(x->left); cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł inorder(x->right); } } // Przechodzi przez BST metodą postorder //-------------------------------------- void BST::postorder(BSTNode * x) { if(x) { postorder(x->left); postorder(x->right); cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł } } // Przechodzi przez drzewo wypisując zawartość węzłów //--------------------------------------------------- void BST::walk(BSTNode * x) { cout << x->key << " : Left-> "; if(x->left) cout << x->left->key; else cout << "NIL"; cout << ", Right-> "; if(x->right) cout << x->right->key; else cout << "NIL"; cout << endl; if(x->left) walk(x->left); if(x->right) walk(x->right); } // Wypisuje do cout liczbę węzłów drzewa BST //------------------------------------------ void BST::coutBSTcount() { cout << "\nLiczba wezlow drzewa BST : " << count << endl << endl; } // ********************************** // *** Funkcje obsługi opcji menu *** // ********************************** // Dodaje nowe węzły do drzewa BST //-------------------------------- void add(BST * T) { cout << "Dodawanie nowych wezlow do drzewa BST\n" "-------------------------------------\n\n"; T->coutBSTcount(); cout << "Podaj liczbe wezlow do utworzenia, a nastepnie wprowadz odpowiednia\n" "liczbe kluczy nowych wezlow.\n\n"; int i,n; BSTNode * x; cin >> n; for(i = 0; i < n; i++) { x = new BSTNode; cin >> x->key; T->insert(x); } cout << endl; T->walk(T->root); T->coutBSTcount(); } // Usuwa węzeł o zadanym kluczu //----------------------------- void del(BST * T) { cout << "Usuwanie wezla drzewa BST o zadanym kluczu\n" "------------------------------------------\n\n"; T->coutBSTcount(); BSTNode * x; int key; cout << "Podaj klucz usuwanego wezla : "; cin >> key; x = T->search(key); if(x) { delete T->remove(x); cout << endl; if(T->root) T->walk(T->root); T->coutBSTcount(); } else cout << "\nBrak wezla o takim kluczu\n"; } // Sprawdza, czy drzewo zawiera węzeł o zadanym kluczu //---------------------------------------------------- void check(BST * T) { cout << "Sprawdzenie obecnosci wezla o danym kluczu w drzewie BST\n" "--------------------------------------------------------\n\n" "Podaj klucz wezla : "; int key; cin >> key; cout << endl; if(T->search(key)) cout << "Wezel znaleziony.\n"; else cout << "W drzewie BST brak wezla o podanym kluczu\n"; } // Znajduje minimalny i maksymalny klucz //-------------------------------------- void minmax(BST * T) { cout << "Znajdowanie minimalnego i maksymalnego klucza w drzewie BST\n" "-----------------------------------------------------------\n\n" "Klucz minimalny : " << T->minKey(T->root) << endl << "Klucz maksymalny : " << T->maxKey(T->root) << endl; } // Znajduje poprzednik węzła o zadanym kluczu //------------------------------------------- void pred(BST * T) { cout << "Znajdowanie poprzednika w drzewie BST\n" "-------------------------------------\n\n" "Podaj klucz wezla : "; int key; BSTNode * x; cin >> key; cout << endl; x = T->search(key); if(x) { x = T->pred(x); if(x) cout << "Poprzednikiem [" << key << "] jest " << x->key << endl; else cout << "Wezel [" << key << "] nie posiada poprzednika\n"; } else cout << "Wezel o podanym kluczu nie istnieje w drzewie BST\n"; } // Znajduje następnik węzła o zadanym kluczu //------------------------------------------ void succ(BST * T) { cout << "Znajdowanie nastepnika w drzewie BST\n" "------------------------------------\n\n" "Podaj klucz wezla : "; int key; BSTNode * x; cin >> key; cout << endl; x = T->search(key); if(x) { x = T->succ(x); if(x) cout << "Nastepnikiem [" << key << "] jest " << x->key << endl; else cout << "Wezel [" << key << "] nie posiada nastepnika\n"; } else cout << "Wezel o podanym kluczu nie istnieje w drzewie BST\n"; } // Przechodzi przez drzewo algorytmem preorder //-------------------------------------------- void preorder(BST * T) { cout << "Przechodzenie drzewa BST algorytmem preorder\n" "--------------------------------------------\n\n"; T->preorder(T->root); } // Przechodzi przez drzewo algorytmem inorder //-------------------------------------------- void inorder(BST * T) { cout << "Przechodzenie drzewa BST algorytmem inorder\n" "-------------------------------------------\n\n"; T->inorder(T->root); } // Przechodzi przez drzewo algorytmem postorder //-------------------------------------------- void postorder(BST * T) { cout << "Przechodzenie drzewa BST algorytmem postorder\n" "---------------------------------------------\n\n"; T->postorder(T->root); } // ********************** // *** Program główny *** // ********************** main() { BST * T = new BST(); int choice; do { system("cls"); // w Linuxie wstaw clear cout << "Test funkcji obslugi drzew poszukiwan binarnych\n" "===============================================\n\n" "Wybor Funkcja\n" "-------------\n" " [0] Koniec\n" " [1] Dodaj wezly\n" " [2] Usun wezel\n" " [3] Sprawdz obecnosc wezla\n" " [4] Wezel min i max\n" " [5] Poprzednik\n" " [6] Nastepnik\n" " [7] Preorder\n" " [8] Inorder\n" " [9] Postorder\n" "--------------\n" "Twoj wybor : "; cin >> choice; system("cls"); switch(choice) { case 1 : add(T); break; case 2 : del(T); break; case 3 : check(T); break; case 4 : minmax(T); break; case 5 : pred(T); break; case 6 : succ(T); break; case 7 : preorder(T); break; case 8 : inorder(T); break; case 9 : postorder(T); break; } if((choice >= 1) && (choice <= 9)) { cout << endl; system("pause"); } } while(choice); delete T; }
Test funkcji obslugi drzew poszukiwan binarnych =============================================== Wybor Funkcja ------------- [0] Koniec [1] Dodaj wezly [2] Usun wezel [3] Sprawdz obecnosc wezla [4] Wezel min i max [5] Poprzednik [6] Nastepnik [7] Preorder [8] Inorder [9] Postorder -------------- Twoj wybor : |
Dodawanie nowych wezlow do drzewa BST ------------------------------------- Liczba wezlow drzewa BST : 0 Podaj liczbe wezlow do utworzenia, a nastepnie wprowadz odpowiednia liczbe kluczy nowych wezlow. 6 5 2 1 6 4 7 5 : Left-> 2, Right-> 6 2 : Left-> 1, Right-> 4 1 : Left-> NIL, Right-> NIL 4 : Left-> NIL, Right-> NIL 6 : Left-> NIL, Right-> 7 7 : Left-> NIL, Right-> NIL Liczba wezlow drzewa BST : 6 |
Znajdowanie minimalnego i maksymalnego klucza w drzewie BST ----------------------------------------------------------- Klucz minimalny : 1 Klucz maksymalny : 7 |
Znajdowanie poprzednika w drzewie BST ------------------------------------- Podaj klucz wezla : 4 Poprzednikiem [4] jest 2 |
Przechodzenie drzewa BST algorytmem preorder -------------------------------------------- 5 2 1 4 6 7 |
Przechodzenie drzewa BST algorytmem inorder ------------------------------------------- 1 2 4 5 6 7 |
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe
