Algorytmy i Struktury Danych - Tworzenie drzew BST

Jeśli będziemy chcieli utworzyć drzewo BST, to staniemy przed koniecznością dodawania do niego nowych węzłów. Zasada pracy algorytmu dołączającego węzeł jest następująca:

Jeśli drzewo jest puste, to nowy węzeł staje się jego korzeniem.

W przeciwnym razie porównujemy klucz wstawianego węzła z kluczami kolejnych węzłów, idąc w dół drzewa. Jeśli klucz nowego węzła jest mniejszy od klucza aktualnie odwiedzonego węzła w drzewie, to przechodzimy do lewego syna. Inaczej przechodzimy do prawego syna. Całą procedurę kontynuujemy do momentu, aż dany syn nie istnieje. Wtedy dołączamy nowy węzeł na jego miejsce i kończymy.

Algorytm wstawiania węzła do drzewa BST - insert_bst(root,k,d)

Wejście:

root : referencja do zmiennej wskazującej korzeń drzewa BST.
k : klucz dla wstawianego węzła.
d : dane dla wstawianego węzła.

Wyjście:

Drzewo BST z wstawionym nowym węzłem o kluczu k.

Elementy pomocnicze:

p, w : wskazanie węzłów.

Lista kroków:

K01: Utwórz nowy węzeł
K02: w ← adres nowego węzła
K03: w→left ← nil ; inicjujemy pola węzła
K04: w→right ← nil
K05: w→key ← k ; wstawiamy klucz i dane
     w→data ← d
K06: p ← root
K07: Jeśli p ≠ nil, ; sprawdzamy, czy drzewo jest puste
     to idź do kroku K11
K08: root ← w ; jeśli tak, to nowy węzeł staje się jego korzeniem
K09:   w→up ← p ; uzupełniamy ojca węzła
K10:   Zakończ
K11:   Jeśli k < p→key, ; porównujemy klucze
       to idź do kroku K15
K12:   Jeśli p→right = nil, ; jeśli prawy syn nie istnieje, to
       to p→right ← w ; nowy węzeł staje się prawym synem 
       i idź do kroku K09 ; i wychodzimy z pętli
K13:   p ← p→right ; inaczej przechodzimy do prawego syna 
K14:   Idź do K11 ; i kontynuujemy pętlę
K15:   Jeśli p→left = nil, ; to samo dla lewego syna 
       to p→left ← w
       i idź do kroku K09
K16:   p ← p→left
K17:   Idź do kroku K11

W zależności od kolejności wprowadzania danych do drzewa BST mogą powstać różne konfiguracje węzłów. Dla 3 kluczy możemy otrzymać aż pięć różnych drzew BST:

a) 1-2-3

b) 1-3-2

c) 2-1-3 / 2-3-1

d) 3-1-2

e) 3-2-1

Szczególnie niekorzystne jest wprowadzanie wartości uporządkowanych rosnąco lub malejąco – w takim przypadku otrzymujemy drzewo BST zdegenerowane do listy liniowej (pierwszy i ostatni przykład). W takim drzewie operacje wyszukiwania wymagają czasu rzędu O(n), a nie O(log n).

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 generuje 20 losowych kluczy z zakresu od 1 do 10, tworzy z nich węzły i wstawia do drzewa BST. Na koniec drzewo zostaje zaprezentowane algorytmem prezentacji drzew, który omówiliśmy we wcześniejszym artykule. Procedura wstawiania węzła do drzewa BST jest nieco zmodyfikowana – przyjmuje jako parametry referencję do zmiennej przechowującej adres korzenia oraz wartość klucza k. Sam węzeł jest tworzony dynamicznie wewnątrz procedury.

Pascal

// Budowanie drzewa BST
// Data: 1.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bst;

// Typ węzłów drzewa BST
type
  PBSTnode = ^BSTnode;
  BSTnode  = record
    up, left, right : PBSTnode;
    key   : integer;
  end;

// Zmienne globalne
var
  // łańcuchy do znaków ramek
  cr, cl, cp : string;

// Procedura wypisuje drzewo
//--------------------------
procedure print_bt(sp, sn : string;
                  v : PBSTnode);
