// 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 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 prawego syna, 
      // o ile takowy istnieje
      if k < p^.key then
      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;
end;

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

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

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

begin

  // Tworzymy puste drzewo BST
  root := nil;

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

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

  readln;
  writeln;

  // Przechodzimy drzewo algorytmem inorder
  inorder_bst(root);
  writeln;

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

end.

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

  // Drzewo puste?
  if(!p)
    // 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;
      }
}

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

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

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

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

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

  cout << endl;

  // Przechodzimy drzewo
  // algorytmem inorder
  inorder_bst(root);
  cout << endl;

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

  return 0;
}

' 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 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
  End If
End Sub

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

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

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

Open Cons For Input As #1

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

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

Close #1

Print

' Przechodzimy drzewo
' algorytmem inorder
inorder_bst(root)
print

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

End

// 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;
    // Klucz jest priorytetem
    key : integer;
    // Dane przechowywane przez węzeł
    Data: integer;
  end;

// Definicja typu obiektowego Queue
//----------------------------------
  Queue = object
    private
      // Korzeń drzewa BST
      root : PBSTnode;

    public
      constructor init;
      destructor destroy;
      function  q_empty : boolean;
      function  q_front : integer;
      function  q_frontprio: integer;
      procedure push(prio, v : integer);
      procedure q_pop;
  end;

//----------------------
// Metody obiektu Queue
//----------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor Queue.init;
begin
  root := nil;
end;

// Destruktor-usuwa listę z pamięci
//-----------------------------------
destructor Queue.destroy;
begin
  while root <> nil do
    q_pop;
end;

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

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function Queue.q_front : integer;
var
  p : PBSTnode;
begin
  // Jeśli drzewo nie jest puste, 
  // to szukamy największego elementu
  if root <> nil then
  begin
    p := root;
    while p^.right <> nil do
      p := p^.right;
    // i zwracamy jego wartość
    q_front := p^.data;
  end
  else
    // inaczej zwracamy wartość specjalną
    q_front := -MAXINT;
end;

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

// Zapisuje do kolejki
//--------------------
procedure Queue.push(prio, v : integer);
var
  w, p : PBSTnode;
begin
  // Tworzymy dynamicznie nowy węzeł
  new(w);
  // Zerujemy wskazania synów
  w^.left  := nil;
  w^.right := nil;
  // Wstawiamy priorytet
  w^.key   := prio;
  // Wstawiamy dane
  w^.Data:= v;
  // 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
      // prawego syna, 
      // o ile takowy istnieje
      if prio < p^.key then
      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;

// Usuwa z kolejki
//----------------
procedure Queue.q_pop;
var
  p : PBSTnode;
begin
  // Jeśli drzewo BST nie jest puste, 
  // to szukamy największego elementu
  if root <> nil then
  begin
    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
      // inaczej uaktualniamy korzeń drzewa
      root := p^.left;
    // zwalniamy pamięć
    dispose (p);
  end
end;

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

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

begin
  randomize;

  // Inicjujemy kolejkę priorytetową
  Q.init;

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

  writeln('----');

  // Pobieramy z kolejki kolejne elementy
  while not Q.q_empty do
  begin
    // Wypisujemy ich zawartość
    writeln(Q.q_front:2, ':', Q.q_frontprio);
    // i usuwamy z kolejki
    Q.q_pop;
  end;
  Q.destroy;
end.

// 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;
  // Klucz jest priorytetem
  int key;
  // Dane przechowywane przez węzeł
  int data;
};

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

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

// Destruktor - usuwa listę z pamięci
//-----------------------------------
Queue::~Queue()
{
  while(root) pop();
}

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

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

  // Jeśli drzewo nie jest puste, 
  // to szukamy największego elementu
  if(root)
  {
    for(p = root; p->right; p = p->right);
    // i zwracamy jego wartość
    return p->data;
  }
  else
    // inaczej zwracamy wartość specjalną
    return -MAXINT;
}

