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