// 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
  cr, cl, cp : string;      // łańcuchy do znaków ramek

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

    s := Copy (sp, 1, length (sp)-2);
    writeln(s, sn, v^.key);

    s := sp;
    if sn = cl then s [length (s) - 1] := ' ';
    printBT (s+cp, cl, v^.left);
  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;

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

  w^.up  := p;     // Ojcem w jest zawsze 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;             // inicjujemy generator pseudolosowy

  root := nil;           // Tworzymy puste drzewo BST

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

  writeln; writeln;

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

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

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

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

  if(v)
  {
    s = sp;
    if(sn == cr) s [s.length() - 2] = ' ';
    printBT (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] = ' ';
    printBT (s + cp, cl, v->left);
  }
}

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

  w->up  = p;                // Ojcem węzła w jest zawsze węzeł wskazywany przez 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));  // inicjujemy generator pseudolosowy

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

  cout << endl << endl;

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

  return 0;
}

' 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

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

' Procedura wypisuje drzewo
'--------------------------
Sub printBT (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) = " "
    printBT (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) = " "
    printBT (s + cp, cl, v->Left)
  End If
End Sub

' 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
 
  w->up  = p             ' Ojcem węzła w jest zawsze węzeł wskazywany przez 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                ' inicjujemy generator pseudolosowy

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

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

End

// 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
  cr, cl, cp : string;      // łańcuchy do znaków ramek

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

    s := Copy (sp, 1, length (sp)-2);
    writeln(s, sn, v^.key);

    s := sp;
    if sn = cl then s [length (s) - 1] := ' ';
    printBT (s+cp, cl, v^.left);
  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;

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

  w^.up  := p;           // Ojcem 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 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 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;

// Procedura usuwa węzeł z drzewa BST
// root - referencja do zmiennej wskazującej węzeł
// X    - wskazanie węzła do usunięcia
//----------------------------------------------
procedure removeBST (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 := succBST (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
  Tk   : array [0..14] of integer;  // tablica kluczy węzłów
  i, x, i1, i2  : integer;
  root : PBSTNode;                    // korzeń drzewa BST

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;            // Inicjujemy generator pseudolosowy

  root := nil;          // Tworzymy puste drzewo BST

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

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

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

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

  writeln; writeln;

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

  writeln; writeln;

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

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

  writeln; writeln;

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

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

end.

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

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

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

  if(v)
  {
    s = sp;
    if(sn == cr) s [s.length() - 2] = ' ';
    printBT (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] = ' ';
    printBT (s + cp, cl, v->left);
  }
}

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

  w->up  = p;                // Ojcem węzła w jest zawsze węzeł wskazywany przez 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 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;
}

// Procedura usuwa węzeł z drzewa BST
// root - referencja do zmiennej wskazującej węzeł
// X    - wskazanie węzła do usunięcia
//----------------------------------------------
void removeBST (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 : succBST (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()
{
  int Tk [15];   // tablica kluczy węzłów
  int i, x, i1, i2;
  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));   // inicjujemy generator pseudolosowy

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

  for(i = 0; i < 100; i++) // Mieszamy tablicę
  {
    i1 = rand() % 15;       // Losujemy 2 indeksy
    i2 = rand() % 15;

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

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

  cout << endl << endl;

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

  cout << endl << endl;

  for(i = 0; i < 100; i++) // Ponownie mieszamy tablicę
  {
    i1 = rand() % 15; i2 = rand() % 15;
    x = Tk [i1]; Tk [i1] = Tk [i2]; Tk [i2] = x;
  }

  for(i = 0; i < 5; i++)   // Usuwamy 5 węzłów
  {
    cout << setw (3) << Tk [i];
    removeBST (root, findBST (root, Tk [i]));
  }

  cout << endl << endl;

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

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

  return 0;
}

' 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

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

' Procedura wypisuje drzewo
'--------------------------
Sub printBT (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) = " "
    printBT (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) = " "
    printBT (s + cp, cl, v->Left)
  End If
End Sub

' 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
 
  w->up  = p             ' Ojcem węzła w jest zawsze węzeł wskazywany przez 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 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 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

' Procedura usuwa węzeł z drzewa BST
' root - referencja do zmiennej wskazującej węzeł
' X    - wskazanie węzła do usunięcia
'----------------------------------------------
Sub removeBST (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 = succBST (X)

    ' Z wskazuje syna Y lub NULL

    If Y->Left Then Z = Y->left: Else Z = Y->Right

    ' 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 ***
' **********************

Dim As Integer Tk (14) ' tablica kluczy węzłów
Dim As Integer i, i1, i2
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                ' Inicjujemy generator pseudolosowy

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

For i = 1 To 100         ' Mieszamy tablicę
  i1 = Int (Rnd() * 15) ' Losujemy 2 indeksy
  i2 = Int (Rnd() * 15)
  Swap Tk (i1), Tk (i2) ' Wymieniamy Tk [i1] <--> Tk [i2]
Next

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

Print: Print

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

Print: Print

For i = 1 To 100         ' Ponownie ieszamy tablicę
  i1 = Int (Rnd() * 15): i2 = Int (Rnd() * 15)
  Swap Tk (i1), Tk (i2)
Next

For i = 0 To 4           ' Usuwamy 5 węzłów
  Print Using "###";Tk (i);
  removeBST (root, findBST (root, Tk (i)))
Next

Print: Print

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

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

End