var
  s : string;
  i : integer;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cr, v^.right);

    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(v^.key);

    s := sp;
    if sn = cl then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cl, v^.left);
  end;
end;

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

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

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

  // Zerujemy wskazania synów
  w^.left  := nil;
  w^.right := nil;
  // Wstawiamy klucz
  w^.key := k;
  // Wyszukujemy miejsce dla w, 
  // rozpoczynając od korzenia
  p := root;
  // Drzewo puste?
  if p = nil then
    // Jeśli tak, to w
    // staje się korzeniem
    root := w
  else
    // Pętla nieskończona
    while true do
      // W zależności od klucza
      // idziemy do lewego lub
      if k < p^.key then
      // prawego syna, 
      // o ile takowy istnieje
      begin
        // Jeśli lewego syna nie ma, 
        if p^.left = nil then
        begin
          // to w staje się lewym synem 
          p^.left := w;
          // Przerywamy pętlę while
          break;
        end
        else
          p := p^.left;
      end
      else
      begin
        // Jeśli prawego syna nie ma, 
        if p^.right = nil then
        begin
          // to w staje się prawym synem 
          p^.right := w;
          // Przerywamy pętlę while
          break;
        end
        else
          p := p^.right;
      end;
  // Rodzicem w jest zawsze p
  w^.up  := p;
end;

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

var
  root : PBSTnode;
  i, k  : integer;

begin
  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;

  // Tworzymy puste drzewo BST
  root := nil;

  // Wypełniamy drzewo BST węzłami
  for i := 1 to 20 do
  begin
    // Generujemy klucz 1…9
    k := 1+random(9);
    // Wyświetlamy klucz
    write(k, ' ');
    // Tworzymy nowy węzeł o kluczu k
    // i umieszczamy go w drzewie
    insert_bst(root, k);
  end;

  writeln; writeln;

  // Wyświetlamy drzewo
  print_bt('', '', root);
  // Usuwamy drzewo z pamięci
  dfs_release(root);
end.

C++

// Budowanie drzewa BST
// Data: 1.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Typ węzłów drzewa BST
struct BSTnode
{
  BSTnode *up, *left, *right;
  int key;
};

// Zmienne globalne
//-----------------

// łańcuchy do znaków ramek
string cr, cl, cp;

// Procedura wypisuje drzewo
//--------------------------
void print_bt(string sp, 
             string sn, 
             BSTnode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cr, v->right);

    s = s.substr(0, sp.length()-2);
    cout << s << sn << v->key
         << endl;

    s = sp;
    if(sn == cl)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cl, v->left);
  }
}

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

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

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

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

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

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

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

int main()
{
  BSTnode * root = NULL;
  int i, k;

  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  srand(time(NULL));

  // Wypełniamy drzewo BST węzłami
  for(i = 0; i < 20; i++)
  {
    // Generujemy klucz 1…9
    k = 1+rand()%9;
    // Wyświetlamy klucz
    cout << k << " ";
     // Tworzymy nowy węzeł o kluczu k
     // i umieszczamy go w drzewie
    insert_bst(root, k);
  }

  cout << endl << endl;

  // Wyświetlamy drzewo
  print_bt("", "", root);
  // Usuwamy drzewo z pamięci
  dfs_release(root);

  return 0;
}

Basic

' Budowanie drzewa BST
' Data: 1.05.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

' Zmienne globalne
'-----------------

' łańcuchy do ramek
Dim Shared As String * 2 cr, cl, cp

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(sp As String, _
            sn As String, _
            v As BSTnode Ptr)

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cr, v->Right)

    s = Mid (s, 1, Len(sp)-2)
    Print Using "&&&";s;sn;v->key

    s = sp
    If sn = cl Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

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

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

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

  ' Zerujemy wskazania synów
  w->left = 0
  w->right = 0
  ' Wstawiamy klucz
  w->key = k
  ' Wyszukujemy miejsce dla w, 
  ' rozpoczynając od korzenia
  p = root

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

End Sub

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

Dim As BSTnode Ptr root = 0
Dim As Integer i, k

' ustawiamy łańcuchy znakowe, 
' ponieważ nie wszystkie edytory
' pozwalają wstawiać znaki konsoli
' do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr (218)+Chr (196)
cl = Chr (192)+Chr (196)
cp = Chr (179)+" "

