Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Drzewa poszukiwań binarnych – BST

SPIS TREŚCI
Podrozdziały

Budowa drzewa BST

Drzewo poszukiwań binarnych ( ang. Binary Search Tree ) jest drzewem binarnym, w którym każdy węzeł spełnia reguły:

  1. Jeśli węzeł posiada lewe poddrzewo ( drzewo, którego korzeniem jest lewy syn ), to wszystkie węzły w tym poddrzewie mają wartość niewiększą od wartości danego węzła.
  2. Jeśli węzeł posiada prawe poddrzewo, to wszystkie węzły w tym poddrzewie są niemniejsze od wartości danego węzła.

Innymi słowy, przejście in-order tego drzewa daje ciąg wartości niemalejących.

obrazek
Drzewo BST
in-order: 1 2 2 3 5 8 9
     obrazek
Drzewo nie BST
in-order: 1 2 2 3 2 8 9

Powyżej mamy przykład drzewa BST oraz drzewa nie będącego drzewem BST – zaznaczony liść 2 należy do prawego poddrzewa korzenia 2 i jest od niego mniejszy, a w prawym poddrzewie muszą być tylko węzły równe lub większe od korzenia.

Węzły w drzewie BST zawierają trzy wskaźniki, klucz oraz dane:

Pascal
type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up    : PBSTNode;
    left  : PBSTNode;
    right : PBSTNode;
    key   : integer;
    data  : typ_danych;
  end;
   C++
struct BSTNode
{
  BSTNode * up;
  BSTNode * left;
  BSTNode * right;
  int key;
  typ_danych data;
};
   Basic
Type BSTNode
  up    As BSTNode Ptr
  left  As BSTNode Ptr
  right As BSTNode Ptr
  key   As Integer
  data  As typ_danych
End Type
up  –  wskazanie ojca węzła
left  – wskazanie lewego syna
right  – wskazanie prawego syna
key  – klucz, wg którego węzły są uporządkowane na drzewie BST
data  – dowolne dane

Dla niektórych drzew BST klucz może być daną, wtedy nie występuje pole data.

Na początek:  podrozdziału   strony 

Wyszukiwanie węzłów w drzewie BST

Drzewa BST pozwalają wyszukiwać zawarte w nich elementy z klasą złożoności obliczeniowej O ( log n ), gdzie n  oznacza liczbę węzłów. Prześledźmy sposób wyszukiwania węzła o kluczu 19 w drzewie BST:   

Stan Opis
obrazek Wyszukiwanie rozpoczynamy od korzenia drzewa. Porównujemy wartość węzła z wartością poszukiwaną.  Ponieważ jest ona większa od wartości korzenia, idziemy wzdłuż prawej krawędzi do prawego syna ( jeśli węzeł nie miałby prawego syna, to oznaczałoby to, że poszukiwanej wartości nie ma w drzewie BST. )
obrazek W węźle 21 ponownie dokonujemy porównania. Ponieważ poszukiwany węzeł jest mniejszy od 21, wybieramy gałąź lewą i przechodzimy do lewego syna 15.
obrazek Porównujemy węzeł 15 z poszukiwanym 19. Ponieważ 19 jest większe, idziemy prawą krawędzią do prawego syna 19.
obrazek Porównujemy węzeł 19 z poszukiwanym. Są równe. Wyszukiwanie zakończone.

Z przedstawionego powyżej schematu wynikają dwa proste wnioski:

obrazek
Element najmniejszy w drzewie znajdziemy,
idąc lewymi gałęziami aż do elementu, który
nie posiada już lewego syna
     obrazek
Element największy w drzewie znajdziemy,
idąc prawymi gałęziami aż do elementu, który
nie posiada już prawego syna.

W obu przypadkach nie musimy porównywać węzłów.

Algorytm wyszukiwania węzła w drzewie BST – findBST ( root, k )

Wejście:

k  –  klucz poszukiwanego węzła
p  – wskazanie korzenia drzewa BST

Wyjście:

Wskazanie węzła na drzewie BST o kluczu k  lub nil, jeśli drzewo nie zawiera takiego węzła

Lista kroków:

K01: Dopóki ( p ≠ nil ) obrazek ( ( pkey  ) ≠ k  ),
wykonuj krok K02
węzła brak lub został znaleziony
K02:     Jeśli k  < ( pkey  ),
    to p  ← ( pleft  )
    inaczej p  ← ( pright  )
decydujemy, którą drogą pójść: w lewo czy w prawo
K03: Zakończ z wynikiem p  

Algorytm wyszukiwania w drzewie BST węzła o najmniejszym kluczu – minBST ( p )

Wejście:

p  – wskazanie korzenia drzewa BST

Wyjście:

Wskazanie węzła o najmniejszym kluczu lub nil, jeśli drzewo jest puste.

Lista kroków:

K01: Jeśli p  = nil,
to idź do kroku K03
 
K02: Dopóki ( pleft  ) nil,
wykonuj
p  ← ( pleft  )
szukamy węzła bez lewego syna
K03: Zakończ z wynikiem p  

Algorytm wyszukiwania w drzewie BST węzła o największym kluczu – maxBST ( p )

Wejście:

p  – wskazanie korzenia drzewa BST

Wyjście:

Wskazanie węzła o największym kluczu lub nil, jeśli drzewo jest puste.

Lista kroków:

K01: Jeśli p  = nil,
to idź do kroku K03
 
K02: Dopóki ( pright  ) nil,
wykonuj
p  ← ( pright  )
szukamy węzła bez prawego syna
K03: Zakończ z wynikiem p  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wczytuje definicję drzewa binarnego, którego klucze są liczbami całkowitymi. Wyznacza klucz minimalny i maksymalny, a następnie idąc kolejno przez wartości kluczy od min do max wyświetla informacje o znalezionym węźle.

Sposób wprowadzania drzew binarnych opisaliśmy w rozdziale o badaniu drzew binarnych. Tutaj krótko przypomnijmy, że węzły drzewa są numerowane od strony lewej do prawej na kolejnych poziomach. Pierwszą liczbą jest ilość wierzchołków n. Kolejne n  wierszy zawiera 3 liczby określające kolejne wierzchołki. Pierwsza liczba w trójce określa klucz węzła. Pozostałe dwie liczby określają kolejno numer węzła będącego lewym i prawym synem. Jeśli węzeł nie ma któregoś z synów, to numer syna przyjmuje wartość zero. W strukturach węzłów nie będziemy wykorzystywać pola up, które tutaj nie będzie nam potrzebne, ponieważ będziemy poruszać się tylko w dół drzewa.
 
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek     
12
9 1 2
5 3 4
15 5 6
4 7 0
7 8 9
10 0 10
18 0 11
1 0 0
6 0 0
8 0 0
12 0 0
19 0 0
Pascal
// Wyszukiwanie w drzewie BST
// Data: 24.04.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program bst;

// Typ węzłów drzewa BST

type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    left  : PBSTNode;
    right : PBSTNode;
    key   : integer;
  end;

// Funkcja wczytuje drzewo BST ze standardowego
// wejścia i zwraca wskazanie korzenia.
//-----------------------------------------------
function readBST : PBSTNode;
var
  vp : array of PBSTNode;   // Tablica wskazań węzłów
  key, l, r, i, n : integer;

begin

  read ( n );               // Odczytujemy liczbę węzłów drzewa

  SetLength ( vp, n );      // Tworzymy dynamiczną tablicę wskazań węzłów

  // Tablicę dynamiczną wypełniamy wskazaniami węzłów, 
  // które również tworzymy dynamicznie

  for i := 0 to n - 1 do new ( vp [ i ] );

  // Teraz wczytujemy definicję drzewa i tworzymy jego strukturę
  // w pamięci wypełniając odpowiednie pola węzłów.

  for i := 0 to n - 1 do
  begin

    read ( key, l, r );     // Czytamy klucz, numer lewego i prawego syna

    vp [ i]^.key := key;    // Ustawiamy klucz

    if l > 0 then vp [ i]^.left  := vp [ l ] // Ustawiamy lewego syna
    else          vp [ i]^.left  := nil;

    if r > 0 then vp [ i]^.right := vp [ r ] // Ustawiamy prawego syna
    else          vp [ i]^.right := nil;

  end;

  readBST := vp [ 0 ];      // Zapamiętujemy korzeń

  SetLength ( vp, 0 );      // Usuwamy tablicę dynamiczną

end;

// Funkcja szuka w drzewie BST węzła o zadanym kluczu.
// Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie, 
// to zwraca wskazanie puste.
// Parametrami są:
// p - wskazanie korzenia drzewa BST
// k - klucz poszukiwanego węzła
//----------------------------------------------------
function findBST ( p : PBSTNode; k : integer ) : PBSTNode;
begin

  while( p <> nil ) and ( p^.key <> k ) do
    if k < p^.key then p := p^.left
    else               p := p^.right;

  findBST := p;
end;

// Funkcja zwraca wskazanie węzła o najmniejszym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
function minBST ( p : PBSTNode ) : PBSTNode;
begin
  if p <> nil then
    while p^.left <> nil do
      p := p^.left;

  minBST := p;
end;

