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

Proste zastosowania drzew BST

SPIS TREŚCI
Podrozdziały

Drzewa BST ( ang. Binary Search Tree – Drzewo Poszukiwań Binarnych ) są zwykle stosowane w aplikacjach, gdzie należy szybko wyszukiwać różne dane. Dobrze skonstruowane drzewo BST pozwala znaleźć dane w czasie O ( log n ). Oczywiście podobny czas uzyskamy stosując tablicę i algorytm wyszukiwania binarnego, jednakże tablice nie pozwalają na łatwe dołączanie i usuwanie elementów, ponieważ zajmują ciągły blok pamięci ( wstawienie nowego elementu wymaga rozsunięcia elementów tablicy, co zajmuje czas ). Drzewo BST jest natomiast strukturą dynamiczną, w której można tworzyć i usuwać efektywnie elementy.

Poniżej podajemy kilka wybranych zastosowań drzew BST.

Sortowanie

Drzewo BST można wykorzystać do stworzenia prostego algorytmu sortującego. Działa on w dwóch krokach. Najpierw z danych wejściowych budujemy odpowiednie drzewo BST ( dane nie powinny być w żaden sposób uporządkowane, inaczej otrzymamy zdegenerowane drzewo BST i efektywność sortowania spadnie ). Następnie drzewo przechodzimy algorytmem inorder i wyprowadzamy na wyjście dane przechowywane w odwiedzanych węzłach. Dane te będą uporządkowane rosnąco.


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 odczytuje z wejścia liczbę n, a następnie n  liczb. Z odczytanych liczb tworzy drzewo BST. Utworzone drzewo przechodzi algorytmem in-order, wypisując na wyjście klucze kolejno odwiedzanych węzłów.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):

29
14 23 16 27 24 17 10 2 29 5 22 7 25 1 11 13 8 15 21 6 9 26 19 28 3 20 12 18 4
Pascal
// Sortowanie BST
// Data: 5.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bst;

// Typ węzłów drzewa BST
//----------------------
type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    left, right : PBSTNode;
    key   : integer;
  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;

// Procedura wstawia do drzewa BST węzeł o kluczu k
//-------------------------------------------------
procedure insertBST ( var root : PBSTNode; k : integer );
var
  w, p : PBSTNode;
begin

  new ( w );             // Tworzymy dynamicznie nowy węzeł

  w^.left  := nil;       // Zerujemy wskazania synów
  w^.right := nil;
  w^.key := k;           // Wstawiamy klucz

  p := root;             // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if p = nil then        // Drzewo puste?
    root := w            // Jeśli tak, to w staje się korzeniem
  else
    while true do        // Pętla nieskończona
      if k < p^.key then // W zależności od klucza idziemy do lewego lub
      begin              // prawego syna, o ile takowy istnieje 
        if p^.left = nil then // Jeśli lewego syna nie ma, 
        begin
          p^.left := w;  // to w staje się lewym synem
          break;         // Przerywamy pętlę while
        end
        else p := p^.left;
      end
      else
      begin
        if p^.right = nil then // Jeśli prawego syna nie ma, 
        begin
          p^.right := w;  // to w staje się prawym synem
          break;          // Przerywamy pętlę while
        end
        else p := p^.right;
      end;
end;

// Rekurencyjna procedura inorder
//-------------------------------
procedure inorderBST ( v : PBSTNode );
begin
  if v <> nil then
  begin
    inorderBST ( v^.left );   // przechodzimy lewe poddrzewo
    write ( v^.key, ' ' );    // odwiedzamy węzeł
    inorderBST ( v^.right );  // przechodzimy prawe poddrzewo
  end;
end;

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

var
  i, n, x : integer;
  root  : PBSTNode;     // korzeń drzewa BST

begin

  root := nil;          // Tworzymy puste drzewo BST

  read ( n );           // Czytamy liczbę elementów

  for i := 1 to n do
  begin
    read ( x );         // Czytamy kolejne elementy
    insertBST ( root, x ); // i umieszczamy je w drzewie BST
  end;

  writeln;

  inorderBST ( root );  // Przechodzimy drzewo algorytmem inorder

  DFSRelease ( root );  // Usuwamy drzewo BST z pamięci

end.
C++
// Sortowanie BST
// Data: 5.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typ węzłów drzewa BST

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

// 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ł
  }
}