Randomize

' Wypełniamy drzewo BST węzłami
For i = 1 To 20
  ' Generujemy klucz 1…9
  k = 1+Int(Rnd()*9) 
  Print k; ' Wyświetlamy klucz
  ' Tworzymy nowy węzeł o kluczu k
  ' i umieszczamy go w drzewie BST
  insert_bst(root, k)
Next

Print
Print
 
' Wyświetlamy drzewo
print_bt("", "", root)
' Usuwamy drzewo z pamięci
dfs_release(root)

End

Python (dodatek)

# Budowanie drzewa BST
# Data: 15.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------

import random


# klasa węzłów drzewa
class BSTnode:


    def __init__(self, k):
        self.up    = None
        self.left  = None
        self.right = None
        self.key   = k

# zmienne globalne
#-----------------

# łańcuchy do ramek
cr = "┌─"
cl = "└─"
cp = "│ "


# procedura DFS:postorder
# usuwająca drzewo BST
#------------------------
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.up    = None
        v.left  = None
        v.right = None


# procedura wypisuje drzewo
#--------------------------
def print_bt(sp, sn, v):
    global cr, cl, cp
    if v:
        s = sp
        if sn == cr:
            s = s[:-2]+' '+s[-1]
        print_bt(s+cp, cr, v.right)
        s = s[:-2]
        print(s, sn, v.key, sep="")
        s = sp
        if sn == cl:
            s = s[:-2]+' '+s[-1]
        print_bt(s+cp, cl, v.left)


# Procedura wstawia do drzewa BST
# węzeł o kluczu k
# R - korzeń
#--------------------------------
def insert_bst(r, k):
    # Tworzymy dynamicznie nowy węzeł
    w = BSTnode(k)
    # Wyszukujemy miejsce dla w, 
    # rozpoczynając od korzenia
    p = r
    # Drzewo puste?
    if not p:
        # Jeśli tak, to w staje się
        # korzeniem
        r = w
    else:
        while True: # Pętla nieskończona
            # W zależności od klucza idziemy
            # do lewego lub prawego syna, 
            # o ile takowy istnieje
            if k < p.key:
                # Jeśli lewego syna nie ma, 
                if not p.left:
                    # to węzeł w staje się
                    # lewym synem 
                    p.left = w
                    break # Przerywamy pętlę
                else:
                    p = p.left
            else:
                # Jeśli prawego syna nie ma, 
                if not bool(p.right):
                    # to węzeł w staje się
                    # prawym synem 
                    p.right = w
                    break # Przerywamy pętlę
                else:
                    p = p.right
    # Rodzicem węzła w jest zawsze węzeł
    # wskazywany przez p
    w.up = p
    return r

#**********************
#*** PROGRAM GŁÓWNY ***
#**********************

# Korzeń
root = None
# Wypełniamy drzewo BST węzłami
for i in range(20):
    # Generujemy klucz 1…9
    k = random.randrange(1, 10)
    print(k, end=" ") # Wyświetlamy klucz
    # Tworzymy nowy węzeł o kluczu k
    # i umieszczamy go w drzewie BST
    root = insert_bst(root, k)
print()
print()
# wyświetlamy drzewo
print_bt("", "", root)
# usuwamy drzewo z pamięci
dfs_release(root)

Wynik:

3 5 2 9 4 1 7 5 9 8 3 4 1 8 8 5 2 6 1 3

    ┌─9
  ┌─9
  │ │     ┌─8
  │ │   ┌─8
  │ │ ┌─8
  │ └─7
  │   │   ┌─6
  │   │ ┌─5
  │   └─5
┌─5
│ │ ┌─4
│ └─4
│   │ ┌─3
│   └─3
3
│ ┌─2
└─2
  │   ┌─1
  │ ┌─1
  └─1

do podrozdziału do strony

