Drzewa poszukiwań binarnych - BST


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).

Węzeł BST

Dla każdego węzła w drzewie BST zachodzą następujące własności:

Drzewo BST

To jest drzewo BST
           Drzewo nie BST

To nie jest drzewo BST

Strukturę 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.

Dodawanie węzła do drzewa BST

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ęci

Dane 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 - 1
3 - 1 - 2 3 - 2 - 1
BST BST BST BST BST

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).

Wyszukiwanie węzła o zadanym kluczu

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).

Wyszukiwanie najmniejszego i największego klucza

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;
}

Znajdowanie poprzednika i następnika

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:

Poprzednik węzła BST 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).
 
Poprzednik węzła BST 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

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:

Usuwanie węzła BST Usuwanie węzła BST

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

Usuwanie węzła BST Usuwanie węzła BST

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.

Usuwanie węzła BST Usuwanie węzła BST

Jeśli następnik lub poprzednik posiada dziecko, to zostaje on nim zastąpiony w strukturze drzewa, co wynika z rekurencyjnego charakteru tej operacji.

Usuwanie węzła BST Usuwanie węzła BST

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 z
K04: 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 żaden
K10: 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;
}

Przechodzenie przez drzewo BST

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 testowy

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



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.