// Przechodzenie drzew binarnych BFS
// Data: 23.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program BFS;

// Typ węzłów drzewa

type
  PBTNode = ^BTNode;
  BTNode  = record
    left  : PBTNode;
    right : PBTNode;
    data  : char;
  end;

// Typ tablicy wskazań węzłów

  TBTNode = array of PBTNode;

// Definicja typu obiektowego queue
//---------------------------------

  queue = object
    private
      n    : integer;    // rozmiar tablicy
      qptr : integer;    // wskaźnik początku kolejki
      qcnt : integer;    // licznik elementów
      Q    : TBTNode; // tablica dynamiczna wskazań węzłów drzewa

    public
      constructor init (x : integer);
      destructor destroy;
      function empty : boolean;
      function front : PBTNode;
      procedure push (v : PBTNode);
      procedure pop;
  end;

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

// Konstruktor - tworzy tablicę dla kolejki
//-----------------------------------------
constructor queue.init (x : integer);
begin
  n := x;
  SetLength (Q, x);
  qptr := 0;  // początek kolejki na początku tablicy
  qcnt := 0;  // pusta kolejka
end;

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
destructor queue.destroy;
begin
  SetLength (Q, 0);
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if qcnt = 0 then empty := true
  else empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to nil
//-----------------------------
function queue.front : PBTNode;
begin
  if qcnt = 0 then front := nil
  else             front := Q [qptr];

end;

// Zapisuje do kolejki
//--------------------
procedure queue.push (v : PBTNode);
var
  i : integer;
begin
  if qcnt < n then
  begin
    i := qptr + qcnt;
    if i >= n then dec (i, n);
    Q [i] := v;
    inc (qcnt);
  end;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
begin
  if qcnt > 0 then
  begin
    dec (qcnt);
    inc (qptr);
    if qptr = n then qptr := 0;
  end;
end;

// Tworzenie struktury drzewa rozpoczynamy od liści

var

  G : BTNode = (left:nil; right:nil; data:'G');
  H : BTNode = (left:nil; right:nil; data:'H');
  I : BTNode = (left:nil; right:nil; data:'I');
  J : BTNode = (left:nil; right:nil; data:'J');
  K : BTNode = (left:nil; right:nil; data:'K');

// Tworzymy kolejnych ojców

  D : BTNode = (left: @H; right: @I; data:'D');
  E : BTNode = (left: @J; right:nil; data:'E');
  F : BTNode = (left: @K; right:nil; data:'F');
  B : BTNode = (left: @D; right: @E; data:'B');
  C : BTNode = (left: @F; right: @G; data:'C');

// Korzeń drzewa

  A : BTNode = (left: @B; right: @C; data:'A');

  Q : queue;      // kolejka

  v : PBTNode; // wskazanie węzła

begin

  Q.init (8);   // rozmiar kolejki równy 2^3, gdzie 3 jest wysokością drzewa

  Q.push (@A);  // w kolejce umieszczamy wskazanie węzła A

  while not Q.empty do
  begin

    v := Q.front;  // pobieramy element z kolejki

    Q.pop;         // pobrany element usuwamy z kolejki

    write (v^.data, ' '); // odwiedzamy węzeł

    // w kolejce umieszczamy synów węzła wskazywanego przez v

    if v^.left  <> nil then Q.push (v^.left);  // lewy syn

    if v^.right <> nil then Q.push (v^.right); // prawy syn

  end;

  writeln;

  Q.destroy;

end.

// Przechodzenie drzew binarnych BFS
// Data: 23.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Typ węzłów drzewa

struct BTNode
{
  BTNode * left;
  BTNode * right;
  char data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    int n;           // rozmiar tablicy
    int qptr;        // wskaźnik początku kolejki
    int qcnt;        // licznik elementów
    BTNode * * Q; // tablica dynamiczna wskazań węzłów

  public:
    queue (int x); // konstruktor
    ~queue();     // destruktor
    bool empty (void);
    BTNode * front (void);
    void push (BTNode * v);
    void pop (void);
};

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