// Procedura wstawia do drzewa BST węzeł o kluczu k
//-------------------------------------------------
void insertBST ( BSTNode * & root, int k )
{
  BSTNode * w, * p;

  w = new BSTNode;           // Tworzymy dynamicznie nowy węzeł

  w->left = w->right = NULL; // Zerujemy wskazania synów
  w->key = k;                // Wstawiamy klucz

  p = root;                  // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if( !p )                   // Drzewo puste?
    root = w;                // Jeśli tak, to w staje się korzeniem
  else
    while( true )            // Pętla nieskończona
      if( k < p->key )       // W zależności od klucza idziemy do lewego lub
      {                      // prawego syna, o ile takowy istnieje
        if( !p->left )       // Jeśli lewego syna nie ma, 
        {
          p->left = w;       // to węzeł w staje się lewym synem
          break;             // Przerywamy pętlę while
        }
        else p = p->left;
      }
      else
      {
        if( !p->right )      // Jeśli prawego syna nie ma, 
        {
          p->right = w;      // to węzeł w staje się prawym synem
          break;             // Przerywamy pętlę while
        }
        else p = p->right;
      }
}

// Rekurencyjna procedura inorder
//-------------------------------
void inorderBST ( BSTNode * v )
{
  if( v )
  {
    inorderBST ( v->left );  // przechodzimy lewe poddrzewo
    cout << v->key << " ";   // odwiedzamy węzeł
    inorderBST ( v->right ); // przechodzimy prawe poddrzewo
  }
}

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

int main( )
{
  int i, n, x;
  BSTNode * root = NULL; // korzeń drzewa BST

  cin >> n;              // Czytamy liczbę elementów

  for( i = 0; i < n; i++ )
  {
    cin >> x;            // Czytamy kolejne elementy
    insertBST ( root, x ); // i umieszczamy je w drzewie BST
  }

  cout << endl;

  inorderBST ( root );   // Przechodzimy drzewo algorytmem inorder

  DFSRelease ( root );   // Usuwamy drzewo BST z pamięci

  return 0;
}
Basic
' Sortowanie BST
' Data: 5.05.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

' 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

' Procedura wstawia do drzewa BST węzeł o kluczu k
'-------------------------------------------------
Sub insertBST ( ByRef root As BSTNode Ptr, k As Integer )
	
  Dim As BSTNode Ptr w, p

  w = new BSTNode           ' Tworzymy dynamicznie nowy węzeł

  w->left  = 0              ' Zerujemy wskazania synów
  w->right = 0
  w->key = k                ' Wstawiamy klucz

  p = root                  ' Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  If p = 0 Then             ' Drzewo puste?
    root = w                ' Jeśli tak, to w staje się korzeniem
  Else
    Do                      ' Pętla nieskończona
      If k < p->key Then    ' W zależności od klucza idziemy do lewego lub
                            ' prawego syna, o ile takowy istnieje
        If p->Left = 0 Then ' Jeśli lewego syna nie ma, 
          p->left = w       ' to węzeł w staje się lewym synem
          Exit Do           ' Przerywamy pętlę
        Else
          p = p->Left
        End If
      Else
        If p->Right = 0 Then' Jeśli prawego syna nie ma, 
          p->right = w      ' to węzeł w staje się prawym synem
          Exit Do           ' Przerywamy pętlę
        Else
          p = p->Right
        End If
      End If
    Loop                    ' Koniec pętli
  End If
End Sub

' Rekurencyjna procedura inorder
'-------------------------------
Sub inorderBST ( v As BSTNode Ptr )
  If v  Then
    inorderBST ( v->left )  ' przechodzimy lewe poddrzewo
    print v->key;           ' odwiedzamy węzeł
    inorderBST ( v->right ) ' przechodzimy prawe poddrzewo
  End If
End Sub

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

Dim As Integer i, n, x
Dim As BSTNode Ptr root = 0 ' korzeń drzewa BST

Open Cons For Input As #1

Input #1, n              ' Czytamy liczbę elementów

For i = 1 To n
  Input #1, x            ' Czytamy kolejne elementy
  insertBST ( root, x )  ' i umieszczamy je w drzewie BST
Next

Close #1

Print

inorderBST ( root )      ' Przechodzimy drzewo algorytmem inorder

DFSRelease ( root )      ' Usuwamy drzewo BST z pamięci

End
Wynik:
29
14 23 16 27 24 17 10 2 29 5 22 7 25 1 11 13 8 15 21 6 9 26 19 28 3 20 12 18 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Na początek:  podrozdziału   strony 

Kolejka priorytetowa