Węzły usuwamy z drzewa BST, tak aby została zachowana hierarchia powiązań węzłów. Musimy rozpatrzyć kilka przypadków.

	Przypadek 1: Usuwany węzeł jest liściem, tzn. nie posiada synów. W takim przypadku po prostu odłączamy go od drzewa i usuwamy.
	Przypadek 2: Usuwany węzeł posiada tylko jednego syna. Węzeł zastępujemy jego synem, po czym sam węzeł usuwamy z pamięci.
	Przypadek 3: Najbardziej skomplikowany jest przypadek trzeci, gdy usuwany węzeł posiada dwóch synów. W takim przypadku znajdujemy węzeł będący następnikiem usuwanego węzła. Przenosimy dane i klucz z następnika do usuwanego węzła, po czym następnik usuwamy z drzewa – do tej operacji można rekurencyjnie wykorzystać tę samą procedurę lub zastąpić następnik przez jego prawego syna (następnik nigdy nie posiada lewego syna). Jako wariant można również zastępować usuwany węzeł jego poprzednikiem.

Algorytm usuwania węzła z drzewa BST - remove_bst(root,x)

Wejście:

root : referencja do zmiennej wskazującej węzeł drzewa BST, który jest korzeniem poddrzewa z węzłem o kluczu k.
x : wskazanie usuwanego węzła.

Wyjście:

Drzewo BST z usuniętym węzłem x.

Elementy pomocnicze:

y, z : wskazania węzła.
succ_bst(p) : zwraca wskazanie następnika węzła p.

Lista kroków:

K01: Jeśli (x→left = nil)(x→right = nil), ; y wskazuje węzeł
     to y ← x ; do usunięcia. Jeśli x nie ma synów lub ma tylko
     inaczej y ← succ_bst(x) ; jednego, to y jest x. W przeciwnym
     ; razie y jest bezpośrednim następnikiem x
K02: Jeśli y→left ≠ nil,
     to z ← z→left ; z jest synem y
     inaczej z ← y→right
K03: Jeśli z ≠ nil, ; Jeśli syn z istnieje, to jego ojcem 
     to z→up ← y→up ; staje się ojciec y
K04: Jeśli y→up ≠ nil, ; Sprawdzamy, czy usuwany węzeł jest
     to idź do kroku K07 ; korzeniem drzewa
K05: root ← z ; Jeśli tak, to korzeniem stanie się syn y
K06: Idź do kroku K08
K07: Jeśli y = y→up→left, ; Jeśli syn y nie jest korzeniem, 
     to y→up→left ← z ; to zastępuje Y w drzewie
     inaczej y→up→right ← z
K08: Jeśli y ≠ x, ; Jeśli y nie jest pierwotnym węzłem, 
     to przenieś dane z y do x ; to jest jego następnikiem
     ; i zamieniamy dane
K09: Usuń węzeł y ; Teraz możemy usunąć węzeł y z pamięci
K10: Zakończ

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 drzewo BST z 15 węzłów o kluczach od 1 do 15. Wyświetla je. Następnie usuwa z niego 5 losowych węzłów i wyświetla ponownie drzewo BST.

Pascal

// Usuwanie węzłów w drzewie BST
// Data: 1.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program bst;

// Typ węzłów drzewa BST
type
  PBSTnode = ^BSTnode;
  BSTnode  = record
    up, left, right : PBSTnode;
    key : integer;
  end;

// Zmienne globalne

var
  // łańcuchy do znaków ramek
  cr, cl, cp : string;

  // Procedura wypisuje drzewo
  //--------------------------
  procedure print_bt(sp, sn : string;
                    v : PBSTnode);
  var
    s : string;
    i : integer;
  begin
    if v <> nil then
    begin
      s := sp;
      if sn = cr then
        s[length(s)-1] := ' ';
      print_bt(s+cp, cr, v^.right);

      s := Copy(sp, 1, length(sp)-2);
      for i := 1 to length(s) do
        write(char(ord(s[i])));
      for i := 1 to length(sn) do
        write(char(ord(sn[i])));
      writeln(v^.key);

      s := sp;
      if sn = cl then
        s[length(s)-1] := ' ';
      print_bt(s+cp, cl, v^.left);
    end;
  end;

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

// Procedura wstawia do drzewa BST
// węzeł o kluczu k
//--------------------------------
procedure insert_bst(var root : PBSTnode;
                        k : integer);
var
  w, p : PBSTnode;