// Zwraca priorytet pierwszego elementu
//-------------------------------------
int Queue::frontprio()
{
  BSTnode * p;

  // Jeśli drzewo nie jest puste, 
  // to szukamy największego elementu
  if(root)
  {
    for(p = root; p->right; p = p->right);
    // i zwracamy jego priorytet, 
    // czyli klucz
    return p->key;
  }
  else
    // inaczej zwracamy wartość specjalną
    return -MAXINT;
}

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

  // Tworzymy dynamicznie nowy węzeł
  w = new BSTnode;
  // Zerujemy wskazania synów
  w->left = w->right = NULL;
  // Wstawiamy priorytet
  w->key = prio;
  // Wstawiamy dane
  w->data = v;
  // Wyszukujemy miejsce dla w, 
  // rozpoczynając od korzenia
  p = root;
  // Drzewo puste?
  if(!p)
    // 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
      // prawego syna, 
      // o ile takowy istnieje
      if(prio < p->key)
      {
        // Jeśli lewego syna nie ma, 
        if(!p->left)
        {
          // to 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 staje się
          // prawym synem 
          p->right = w;
          // Przerywamy pętlę while
          break;
        }
        else p = p->right;
      }

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

// Usuwa z kolejki
//----------------
void Queue::pop()
{
  BSTnode * p;

  // Jeśli drzewo BST nie jest puste, 
  // to szukamy największego elementu
  if(root)
  {
    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 się
    // lewy syn elementu
    if(p->up) p->up->right = p->left;
    else
      // inaczej uaktualniamy korzeń drzewa
      root = p->left;
    // zwalniamy pamięć
    delete p;
  }
}

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

  srand(time(NULL));

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

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

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

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

' Typ węzłów drzewa BST
'----------------------
Type BSTnode
  left  As BSTnode Ptr
  right As BSTnode Ptr
  up    As BSTnode Ptr
  ' Klucz jest priorytetem
  key As Integer
  ' Dane przechowywane przez węzeł
  data As integer
End Type

' Definicja typu obiektowego Queue
'----------------------------------
Type Queue
  Private:
    ' Korzeń drzewa BST
    root As BSTnode Ptr

  Public:
    Declare Constructor	
    Declare Destructor
    Declare Function q_empty As Integer
    Declare Function q_front As Integer
    Declare Function q_frontprio As Integer
    Declare Sub push(ByVal prio As integer, _
                       ByVal v As integer)
    Declare Sub q_pop
End Type

'----------------------
' Metody obiektu Queue
'----------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor Queue
  root = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor Queue
  While root
    q_pop
  Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function Queue.q_empty As Integer
  Return root = 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function Queue.q_front As Integer
  Dim As BSTnode Ptr p

  ' Jeśli drzewo nie jest puste, 
  ' to szukamy największego elementu
  If root Then
    p = root
    While p->Right
      p = p->Right
    Wend
    ' i zwracamy jego wartość
    Return p->Data
  Else
    ' inaczej zwracamy wartość specjalną
    Return -MAXINT
  End If
End Function

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function Queue.q_frontprio As Integer
  Dim As BSTnode Ptr p

  ' Jeśli drzewo nie jest puste, 
  ' to szukamy największego elementu
  If root Then
    p = root
    While p->Right
      p = p->Right
    Wend
    ' i zwracamy jego priorytet, 
    ' czyli klucz
    Return p->key
  Else
    ' inaczej zwracamy wartość specjalną
    Return -MAXINT
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub Queue.push(ByVal prio As Integer, _
                      ByVal v 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 priorytet
  w->key   = prio
  ' Wstawiamy dane
  w->data  = v
  ' 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
    ' Pętla nieskończona
    While 1
      ' W zależności od klucza idziemy
      ' do lewego lub prawego syna, 
      ' o ile takowy istnieje
      If prio < p->key Then
        ' Jeśli lewego syna nie ma, 
        If p->Left = 0 Then
          ' to w staje się
          ' lewym synem 
          p->left = w
          ' Przerywamy pętlę while
          Exit While
        Else
          p = p->Left
        End If
      Else
        ' Jeśli prawego syna nie ma, 
        if p->Right = 0 Then
          ' to w staje się prawym synem 
          p->right = w
          ' Przerywamy pętlę while
          Exit While
        Else
          p = p->Right
        End If
      End If
    Wend
  End If
  ' Rodzicem w jest zawsze p
  w->up = p
End Sub

' Usuwa z kolejki
'----------------
Sub Queue.q_pop
  Dim As BSTnode Ptr p

  ' Jeśli drzewo BST nie jest puste, 
  ' to szukamy największego elementu
  If root Then
    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
      ' inaczej uaktualniamy korzeń drzewa
      root = p->Left
    End If
    ' zwalniamy pamięć
    Delete p
  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.q_empty = 0
  Print Using "##:#";_
    Q.q_front;_
    Q.q_frontprio
  Q.q_pop
Wend
End