Kolejka priorytetowa ( ang. priority queue ) jest strukturą danych, w której umieszczone dane posiadają priorytet. Odczyt danych z kolejki zawsze wykonywany jest wg najwyższego priorytetu. Istnieje wiele różnych implementacji kolejek priorytetowych. Możemy je oprzeć na drzewie BST. Dane do drzewa BST wprowadzamy w normalny sposób. Natomiast wyprowadzamy zawsze największy węzeł. Kolejkę zrealizujemy w postaci obiektu. W rzeczywistej implementacji należałoby zadbać o równoważenie drzewa BST – np. można zliczać węzły oraz mierzyć wysokość drzewa przy wstawianiu nowego elementu i jeśli przekroczy ona znacznie wartość log 2 n, dokonać zrównoważenia algorytmem DSW, albo po prostu dokonywać zrównoważenia po wstawieniu lub usunięciu zadanej liczby elementów. U nas tę opcję pominiemy, pozostawiając ją zdolniejszym czytelnikom.


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 tworzy 10 elementów o losowych priorytetach i umieszcza je w kolejce, po czym odczytuje zawartość kolejki i wyświetla ją w oknie konsoli.
Pascal
// Kolejka priorytetowa oparta na drzewie BST
// Data: 11.05.2013
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

program prioqueue;

// Definicja typu węzłów drzewa
//-------------------------------

// Typ węzłów drzewa BST
//----------------------
type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up, left, right : PBSTNode;
    key : integer;     // Klucz jest priorytetem
    data : integer;    // Dane przechowywane przez węzeł
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      root : PBSTNode; // Korzeń drzewa BST

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      function frontprio: integer;
      procedure push ( prio, v : integer );
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  root := nil;
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;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  DFSRelease ( root );
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  empty := root = nil;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
var
  p : PBSTNode;
begin
  if root <> nil then    // Jeśli drzewo nie jest puste, 
  begin                  // to szukamy największego elementu
    p := root;
    while p^.right <> nil do
      p := p^.right;

    front := p^.data;    // i zwracamy jego wartość

  end

  else front := -MAXINT; // inaczej zwracamy wartość specjalną

end;

// Zwraca priorytet pierwszego elementu
//-------------------------------------
function queue.frontprio : integer;
var
  p : PBSTNode;
begin
  if root <> nil then    // Jeśli drzewo nie jest puste, 
  begin                  // to szukamy największego elementu
    p := root;
    while p^.right <> nil do
      p := p^.right;
    frontprio := p^.key; // i zwracamy jego priorytet, czyli klucz
  end
  else frontprio := -MAXINT; // inaczej zwracamy wartość specjalną

end;

// Zapisuje do kolejki
//--------------------
procedure queue.push ( prio, v : integer );
var
  w, p : PBSTNode;
begin

  new ( w );                  // Tworzymy dynamicznie nowy węzeł

  w^.left  := nil;            // Zerujemy wskazania synów
  w^.right := nil;
  w^.key   := prio;           // Wstawiamy priorytet
  w^.data  := v;              // Wstawiamy dane

  p := root;                  // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if p = nil then             // Drzewo puste?
    root := w                 // Jeśli tak, to w staje się korzeniem
  else
    while true do             // Pętla nieskończona
      if prio < p^.key then   // W zależności od klucza idziemy do lewego lub
      begin                   // prawego syna, o ile takowy istnieje
        if p^.left = nil then // Jeśli lewego syna nie ma, 
        begin
          p^.left := w;       // to w staje się lewym synem
          break;              // Przerywamy pętlę while
        end
        else p := p^.left;
      end
      else
      begin
        if p^.right = nil then // Jeśli prawego syna nie ma, 
        begin
          p^.right := w;       // to w staje się prawym synem
          break;               // Przerywamy pętlę while
        end
        else p := p^.right;
      end;

  w^.up   := p;     // Ojcem w jest zawsze p
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PBSTNode;
begin
  if root <> nil then         // Jeśli drzewo BST nie jest puste, 
  begin                       // to szukamy największego elementu
    p := root;
    while p^.right <> nil do
      p := p^.right;

// Jeśli element ma lewego syna, to jego ojcem stanie się ojciec elementu

    if p^.left <> nil then p^.left^.up := p^.up;

// Jeśli element ma ojca, to jego prawym synem stanie sie lewy syn elementu

    if p^.up <> nil then p^.up^.right := p^.left
    else  root := p^.left;   // inaczej uaktualniamy korzeń drzewa

    dispose ( p );           // zwalniamy pamięć

  end
end;

//---------------
// Program główny
//---------------

var
  Q : queue;   // kolejka
  i, p, v : integer;

begin
  randomize;                 // Inicjujemy generator pseudolosowy

  Q.init;                    // Inicjujemy kolejkę priorytetową

  for i := 1 to 10 do        // Wstawiamy do kolejki 10 elementów
  begin                      // o różnych priorytetach.
    v := random ( 100 );
    p := random ( 10 );
    writeln ( v:2, ':', p );
    Q.push ( p, v );
  end;

  writeln ( '----' );

  while not Q.empty do       // Pobieramy z kolejki kolejne elementy
  begin
    writeln ( Q.front:2, ':', Q.frontprio ); // Wypisujemy ich zawartość
    Q.pop;                   // i usuwamy z kolejki
  end;

  Q.destroy;

end.
C++
// Kolejka priorytetowa oparta na drzewie BST
// Data: 11.05.2013
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu węzłów drzewa
//-------------------------------

// Typ węzłów drzewa BST
//----------------------

struct BSTNode
{
  BSTNode * up, * left, * right;
  int key;     // Klucz jest priorytetem
  int data;    // Dane przechowywane przez węzeł
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    BSTNode * root;    // Korzeń drzewa BST

  public:
    queue( );
    ~queue( );
    bool empty( );
    int front( );
    int frontprio( );
    void push ( int prio, int v );
    void pop( );
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue( )
{
  root = NULL;
}

// 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ł
  }
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue( )
{
  DFSRelease ( root );
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty( )
{
  return !root;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front( )
{
  BSTNode * p;

  if( root )           // Jeśli drzewo nie jest puste, 
  {                    // to szukamy największego elementu
    for( p = root; p->right; p = p->right ) ;

    return p->data;    // i zwracamy jego wartość
  }
  else return -MAXINT; // inaczej zwracamy wartość specjalną
}

// Zwraca priorytet pierwszego elementu
//-------------------------------------
int queue::frontprio( )
{
  BSTNode * p;

  if( root )           // Jeśli drzewo nie jest puste, 
  {                    // to szukamy największego elementu
    for( p = root; p->right; p = p->right ) ;

    return p->key;     // i zwracamy jego priorytet, czyli klucz
  }
  else return -MAXINT; // inaczej zwracamy wartość specjalną
}

// Zapisuje do kolejki
//--------------------
void queue::push ( int prio, int v )
{
  BSTNode * w, * p;

  w = new BSTNode;             // Tworzymy dynamicznie nowy węzeł

  w->left  =  w->right = NULL; // Zerujemy wskazania synów
  w->key  = prio;              // Wstawiamy priorytet
  w->data = v;                 // Wstawiamy dane

  p = root;                    // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if( !p )                     // Drzewo puste?
    root = w;                  // Jeśli tak, to w staje się korzeniem
  else
    while( true )              // Pętla nieskończona
      if( prio < p->key )      // W zależności od klucza idziemy do lewego lub
      {                        // prawego syna, o ile takowy istnieje
        if( !p->left )         // Jeśli lewego syna nie ma, 
        {
          p->left = w;         // to w staje się lewym synem
          break;               // Przerywamy pętlę while
        }
        else p = p->left;
      }
      else
      {
        if( !p->right )        // Jeśli prawego syna nie ma, 
        {
          p->right = w;        // to w staje się prawym synem
          break;               // Przerywamy pętlę while
        }
        else p = p->right;
      }

  w->up   = p;     // Ojcem w jest zawsze p
}

// Usuwa z kolejki
//----------------
void queue::pop( )
{
  BSTNode * p;

  if( root )         // Jeśli drzewo BST nie jest puste, 
  {                  // to szukamy największego elementu
    for( p = root; p->right; p = p->right ) ;

// Jeśli element ma lewego syna, to jego ojcem stanie się ojciec elementu

    if( p->left ) p->left->up = p->up;

// Jeśli element ma ojca, to jego prawym synem stanie sie lewy syn elementu

    if( p->up ) p->up->right = p->left;
    else root = p->left;   // inaczej uaktualniamy korzeń drzewa

    delete p;              // zwalniamy pamięć
  }
}

//---------------
// Program główny
//---------------
int main( )
{
  queue * Q = new queue;    // kolejka
  int i, p, v;

  srand ( time ( NULL ) );  // Inicjujemy generator pseudolosowy

  for( i = 0; i < 10; i++ ) // Wstawiamy do kolejki 10 elementów
  {                         // o różnych priorytetach.
    v = rand( ) % 100;
    p = rand( ) %  10;
    cout << setw ( 2 ) << v << ":" << p << endl;
    Q->push ( p, v );
  }

  cout << "----" << endl;

  while( !Q->empty( ) )       // Pobieramy z kolejki kolejne elementy
  {
    cout << setw ( 2 ) << Q->front( )
      << ":" << Q->frontprio( ) << endl; // Wypisujemy ich zawartość
    Q->pop( );                // i usuwamy z kolejki
  }

  delete Q;
}
Basic
' Kolejka priorytetowa oparta na drzewie BST
' Data: 11.05.2013
' (C)2020 mgr Jerzy Wałaszek
'------------------------------
const MAXINT As Integer = 2147483647

' Definicja typu węzłów drzewa
'-------------------------------

' Typ węzłów drzewa BST
'----------------------

Type BSTNode
  Left As BSTNode Ptr
  Right As BSTNode Ptr
  Up As BSTNode Ptr
  key As Integer  ' Klucz jest priorytetem
  Data As integer ' Dane przechowywane przez węzeł
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    root As BSTNode Ptr    ' Korzeń drzewa BST

  Public:
    Declare Constructor( )	
    Declare Destructor( )
    Declare Function empty( ) As Integer
    Declare Function front( ) As Integer
    Declare Function frontprio( ) As Integer
    Declare Sub push ( ByVal prio As integer, ByVal v As integer )
    Declare Sub pop( )
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue( )
  root = 0
End Constructor

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
sub DFSRelease ( ByVal 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

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue( )
  DFSRelease ( root )
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty( ) As Integer
  Return root = 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front( ) As Integer
  Dim As BSTNode Ptr p

  If root Then              ' Jeśli drzewo nie jest puste, to szukamy największego elementu
    p = root
    While p->Right
    	p = p->Right 
    Wend

    return p->Data          ' i zwracamy jego wartość
  Else
    Return -MAXINT          ' inaczej zwracamy wartość specjalną
  End If
End Function

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function queue.frontprio( ) As Integer
  Dim As BSTNode Ptr p

  If root Then              ' Jeśli drzewo nie jest puste, to szukamy największego elementu
    p = root
    While p->Right
    	p = p->Right 
    Wend

    Return p->key           ' i zwracamy jego priorytet, czyli klucz
  Else
    Return -MAXINT          ' inaczej zwracamy wartość specjalną
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push ( ByVal prio As Integer, ByVal v As Integer )
  Dim As BSTNode ptr w, p

  w = new BSTNode             ' Tworzymy dynamicznie nowy węzeł

  w->left  = 0                ' Zerujemy wskazania synów
  w->right = 0
  w->key   = prio             ' Wstawiamy priorytet
  w->data  = v                ' Wstawiamy dane

  p = root                    ' Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  If p = 0 Then               ' Drzewo puste?
    root = w                  ' Jeśli tak, to w staje się korzeniem
  Else
    While 1                   ' Pętla nieskończona
      if prio < p->key Then   ' W zależności od klucza idziemy do lewego lub
                              ' prawego syna, o ile takowy istnieje
        if p->Left = 0 Then   ' Jeśli lewego syna nie ma, 
          p->left = w         ' to w staje się lewym synem
          Exit While          ' Przerywamy pętlę while
        Else
          p = p->Left
        End If
      Else
        if p->Right = 0 Then  ' Jeśli prawego syna nie ma, 
          p->right = w        ' to w staje się prawym synem
          Exit While          ' Przerywamy pętlę while
        Else
          p = p->Right
        End If
      End If
    Wend
  End If
  w->up   = p                 ' Ojcem w jest zawsze p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop( )
  Dim As BSTNode Ptr p

  If root Then                ' Jeśli drzewo BST nie jest puste, 
                              ' to szukamy największego elementu
    p = root
    While p->Right
      p = p->Right 
    Wend

' Jeśli element ma lewego syna, to jego ojcem stanie się ojciec elementu

    if p->left Then p->left->up = p->up

' Jeśli element ma ojca, to jego prawym synem stanie sie lewy syn elementu

    If p->up Then
    	p->up->right = p->Left
    Else
      root = p->Left   ' inaczej uaktualniamy korzeń drzewa
    End If
    
    Delete p           ' zwalniamy pamięć
  End If
End Sub

'---------------
' Program główny
'---------------
Dim Q As queue
Dim As Integer i, p, v

Randomize

For i = 1 To 10
  v = Int ( Rnd( ) * 100 )
  p = Int ( Rnd( ) * 10 )
  Print Using "##:#";v;p
  Q.push ( p, v )
Next

Print "----"

While Q.empty( ) = 0
  Print Using "##:#";Q.front( );Q.frontprio( )
  Q.pop( )
Wend

End
Wynik:
33:9
39:6
83:9
71:6
61:5
86:4
 6:3
81:4
86:9
17:0
----
86:9
83:9
33:9
71:6
39:6
61:5
81:4
86:4
 6:3
17:0
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.