// Konstruktor - tworzy tablicę dla kolejki
//-----------------------------------------
queue::queue (int x)
{
  n = x;
  Q = new BTNode * [x]; // tworzymy tablicę x wskazań węzłów
  qptr = qcnt = 0;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
queue::~queue()
{
  delete [] Q;
}

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

// Zwraca początek kolejki.
// Wartość specjalna to NULL
//-----------------------------
BTNode * queue::front (void)
{
  if(qcnt) return Q [qptr];
  return NULL;
}

// Zapisuje do kolejki
//--------------------
void queue::push (BTNode * v)
{
  int i;
  if(qcnt < n)
  {
    i = qptr + qcnt++;
    if(i >= n) i -= n;
    Q [i] = v;
  }
}

// Usuwa z kolejki
//----------------
void queue::pop (void)
{
  if(qcnt)
  {
    qcnt--;
    qptr++;
    if(qptr == n) qptr = 0;
  }
}

// Tworzenie struktury drzewa rozpoczynamy od liści

BTNode G = {NULL, NULL, 'G'};
BTNode H = {NULL, NULL, 'H'};
BTNode I = {NULL, NULL, 'I'};
BTNode J = {NULL, NULL, 'J'};
BTNode K = {NULL, NULL, 'K'};

// Tworzymy kolejnych ojców

BTNode D = { &H,  &I, 'D'};
BTNode E = { &J, NULL, 'E'};
BTNode F = { &K, NULL, 'F'};
BTNode B = { &D,  &E, 'B'};
BTNode C = { &F,  &G, 'C'};

// Tworzymy korzeń drzewa

BTNode A = { &B,  &C, 'A'};

int main()
{
  queue Q (8);       // rozmiar kolejki równy 2^3, gdzie 3 jest wysokością drzewa

  BTNode * v;    // wskazanie węzła

  Q.push (&A);       // w kolejce umieszczamy wskazanie węzła A

  while(!Q.empty())
  {
    v = Q.front();  // pobieramy element z kolejki

    Q.pop();        // pobrany element usuwamy z kolejki

    cout << v->data << " "; // odwiedzamy węzeł

    // w kolejce umieszczamy synów węzła wskazywanego przez v

    if(v->left)  Q.push (v->left);  // lewy syn

    if(v->right) Q.push (v->right); // prawy syn

  }

  cout << endl;

  return 0;
}

' Przechodzenie drzew binarnych BFS
' Data: 23.01.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa

Type BTNode
  left As BTNode Ptr
  right As BTNode Ptr
  data As String * 1
End Type

' Definicja typu obiektowego queue
'---------------------------------

Type queue
  Private:
    n    As Integer            ' rozmiar tablicy
    qptr As Integer            ' wskaźnik początku kolejki
    qcnt As Integer            ' licznik elementów
    Q    As BTNode Ptr Ptr  ' tablica dynamiczna wskazań węzłów

  Public:
    Declare Constructor (ByVal x As Integer)
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As BTNode Ptr
    Declare Sub push (ByVal v As BTNode Ptr)
    Declare Sub pop()
End Type

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

' Konstruktor - tworzy tablicę dla kolejki
'-----------------------------------------
Constructor queue (ByVal x As Integer)
  n = x
  Q = New BTNode Ptr [x]
  qptr = 0
  qcnt = 0
End Constructor

' Destruktor - zwalnia tablicę dynamiczną
'----------------------------------------
Destructor queue()
  Delete [] Q
End Destructor

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

' Zwraca początek kolejki.
' Wartość specjalna to 0
'-----------------------------
Function queue.front() As BTNode Ptr
  If qcnt = 0 then
    front = 0
  Else
    front = Q [qptr]
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal v As BTNode Ptr)
  Dim i As Integer
  If qcnt < n then
    i = qptr + qcnt
    If i >= n Then i -= n
    Q [i] = v
    qcnt += 1
  End If
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  If qcnt > 0 Then
    qcnt -= 1
    qptr += 1
    If qptr = n Then qptr = 0
  End If
End Sub

' Tworzenie struktury drzewa rozpoczynamy od liści

Dim G As BTNode => (0, 0, "G")
Dim H As BTNode => (0, 0, "H")
Dim I As BTNode => (0, 0, "I")
Dim J As BTNode => (0, 0, "J")
Dim K As BTNode => (0, 0, "K")

' Tworzymy kolejnych ojców

Dim D As BTNode => (@H, @I, "D")
Dim E As BTNode => (@J, 0, "E")
Dim F As BTNode => (@K, 0, "F")
Dim B As BTNode => (@D, @E, "B")
Dim C As BTNode => (@F, @G, "C")

' Tworzymy korzeń drzewa

Dim A As BTNode => (@B, @C, "A")

Dim Q As queue = 8      ' rozmiar kolejki równy 2^3, gdzie 3 jest wysokością drzewa

Dim As BTNode Ptr v  ' wskazanie węzła

Q.push (@A)              ' w kolejce umieszczamy wskazanie węzła A

While Q.empty() = 0

  v = Q.front()         ' pobieramy element z kolejki

  Q.pop()               ' pobrany element usuwamy z kolejki

  Print v->Data;" ";    ' odwiedzamy węzeł

  ' w kolejce umieszczamy synów węzła wskazywanego przez v

  If v->Left  Then Q.push (v->left)  ' lewy syn

  If v->Right Then Q.push (v->right) ' prawy syn

Wend

Print

End