begin
  // Tworzymy dynamicznie nowy węzeł
  new(w);
  // Zerujemy wskazania synów
  w^.left  := nil;
  w^.right := nil;
  // Wstawiamy klucz
  w^.key := k;
  // Wyszukujemy miejsce dla w, 
  // rozpoczynając od korzenia
  p := root;
  // Drzewo puste?
  if p = nil then
    // Jeśli tak, to w staje się korzeniem
    root := w
  else
    // Pętla nieskończona
    while true do
      // W zależności od klucza
      // idziemy do lewego lub
      if k < p^.key then
      begin // prawego syna, 
        // o ile takowy istnieje
        // Jeśli lewego syna nie ma, 
        if p^.left = nil then
        begin
          // to w staje się lewym synem 
          p^.left := w;
          break; // Przerywamy pętlę while
        end
        else p := p^.left;
      end
      else
      begin
        // Jeśli prawego syna nie ma, 
        if p^.right = nil then
        begin
          // to w staje się prawym synem 
          p^.right := w;
          break; // Przerywamy pętlę while
        end
        else p := p^.right;
      end;
  w^.up  := p; // Rodzicem w jest zawsze p
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 find_bst(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;
  find_bst := p;
end;

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

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

// Procedura usuwa węzeł z drzewa BST
// root-referencja do zmiennej wskazującej
// węzeł
// x - wskazanie węzła do usunięcia
//----------------------------------------
procedure remove_bst(var root : PBSTnode;
                            x : PBSTnode);
var
  y, z : PBSTnode;
begin
  if x <> nil then
  begin
    // Jeśli x nie ma synów
    // lub ma tylko jednego, 
    // to y wskazuje x.
    // Inaczej y wskazuje następnik x
    if(x^.left = nil) or (x^.right = nil) then
      y := x
    else
      y := succ_bst(x);

    // Z wskazuje syna y lub nil
    if y^.left <> nil then
      z := y^.left
    else
      z := y^.right;

    // Jeśli syn y istnieje, 
    // to zastąpi y w drzewie
    if z <> nil then z^.up := y^.up;

    // y zostaje zastąpione przez z w drzewie
    if y^.up = nil then
      root := z
    else
      if y = y^.up^.left then
        y^.up^.left  := z
      else
        y^.up^.right := z;

    // Jeśli y jest następnikiem x, 
    // to kopiujemy dane
    if y <> x then x^.key := y^.key;

    Dispose(y);
  end;
end;

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

var
  // tablica kluczy węzłów
  Tk : array [0..14] of integer;
  i, x, i1, i2 : integer;
  // korzeń drzewa BST
  root : PBSTnode;

begin
  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory
  // pozwalają wstawiać znaki konsoli
  // do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;

  // Tworzymy puste drzewo BST
  root := nil;

  // Tablicę wypełniamy wartościami kluczy
  for i := 0 to 14 do
    Tk[i] := i+1;

  // Mieszamy tablicę
  for i := 1 to 100 do
  begin
    // Losujemy 2 indeksy
    i1 := random(15);
    i2 := random(15);

    // Wymieniamy Tk[i1] <--> Tk[i2]
    x := Tk[i1];
    Tk[i1] := Tk[i2];
    Tk[i2] := x;
  end;

  // Na podstawie tablicy tworzymy drzewo BST
  for i := 0 to 14 do
  begin
    write(' ', Tk[i]);
    insert_bst(root, Tk[i]);
  end;

  writeln;

  // Wyświetlamy zawartość drzewa BST
  print_bt('', '', root);

  writeln;

  // Ponownie mieszamy tablicę
  for i := 1 to 100 do
  begin
    i1 := random(15);
    i2 := random(15);
    x := Tk [i1];
    Tk[i1] := Tk[i2];
    Tk[i2] := x;
  end;

  // Usuwamy 5 węzłów
  for i := 0 to 4 do
  begin
    write(' ', Tk[i]);
    remove_bst(root, find_bst(root, Tk[i]));
  end;

  writeln;

  // Wyświetlamy zawartość drzewa BST
  print_bt('', '', root);

  // Usuwamy drzewo BST z pamięci
  dfs_release(root);
end.

C++

// Usuwanie węzłów w drzewie BST
// Data: 1.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

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

using namespace std;

// Typ węzłów drzewa BST
struct BSTnode
{
  BSTnode *up, *left, *right;
  int key;
};

// Zmienne globalne

// łańcuchy do znaków ramek
string cr, cl, cp;

// Procedura wypisuje drzewo
//--------------------------
void print_bt(string sp, 
              string sn, 
              BSTnode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cr, v->right);

    s = s.substr(0, sp.length()-2);
    cout << s << sn << v->key << endl;

    s = sp;
    if(sn == cl)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cl, v->left);
  }
}

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

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

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

  // Zerujemy wskazania synów
  w->left = w->right = NULL;
  // Wstawiamy klucz
  w->key = k;
  // Wyszukujemy miejsce dla w, 
  // rozpoczynając od korzenia
  p = root;

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

  // Rodzicem węzła w jest zawsze węzeł
  // wskazywany przez p
  w->up  = 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 * find_bst(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 * min_bst(BSTnode * p)
{
  if(p) while(p->left) p = p->left;
  return p;
}

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

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

// Procedura usuwa węzeł z drzewa BST
// root - referencja do zmiennej
//        wskazującej korzeń
// x - wskazanie węzła do usunięcia
//-----------------------------------
void remove_bst(BSTnode * & root, 
               BSTnode * x)
{
  BSTnode *y, *z;

  if(x)
  {
    // Jeśli x nie ma synów lub ma
    // tylko jednego, to y wskazuje x
    // Inaczej y wskazuje następnik x

    y = !x->left || !x->right ? x : succ_bst(x);

    // z wskazuje syna y lub NULL
    z = y->left ? y->left : y->right;

    // Jeśli syn y istnieje, 
    // to zastąpi y w drzewie
    if(z) z->up = y->up;

    // y zostaje zastąpione przez z w drzewie
    if(!y->up) root = z;
    else if(y == y->up->left)
           y->up->left  = z;
         else
           y->up->right = z;

    // Jeśli y jest następnikiem x, 
    // to kopiujemy dane

    if(y != x) x->key = y->key;

    delete y;
  }
}

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

int main()
{
  // tablica kluczy węzłów
  int Tk[15];
  int i;
  BSTnode * root = NULL;

  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory
  // pozwalają wstawiać znaki konsoli
  // do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  srand(time(NULL));

  // Tablicę wypełniamy wartościami kluczy
  for(i = 0; i < 15; i++)
    Tk[i] = i+1;

  // Mieszamy tablicę
  for(i = 0; i < 100; i++)
    swap(Tk[rand()%15], Tk[rand()%15]);

  // Na podstawie tablicy tworzymy drzewo BST
  for(i = 0; i < 15; i++)
  {
    cout << " " << Tk[i];
    insert_bst(root, Tk[i]);
  }
  cout << endl;

  // Wyświetlamy zawartość drzewa BST
  print_bt("", "", root);
  cout << endl ;

  // Ponownie mieszamy tablicę
  for(i = 0; i < 100; i++)
    swap(Tk[rand()%15], Tk[rand()%15]);

  // Usuwamy 5 węzłów
  for(i = 0; i < 5; i++)
  {
    cout << " " << Tk[i];
    remove_bst(root, find_bst(root, Tk[i]));
  }
  cout << endl;

  // Wyświetlamy zawartość drzewa BST
  print_bt("", "", root);

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

  return 0;
}

Basic

' Usuwanie węzłów w drzewie BST
' Data: 1.05.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

' Zmienne globalne

' łańcuchy do ramek
Dim Shared As String * 2 cr, cl, cp

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(sp As String, _
    sn As String, _
    v As BSTnode Ptr)
  Dim As String s

  If v Then
    s = sp
    If sn = cr Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cr, v->Right)

    s = Mid(s, 1, Len(sp)-2)
    Print Using "&&&";s;sn;v->key

    s = sp
    If sn = cl Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

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

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

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

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

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

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