// Funkcja zwraca wskazanie węzła o największym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
function maxBST ( p : PBSTNode ) : PBSTNode;
begin
  if p <> nil then
    while p^.right <> nil do
      p := p^.right;

  maxBST := p;
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease ( v : PBSTNode );
begin
  if v <> nil then
  begin
    DFSRelease ( v^.left );   // usuwamy lewe poddrzewo
    DFSRelease ( v^.right );  // usuwamy prawe poddrzewo
    dispose ( v );            // usuwamy sam węzeł
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  root, p : PBSTNode;
  k, mink, maxk : integer;

begin
  root := readBST;     // Odczytujemy drzewo BST

  if root <> nil then
  begin
    mink := minBST ( root)^.key; // Odczytujemy klucz minimalny
    maxk := maxBST ( root)^.key; // Odczytujemy klucz maksymalny

    // Przechodzimy przez kolejne wartości kluczy

    for k := mink to maxk do
    begin
      p := findBST ( root, k );  // szukamy węzła o kluczu k

      write ( 'KEY = ', k:3, ' : ' );

      if p <> nil then
      begin
        if( p^.left = nil ) and ( p^.right = nil ) then
          writeln ( 'LEAF' )
        else
          writeln ( 'INNER NODE' );
      end
      else writeln ( 'NONE' );

    end;
  end
  else writeln ( 'BST is empty!!!' );

  DFSRelease ( root ); // usuwamy drzewo z pamięci

end.
C++
// Wyszukiwanie w drzewie BST
// Data: 24.04.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typ węzłów drzewa BST

struct BSTNode
{
  BSTNode * left;
  BSTNode * right;
  int key;
};

// Funkcja wczytuje drzewo BST ze standardowego
// wejścia i zwraca wskazanie korzenia.
//-----------------------------------------------
BSTNode * readBST( )
{
  BSTNode ** vp;    // Tablica wskazań węzłów
  int key, l, r, i, n;

  cin >> n;         // Odczytujemy liczbę węzłów drzewa

  vp = new BSTNode * [ n ]; // Tworzymy dynamiczną tablicę wskazań węzłów

  // Tablicę dynamiczną wypełniamy wskazaniami węzłów, 
  // które również tworzymy dynamicznie

  for( i = 0; i < n; i++ ) vp [ i ] = new BSTNode;

  // Teraz wczytujemy definicję drzewa i tworzymy jego strukturę
  // w pamięci wypełniając odpowiednie pola węzłów.

  for( i = 0; i < n; i++ )
  {
    cin >> key >> l >> r; // Czytamy klucz, numer lewego i prawego syna

    vp [ i ] ->key = key; // Ustawiamy klucz

    vp [ i ] ->left  = l ? vp [ l ] : NULL; // Ustawiamy lewego syna

    vp [ i ] ->right = r ? vp [ r ] : NULL; // Ustawiamy prawego syna

  }

  BSTNode * p = vp [ 0 ]; // Zapamiętujemy korzeń

  delete [ ] vp;          // Usuwamy tablicę dynamiczną

  return p;
}

// Funkcja szuka w drzewie BST węzła o zadanym kluczu.
// Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie, 
// to zwraca wskazanie puste.
// Parametrami są:
// p - wskazanie korzenia drzewa BST
// k - klucz poszukiwanego węzła
//----------------------------------------------------
BSTNode * findBST ( BSTNode * p, int k )
{
  while( p && p->key != k )
    p = ( k < p->key ) ? p->left: p->right;

  return p;
}

// Funkcja zwraca wskazanie węzła o najmniejszym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
BSTNode * minBST ( BSTNode * p )
{
  if( p ) while( p->left ) p = p->left;

  return p;
}

// Funkcja zwraca wskazanie węzła o największym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
BSTNode * maxBST ( BSTNode * p )
{
  if( p ) while( p->right ) p = p->right;

  return p;
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease ( BSTNode * v )
{
  if( v )
  {
    DFSRelease ( v->left );  // usuwamy lewe poddrzewo
    DFSRelease ( v->right ); // usuwamy prawe poddrzewo
    delete v;                // usuwamy sam węzeł
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main( )
{
  BSTNode * root, * p;
  int k, mink, maxk;

  root = readBST( ); // Odczytujemy drzewo BST

  if( root )
  {
    mink = minBST ( root )->key; // Odczytujemy klucz minimalny
    maxk = maxBST ( root )->key; // Odczytujemy klucz maksymalny

    // Przechodzimy przez kolejne wartości kluczy

    for( k = mink; k <= maxk; k++ )
    {
      p = findBST ( root, k );   // szukamy węzła o kluczu k

      cout << "KEY = " << setw ( 3 ) <<  k << ": ";

      if( p )
      {
        if( !p->left && !p->right ) cout << "LEAF";
        else                        cout << "INNER NODE";
      }
      else cout << "NONE";

      cout << endl;
    }
  }
  else cout << "BST is empty!!!" << endl;

  DFSRelease ( root ); // usuwamy drzewo z pamięci

  return 0;
}
Basic
' Wyszukiwanie w drzewie BST
' Data: 24.04.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa BST

Type BSTNode
  left  As BSTNode Ptr
  right As BSTNode Ptr
  key   As Integer
End Type

' Funkcja wczytuje drzewo BST ze standardowego
' wejścia i zwraca wskazanie korzenia.
'-----------------------------------------------
Function readBST( ) As BSTNode Ptr

  Dim As BSTNode Ptr Ptr vp  ' Tablica wskazań węzłów
  Dim As Integer key, l, r, i, n

  Open Cons For Input As #1
  
  Input #1, n                ' Odczytujemy liczbę węzłów drzewa

  vp = new BSTNode Ptr [ n ] ' Tworzymy dynamiczną tablicę wskazań węzłów

  ' Tablicę dynamiczną wypełniamy wskazaniami węzłów, 
  ' które również tworzymy dynamicznie

  For i = 0 To n - 1
  	vp [ i ] = new BSTNode
  Next

  ' Teraz wczytujemy definicję drzewa i tworzymy jego strukturę
  ' w pamięci wypełniając odpowiednie pola węzłów.

  For i = 0 To n - 1
    Input #1, key, l, r      ' Czytamy klucz, numer lewego i prawego syna

    vp [ i ] ->key = key     ' Ustawiamy klucz

    If l > 0 Then
    	vp [ i ] ->left = vp [ l ] ' Ustawiamy lewego syna
    Else
    	vp [ i ] ->left = 0
    End If

    If r > 0 Then
    	vp [ i ] ->right = vp [ r ] ' Ustawiamy prawego syna
    Else
    	vp [ i ] ->right = 0
    End If

  Next
  
  Close #1
  
  readBST = vp [ 0 ]       ' Zapamiętujemy korzeń

  delete [ ] vp            ' Usuwamy tablicę dynamiczną

End Function

' Funkcja szuka w drzewie BST węzła o zadanym kluczu.
' Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie, 
' to zwraca wskazanie puste.
' Parametrami są:
' p - wskazanie korzenia drzewa BST
' k - klucz poszukiwanego węzła
'----------------------------------------------------
Function findBST ( p As BSTNode Ptr, k As Integer ) As BSTNode Ptr

  while( p <> 0 ) AndAlso ( p->key <> k )
    If k < p->key Then
    	p = p->Left
    Else
    	p = p->Right
    End If
  Wend
  
  Return p
  
End Function

' Funkcja zwraca wskazanie węzła o najmniejszym kluczu.
' Parametrem jest wskazanie korzenia drzewa BST.
'------------------------------------------------------
Function minBST ( p As BSTNode Ptr ) As BSTNode Ptr

  If p Then
    While p->Left
    	p = p->Left
    Wend
  End If

  Return p
End Function

' Funkcja zwraca wskazanie węzła o największym kluczu.
' Parametrem jest wskazanie korzenia drzewa BST.
'------------------------------------------------------
Function maxBST ( p As BSTNode Ptr ) As BSTNode Ptr

  If p Then
    While p->Right
    	p = p->Right
    Wend
  End If

  Return p
End Function

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease ( v As BSTNode Ptr )
  If v Then
    DFSRelease ( v->left )  ' usuwamy lewe poddrzewo
    DFSRelease ( v->right ) ' usuwamy prawe poddrzewo
    delete v                ' usuwamy sam węzeł
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As BSTNode Ptr root, p
Dim As Integer k, mink, maxk

root = readBST( )     ' Odczytujemy drzewo BST

If root Then
  
  mink = minBST ( root )->key ' Odczytujemy klucz minimalny
  maxk = maxBST ( root )->key ' Odczytujemy klucz maksymalny

    ' Przechodzimy przez kolejne wartości kluczy

  For k = mink To maxk
    
    p = findBST ( root, k ) ' szukamy węzła o kluczu k

    Print Using "KEY = ### : "; k;

    If p Then
      if( p->Left = 0 ) AndAlso ( p->Right = 0 ) Then
        Print "LEAF"
      Else
        Print "INNER NODE"
      End If
      
    Else
     Print "NONE"
    End If

  Next

Else

  Print "BST is empty!!!"

End If

DFSRelease ( root ) ' usuwamy drzewo z pamięci

End
Wynik:
12
9 1 2
5 3 4
15 5 6
4 7 0
7 8 9
10 0 10
18 0 11
1 0 0
6 0 0
8 0 0
12 0 0
19 0 0
KEY =   1 : LEAF
KEY =   2 : NONE
KEY =   3 : NONE
KEY =   4 : INNER NODE
KEY =   5 : INNER NODE
KEY =   6 : LEAF
KEY =   7 : INNER NODE
KEY =   8 : LEAF
KEY =   9 : INNER NODE
KEY =  10 : INNER NODE
KEY =  11 : NONE
KEY =  12 : LEAF
KEY =  13 : NONE
KEY =  14 : NONE
KEY =  15 : INNER NODE
KEY =  16 : NONE
KEY =  17 : NONE
KEY =  18 : INNER NODE
KEY =  19 : LEAF
Na początek:  podrozdziału   strony 

Następnik i poprzednik węzła w drzewie BST

Na początku rozdziału powiedzieliśmy, że kolejność węzłów w drzewie BST jest taka, iż w wyniku przejścia tego drzewa algorytmem in-order otrzymamy niemalejący ciąg kluczy. Przyjrzyjmy się dokładniej temu przejściu:

obrazek

Zauważ, że znalezienie następnika wcale nie wymaga porównywania węzłów. Mogą wystąpić trzy przypadki:

obrazek Przypadek 1:

Węzeł x  posiada prawego syna – następnikiem jest wtedy węzeł o minimalnym kluczu w poddrzewie, którego korzeniem jest prawy syn. Wykorzystujemy tutaj algorytm wyszukiwania węzła o najmniejszym kluczu w prawym poddrzewie.

obrazek Przypadek 2:

Węzeł x  nie posiada prawego syna. W takim przypadku, idąc w górę drzewa, musimy znaleźć pierwszego ojca, dla którego nasz węzeł leży w lewym poddrzewie. Tutaj również nie musimy porównywać węzłów. Po prostu idziemy w górę drzewa i w węźle nadrzędnym sprawdzamy, czy przyszliśmy od strony lewego syna. Jeśli tak, to węzeł ten jest następnikiem. Jeśli nie, to kontynuujemy marsz w górę drzewa. Wymaga to zapamiętywania adresów kolejno mijanych węzłów.

obrazek Przypadek 3:

Węzeł x nie posiada prawego syna. Idąc w górę drzewa, dochodzimy do korzenia, a następnie do adresu nil, który wskazuje pole up  korzenia drzewa BST. W takim przypadku węzeł x  jest węzłem o największym kluczu i nie posiada następnika.

Ponieważ będziemy musieli poruszać się w górę drzewa, węzły muszą posiadać pole up  prowadzące do ojca.

Algorytm znajdowania następnika węzła w drzewie BST – succBST ( p )

Wejście:

p  – wskazanie węzła na drzewie BST, dla którego poszukujemy następnika

Wyjście:

Wskazanie węzła będącego następnikiem węzła wejściowego lub nil, jeśli węzeł wejściowy nie ma następnika.
Zmienne pomocnicze:
r  –  wskazanie węzła
minBST ( w  )  –  znajduje element minimalny od węzła w

Lista kroków:

K01: Jeśli p = nil,
to zakończ z wynikiem
p
jeśli drzewo jest puste, kończymy
K02: Jeśli ( pright  ) ≠ nil,
to zakończ z wynikiem minBST ( pright  )
Przypadek 1: zwracamy węzeł minimalny od prawego syna
K03: r  ← ( pup  ) r wskazuje ojca p
K04: Dopóki ( r  ≠ nil ) obrazek ( p  = ( rright  ),
wykonuj kroki K05...K06
Przypadki 2 i 3, brak prawego syna
K05:     p  ← r przemieszczamy się w górę drzewa, aż trafimy na węzeł,
K06:     r  ← ( rup  ) dla którego p leży w lewej gałęzi
K07: Zakończ z wynikiem r zwracamy znaleziony węzeł lub nil, jeśli następnika nie ma

Algorytm znajdowania poprzednika jest lustrzanym odbiciem algorytmu znajdowania następnika ( dlaczego? ):

Algorytm znajdowania poprzednika węzła w drzewie BST – predBST ( p )

Wejście:

p  – wskazanie węzła na drzewie BST, dla którego poszukujemy poprzednika

Wyjście:

Wskazanie węzła będącego poprzednikiem węzła wejściowego lub nil, jeśli węzeł wejściowy nie ma następnika
Zmienne pomocnicze:
r  –  wskazanie węzła
maxBST ( w  )  –  znajduje element maksymalny od węzła w

Lista kroków:

K01: Jeśli p = nil,
to zakończ z wynikiem
p
jeśli drzewo jest puste, kończymy
K02: Jeśli ( pleft  ) ≠ nil,
to zakończ z wynikiem maxBST ( pleft  )
Przypadek 1: zwracamy węzeł maksymalny od lewego syna
K03: r  ← ( pup  ) r wskazuje ojca p
K04: Dopóki ( r  ≠ nil ) obrazek ( p  = ( rleft  ),
wykonuj kroki K05...K06
Przypadki 2 i 3, brak lewego syna
K05:     p  ← r przemieszczamy się w górę drzewa, aż trafimy na węzeł,
K06:     r  ← ( rup  ) dla którego p leży w prawej gałęzi
K07: Zakończ z wynikiem r zwracamy znaleziony węzeł lub nil, jeśli poprzednika nie ma

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wczytuje definicję drzewa binarnego, którego klucze są liczbami całkowitymi. Definicja drzewa wygląda następująco:

Pierwsza liczba określa n  – ilość węzłów w drzewie.
Kolejne n  wierszy zawiera po cztery liczby: klucz, numer ojca ( dla korzenia wartość jest nieistotna ), numer lewego syna, numer prawego syna.
Program wyznacza kolejne następniki i poprzedniki korzenia.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek     
12
9 0 1 2
5 0 3 4
15 0 5 6
4 1 7 0
7 1 8 9
10 2 0 10
18 2 0 11
1 3 0 0
6 4 0 0
8 4 0 0
12 5 0 0
19 6 0 0
Pascal
// Następnik i poprzednik w drzewie BST
// Data: 27.04.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------------

program sp_bst;

// Typ węzłów drzewa BST

type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up    : PBSTNode;
    left  : PBSTNode;
    right : PBSTNode;
    key   : integer;
  end;

// Funkcja wczytuje drzewo BST ze standardowego
// wejścia i zwraca wskazanie korzenia.
//-----------------------------------------------
function readBST : PBSTNode;
var
  vp : array of PBSTNode;   // Tablica wskazań węzłów
  key, u, l, r, i, n : integer;
begin

  read ( n );               // Odczytujemy liczbę węzłów drzewa

  SetLength ( vp, n );      // Tworzymy dynamiczną tablicę wskazań węzłów

  // Tablicę dynamiczną wypełniamy wskazaniami węzłów, 
  // które również tworzymy dynamicznie

  for i := 0 to n - 1 do new ( vp [ i ] );

  // Teraz wczytujemy definicję drzewa i tworzymy jego strukturę
  // w pamięci wypełniając odpowiednie pola węzłów.

  for i := 0 to n - 1 do
  begin

    read ( key, u, l, r );  // Czytamy klucz, numery ojca, lewego i prawego syna

    vp [ i]^.key := key;    // Ustawiamy klucz

    vp [ i]^.up := vp [ u ];// Ustawiamy ojca

    if l > 0 then vp [ i]^.left  := vp [ l ] // Ustawiamy lewego syna
    else          vp [ i]^.left  := nil;

    if r > 0 then vp [ i]^.right := vp [ r ] // Ustawiamy prawego syna
    else          vp [ i]^.right := nil;

  end;

  vp [ 0]^.up := nil;  // Korzeń nie posiada ojca

  readBST := vp [ 0 ]; // Zapamiętujemy korzeń

  SetLength ( vp, 0 ); // Usuwamy tablicę dynamiczną

end;

// Funkcja zwraca wskazanie węzła o najmniejszym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
function minBST ( p : PBSTNode ) : PBSTNode;
begin
  if p <> nil then
    while p^.left <> nil do
      p := p^.left;

  minBST := p;
end;

// Funkcja zwraca wskazanie węzła o największym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
function maxBST ( p : PBSTNode ) : PBSTNode;
begin
  if p <> nil then
    while p^.right <> nil do
      p := p^.right;

  maxBST := p;
end;

// Funkcja znajduje następnik węzła p
//-----------------------------------
function succBST ( p : PBSTNode ) : PBSTNode;
var
  r : PBSTNode;
begin
  succBST := nil;
  if p <> nil then
  begin
    if p^.right <> nil then succBST := minBST ( p^.right )
    else
    begin
      r := p^.up;
      while( r <> nil ) and ( p = r^.right ) do
      begin
        p := r;
        r := r^.up;
      end;
      succBST := r;
    end;
  end;
end;

// Funkcja znajduje poprzednik węzła p
//------------------------------------
function predBST ( p : PBSTNode ) : PBSTNode;
var
  r : PBSTNode;
begin
  predBST := nil;
  if p <> nil then
  begin
    if p^.left <> nil then predBST := maxBST ( p^.left )
    else
    begin
      r := p^.up;
      while( r <> nil ) and ( p = r^.left ) do
      begin
        p := r;
        r := r^.up;
      end;
      predBST := r;
    end;
  end;
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease ( v : PBSTNode );
begin
  if v <> nil then
  begin
    DFSRelease ( v^.left );   // usuwamy lewe poddrzewo
    DFSRelease ( v^.right );  // usuwamy prawe poddrzewo
    dispose ( v );            // usuwamy sam węzeł
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  root, p : PBSTNode;

begin
  root := readBST;     // Odczytujemy drzewo BST

  if root <> nil then
  begin

    write ( 'SUCCESORS    :' );

    p := root;

    while p <> nil do
    begin
      write ( p^.key:3 );
      p := succBST ( p );
    end;

    writeln;

    write ( 'PREDECCESORS :' );

    p := root;

    while p <> nil do
    begin
      write ( p^.key:3 );
      p := predBST ( p );
    end;

    writeln;

  end
  else writeln ( 'BST is empty!!!' );

  DFSRelease ( root );    // usuwamy drzewo z pamięci

end.
C++
// Następnik i poprzednik w drzewie BST
// Data: 27.04.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typ węzłów drzewa BST

struct BSTNode
{
  BSTNode *up, *left, *right;
  int key;
};

// Funkcja wczytuje drzewo BST ze standardowego
// wejścia i zwraca wskazanie korzenia.
//-----------------------------------------------
BSTNode * readBST( )
{
  BSTNode ** vp;   // Tablica wskazań węzłów
  int key, u, l, r, i, n;

  cin >> n;                  // Odczytujemy liczbę węzłów drzewa

  vp = new BSTNode * [ n ];  // Tworzymy dynamiczną tablicę wskazań węzłów

  // Tablicę dynamiczną wypełniamy wskazaniami węzłów, 
  // które również tworzymy dynamicznie

  for( i = 0; i < n; i++ ) vp [ i ] = new BSTNode;

  // Teraz wczytujemy definicję drzewa i tworzymy jego strukturę
  // w pamięci wypełniając odpowiednie pola węzłów.

  for( i = 0; i < n; i++ )
  {
    cin >> key >> u >> l >> r; // Czytamy klucz, numery ojca, lewego i prawego syna

    vp [ i ] ->key = key;      // Ustawiamy klucz

    vp [ i ] ->up  = vp [ u ]; // Ustawiamy ojca

    vp [ i ] ->left  = l ? vp [ l ] : NULL;  // Ustawiamy lewego syna

    vp [ i ] ->right = r ? vp [ r ] : NULL;  // Ustawiamy prawego syna

  }

  vp [ 0 ] ->up = NULL;      // Korzeń nie posiada ojca

  BSTNode * p = vp [ 0 ];    // Zapamiętujemy korzeń

  delete [ ] vp;             // Usuwamy tablicę dynamiczną

  return p;
}

// Funkcja zwraca wskazanie węzła o najmniejszym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
BSTNode * minBST ( BSTNode * p )
{
  if( p ) while( p->left ) p = p->left;

  return p;
}

// Funkcja zwraca wskazanie węzła o największym kluczu.
// Parametrem jest wskazanie korzenia drzewa BST.
//------------------------------------------------------
BSTNode * maxBST ( BSTNode * p )
{
  if( p ) while( p->right ) p = p->right;

  return p;
}

// Funkcja znajduje następnik węzła p
//-----------------------------------
BSTNode * succBST ( BSTNode * p )
{
  BSTNode * r;

  if( p )
  {
    if( p->right ) return minBST ( p->right );
    else
    {
      r = p->up;
      while( r && ( p == r->right ) )
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return p;
}

// Funkcja znajduje poprzednik węzła p
//------------------------------------
BSTNode * predBST ( BSTNode * p )
{
  BSTNode * r;

  if( p )
  {
    if( p->left ) return maxBST ( p->left );
    else
    {
      r = p->up;
      while( r && ( p == r->left ) )
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return p;
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease ( BSTNode * v )
{
  if( v )
  {
    DFSRelease ( v->left );  // usuwamy lewe poddrzewo
    DFSRelease ( v->right ); // usuwamy prawe poddrzewo
    delete v;                // usuwamy sam węzeł
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main( )
{
  BSTNode * root, * p;

  root = readBST( );     // Odczytujemy drzewo BST

  if( root )
  {

    cout << "SUCCESORS    :";

    for( p = root; p; p = succBST ( p ) ) cout << setw ( 3 ) << p->key;

    cout << endl << "PREDECCESORS :";

    for( p = root; p; p = predBST ( p ) ) cout << setw ( 3 ) << p->key;

    cout << endl;

  }
  else cout << "BST is empty!!!" << endl;

  DFSRelease ( root ); // usuwamy drzewo z pamięci

  return 0;
}
Basic
' Następnik i poprzednik w drzewie BST
' Data: 27.04.2013
' (C)2013 mgr Jerzy Wałaszek
'-------------------------------------

' Typ węzłów drzewa BST

Type BSTNode
  up As BSTNode Ptr
  Left As BSTNode Ptr
  Right As BSTNode Ptr
  key As Integer
End Type

' Funkcja wczytuje drzewo BST ze standardowego
' wejścia i zwraca wskazanie korzenia.
'-----------------------------------------------
Function readBST( ) As BSTNode Ptr

  Dim As BSTNode Ptr Ptr vp   ' Tablica wskazań węzłów
  Dim As Integer key, u, l, r, i, n

  Open Cons For Input As #1
  
  Input #1, n                ' Odczytujemy liczbę węzłów drzewa

  vp = new BSTNode Ptr [ n ] ' Tworzymy dynamiczną tablicę wskazań węzłów

  ' Tablicę dynamiczną wypełniamy wskazaniami węzłów, 
  ' które również tworzymy dynamicznie

  For i = 0 To n - 1
    vp [ i ] = new BSTNode
  Next

  ' Teraz wczytujemy definicję drzewa i tworzymy jego strukturę
  ' w pamięci wypełniając odpowiednie pola węzłów.

  For i = 0 To n - 1
  
    Input #1, key, u, l, r      ' Czytamy klucz, numery ojca, lewego i prawego syna

    vp [ i ] ->key = key        ' Ustawiamy klucz

    vp [ i ] ->up  = vp [ u ]   ' Ustawiamy ojca

    If l > 0 Then
    	vp [ i ] ->left = vp [ l ] ' Ustawiamy lewego syna
    Else
    	vp [ i ] ->left = 0
    End If

    If r > 0 Then
    	vp [ i ] ->right = vp [ r ] ' Ustawiamy prawego syna
    Else
    	vp [ i ] ->right = 0
    End If

  Next

  Close #1
  
  vp [ 0 ] ->up = 0        ' Korzeń nie posiada ojca

  readBST = vp [ 0 ]       ' Zapamiętujemy korzeń

  delete [ ] vp            ' Usuwamy tablicę dynamiczną

End Function

' Funkcja zwraca wskazanie węzła o najmniejszym kluczu.
' Parametrem jest wskazanie korzenia drzewa BST.
'------------------------------------------------------
Function minBST ( p As BSTNode Ptr ) As BSTNode Ptr

  If p Then
    While p->Left
    	p = p->Left
    Wend
  End If

  Return p
End Function

' Funkcja zwraca wskazanie węzła o największym kluczu.
' Parametrem jest wskazanie korzenia drzewa BST.
'------------------------------------------------------
Function maxBST ( p As BSTNode Ptr ) As BSTNode Ptr

  If p Then
    While p->Right
    	p = p->Right
    Wend
  End If

  Return p
End Function

' Funkcja znajduje następnik węzła p
'-----------------------------------
Function succBST ( ByVal p As BSTNode Ptr ) As BSTNode Ptr

  Dim As BSTNode Ptr r

  If p Then
    If p->Right Then
    	Return minBST ( p->right )
    Else
      r = p->up
      while( r <> 0 ) AndAlso ( p = r->right )
        p = r
        r = r->up
      Wend
      Return r
    End If
  End If
  Return p
End Function

' Funkcja znajduje poprzednik węzła p
'------------------------------------
Function predBST ( ByVal p As BSTNode Ptr ) As BSTNode Ptr

  Dim As BSTNode Ptr r

  If p Then
    If p->Left Then
    	Return maxBST ( p->Left )
    Else
      r = p->up
      while( r <> 0 ) AndAlso ( p = r->Left )
        p = r
        r = r->up
      Wend
      Return r
    End If
  End If
  Return p
End Function

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease ( v As BSTNode Ptr )
  If v Then
    DFSRelease ( v->left )  ' usuwamy lewe poddrzewo
    DFSRelease ( v->right ) ' usuwamy prawe poddrzewo
    delete v                ' usuwamy sam węzeł
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As BSTNode Ptr root, p

root = readBST( )     ' Odczytujemy drzewo BST

If root Then
  
  Print "SUCCESORS    :";

  p = root
  
  While p
    Print Using "###";p->key;
    p = succBST ( p )
  Wend

  Print
  Print "PREDECCESORS :";

  p = root
  
  While p
    Print Using "###";p->key;
    p = predBST ( p )
  Wend

  Print 

Else

  Print "BST is empty!!!"

End If

DFSRelease ( root ) ' usuwamy drzewo z pamięci

End
Wynik:
12
9 0 1 2
5 0 3 4
15 0 5 6
4 1 7 0
7 1 8 9
10 2 0 10
18 2 0 11
1 3 0 0
6 4 0 0
8 4 0 0
12 5 0 0
19 6 0 0
SUCCESORS    :  9 10 12 15 18 19
PREDECCESORS :  9  8  7  6  5  4  1
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.