' 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 find_bst(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 min_bst(p As BSTnode Ptr) _
                  As BSTnode Ptr
  If p Then
    While p->Left
      p = p->Left
    Wend
  End If
  Return p
End Function

' Funkcja znajduje następnik węzła p
'-----------------------------------
Function succ_bst(ByVal p As BSTnode Ptr) _
                         As BSTnode Ptr
  Dim As BSTnode Ptr r

  If p Then
    If p->Right Then
      Return min_bst(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

' Procedura usuwa węzeł z drzewa BST
' root - referencja do zmiennej
'        wskazującej korzeń
' x - wskazanie węzła do usunięcia
'-----------------------------------
Sub remove_bst(ByRef root As BSTnode Ptr, _
              ByVal x As BSTnode Ptr)
  Dim As BSTnode Ptr y, z

  If x Then
    ' Jeśli x nie ma synów lub ma
    ' tylko jednego, to y wskazuje x
    ' Inaczej y wskazuje następnik x
    If(x->Left = 0) OrElse _
      (x->Right = 0) Then
      y = x
    Else
      y = succ_bst(x)
    End If
    
    ' z wskazuje syna y lub NULL
    If y->Left Then
      z = y->left
    Else
      z = y->Right
    End If

    ' Jeśli syn y istnieje, 
    ' to zastąpi y w drzewie
    If z Then z->up = y->up

    ' y zostaje zastąpione
    ' przez z w drzewie
    If y->up = 0 Then
      root = z
    ElseIf y = y->up->Left Then
      y->up->left  = z
    Else
      y->up->right = z
    End If

    ' Jeśli y jest następnikiem x, 
    ' to kopiujemy dane
    If y <> x Then x->key = y->key

    Delete y
  End If
End Sub

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

' tablica kluczy węzłów
Dim As Integer Tk(14)
Dim As Integer i
Dim As BSTnode Ptr root = 0

' ustawiamy łańcuchy znakowe, 
' ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218)+Chr(196)
cl = Chr(192)+Chr(196)
cp = Chr(179)+" "

Randomize

' Tablicę wypełniamy wartościami kluczy
For i = 0 To 14
  Tk(i) = i+1
Next

' Mieszamy tablicę
For i = 1 To 100
  ' Wymieniamy Tk[?] <--> Tk[?]
  Swap Tk(Int (Rnd()*15)), _
       Tk(Int (Rnd()*15))
Next

' Na podstawie tablicy tworzymy drzewo BST
For i = 0 To 14
  Print Tk(i);
  insert_bst(root, Tk(i))
Next

Print

' Wyświetlamy zawartość drzewa BST
print_bt("", "", root)

Print

' Ponownie mieszamy tablicę
For i = 1 To 100
  Swap Tk(Int (Rnd()*15)), _
       Tk(Int (Rnd()*15))
Next

' Usuwamy 5 węzłów
For i = 0 To 4
  Print Tk(i);
  remove_bst(root, find_bst(root, Tk(i)))
Next

Print

' Wyświetlamy zawartość drzewa BST
print_bt("", "", root)

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

End

Python (dodatek)

# Usuwanie węzłów w drzewie BST
# Data: 16.07.2024
# (C)2024 mgr Jerzy Wałaszek
# ------------------------------

import random


# klasa węzłów drzewa
class BSTnode:

    def __init__(self, k):
        self.up = None
        self.left = None
        self.right = None
        self.key = k


# zmienne globalne
# -----------------

# łańcuchy do ramek
cr = "┌─"
cl = "└─"
cp = "│ "


# procedura wypisuje drzewo
# --------------------------
def print_bt(sp, sn, v):
    global cr, cl, cp
    if v:
        s = sp
        if sn == cr:
            s = s[:-2] + ' ' + s[-1]
        print_bt(s + cp, cr, v.right)
        s = s[:-2]
        print(s, sn, v.key, sep="")
        s = sp
        if sn == cl:
            s = s[:-2] + ' ' + s[-1]
        print_bt(s + cp, cl, v.left)


# procedura DFS:postorder
# usuwająca drzewo BST
# ------------------------
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.up = None
        v.left = None
        v.right = None


# Procedura wstawia do drzewa BST
# węzeł o kluczu k
# r - korzeń
# --------------------------------
def insert_bst(r, k):
    # Tworzymy dynamicznie nowy węzeł
    w = BSTnode(k)
    # Wyszukujemy miejsce dla w,
    # rozpoczynając od korzenia
    p = r
    # Drzewo puste?
    if not p:
        # Jeśli tak, to w staje się
        # korzeniem
        r = w
    else:
        while True:  # Pętla nieskończona
            # W zależności od klucza idziemy
            # do lewego lub prawego syna,
            # o ile takowy istnieje
            if k < p.key:
                # Jeśli lewego syna nie ma,
                if not p.left:
                    # to węzeł w staje się
                    # lewym synem
                    p.left = w
                    break  # Przerywamy pętlę
                else:
                    p = p.left
            else:
                # Jeśli prawego syna nie ma,
                if not p.right:
                    # to węzeł w staje się
                    # prawym synem
                    p.right = w
                    break  # Przerywamy pętlę
                else:
                    p = p.right

    # rodzicem węzła w jest zawsze węzeł
    # wskazywany przez p
    w.up = p
    return r


# 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.
# Parametrem jest:
# r - korzeń
# k - klucz poszukiwanego węzła
# ----------------------------------
def find_bst(r, k):
    while r and (r.key != k):
        if k < r.key:
            r = r.left
        else:
            r = r.right
    return r


# Funkcja zwraca wskazanie węzła
# o najmniejszym kluczu.
# r - korzeń
# -------------------------------
def min_bst(r):
    if r:
        while r.left:
            r = r.left
    return r


# Funkcja znajduje następnik węzła p
# -----------------------------------
def succ_bst(p):
    if p:
        if p.right:
            return min_bst(p.right)
        else:
            r = p.up
            while r and (p is r.right):
                p = r
                r = r.up
            return r
    return p


# Procedura usuwa węzeł z drzewa BST
# r - korzeń
# x - wskazanie węzła do usunięcia
# -----------------------------------
def remove_bst(r, x):
    if x:
        # Jeśli x nie ma synów lub ma
        # tylko jednego, to y wskazuje x
        # Inaczej y wskazuje następnik x
        if not x.left or not x.right:
            y = x
        else:
            y = succ_bst(x)
        # z wskazuje syna y lub NULL
        if y.left:
            z = y.left
        else:
            z = y.right
        # Jeśli syn y istnieje,
        # to zastąpi y w drzewie
        if z: z.up = y.up
        # y zostaje zastąpione
        # przez z w drzewie
        if not y.up:
            r = z
        elif y is y.up.left:
            y.up.left = z
        else:
            y.up.right = z
        # Jeśli y jest następnikiem x,
        # to kopiujemy dane
        if y is not x: x.key = y.key
    return r


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Korzeń
root = None
# tablica kluczy węzłów
tk = [i for i in range(1, 16)]
# Mieszamy tablicę
for i in range(100):
    # Wymieniamy tk[i1] <--> tk[i2]
    i1 = random.randrange(15)
    i2 = random.randrange(15)
    tk[i1], tk[i2] = tk[i2], tk[i1]
# Na podstawie tablicy
# tworzymy drzewo BST
for i in range(15):
    print("", tk[i], end="")
    root = insert_bst(root, tk[i])
print()
# Wyświetlamy zawartość drzewa BST
print_bt("", "", root)
print()
# Ponownie mieszamy tablicę
for i in range(100):
    i1 = random.randrange(15)
    i2 = random.randrange(15)
    tk[i1], tk[i2] = tk[i2], tk[i1]
# Usuwamy 5 węzłów
for i in range(5):
    print(tk[i], end=" ")
    root = remove_bst(root,
           find_bst(root, tk[i]))
print()
# Wyświetlamy zawartość drzewa BST
print_bt("", "", root)
# Usuwamy drzewo BST z pamięci
dfs_release(root)

Wynik:

 10 7 9 2 6 4 14 12 11 1 8 3 13 15 5
  ┌─15
┌─14
│ │ ┌─13
│ └─12
│   └─11
10
│ ┌─9
│ │ └─8
└─7
  │ ┌─6
  │ │ │ ┌─5
  │ │ └─4
  │ │   └─3
  └─2
    └─1

 6 4 1 2 13
  ┌─15
┌─14
│ └─12
│   └─11
10
│ ┌─9
│ │ └─8
└─7
  └─5
    └─3

do podrozdziału do strony

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.

Tworzenie drzew BST

Problem

Dołączanie nowego węzła do drzewa BST

Algorytm wstawiania węzła do drzewa BST - insert_bst(root,k,d)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Problem

Usuwanie węzła z drzewa BST

Algorytm usuwania węzła z drzewa BST - remove_bst(root,x)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy