Algorytmy i Struktury Danych - Przechodzenie drzew binarnych: BFS

Przechodzenie drzewa binarnego wszerz (ang. breadth-first search, BFS) polega na odwiedzaniu kolejnych węzłów leżących na kolejnych poziomach.

Najpierw odwiedzamy korzeń drzewa – węzeł nr 0, który znajduje się na poziomie 0. Dalej przechodzimy do jego synów i odwiedzamy węzły nr 1 i 2 na poziomie 1. W kolejnym kroku przechodzimy do poziomu 2 i odwiedzamy kolejno węzły nr 3, 4, 5 i 6. Operację tę kontynuujemy, aż do przejścia przez wszystkie węzły drzewa.

Tego typu przejście wymaga zapamiętywania wskazań węzłów w kolejce. Kolejka pozwala odczytywać umieszczone w niej elementy w tej samej kolejności, w jakiej zostały do niej wstawione, czyli jest jakby buforem opóźniającym. Prześledźmy przejście BFS przedstawione w poniższej tabelce (dane dopisujemy na koniec kolejki, czyli z prawej strony, a pobieramy z początku kolejki, czyli z lewej strony, kierunki są oczywiście umowne):

Kolejka	Przetworzone węzły	Opis
[A]		Umieszczamy w kolejce węzeł startowy, czyli A. Przejście wykonywane jest w pętli dotąd, aż kolejka stanie się pusta.
[B C]	A	Pobieramy z kolejki węzeł A. Odwiedzamy go. W kolejce umieszczamy synów węzła A, czyli węzły B i C.
[C D E]	A B	Pobieramy z kolejki węzeł B. Odwiedzamy go. W kolejce umieszczamy synów D i E.
[D E F G]	A B C	Pobieramy z kolejki węzeł C. Odwiedzamy go. W kolejce umieszczamy synów F i G.
[E F G H I]	A B C D	Pobieramy z kolejki węzeł D. Odwiedzamy go. W kolejce umieszczamy synów H i I.
[F G H I J]	A B C D E	Pobieramy z kolejki węzeł E. Odwiedzamy go. W kolejce umieszczamy syna J.
[G H I J K]	A B C D E F	Pobieramy z kolejki węzeł F. Odwiedzamy go. W kolejce umieszczamy syna K.
[H I J K]	A B C D E F G	Pobieramy z kolejki węzeł G. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
[I J K]	A B C D E F G H	Pobieramy z kolejki węzeł H. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
[J K]	A B C D E F G H I	Pobieramy z kolejki węzeł I. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
[K]	A B C D E F G H I J	Pobieramy z kolejki węzeł J. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
[pusta]	A B C D E F G H I J K	Pobieramy z kolejki węzeł K. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce. Kończymy przechodzenie drzewa, ponieważ kolejka jest już pusta. Drzewo zostało przebyte w całości.

Na poniższym rysunku zaznaczyliśmy linię przejścia przez kolejne węzły drzewa.

→ BFS →

Rozmiar kolejki nie przekracza 2^h, gdzie h jest wysokością drzewa.

Algorytm kolejkowy BFS dla drzewa binarnego

Wejście:

v : wskazanie węzła startowego drzewa binarnego.
h : wysokość drzewa.

Wyjście:

Przetworzenie wszystkich węzłów drzewa kolejnymi poziomami od strony lewej do prawej.

Elementy pomocnicze:

Q : kolejka, której elementy są wskazaniami węzłów drzewa. Długość kolejki jest równa 2^h.

Lista kroków:

K01: Utwórz pustą kolejkę Q
K02: Q.push(v) ; zapamiętujemy wskazanie węzła startowego w kolejce
K03: Dopóki Q.empty() = false, 
     wykonuj kroki K04…K08
K04:   v ← Q.front() ; pobieramy wskazanie węzła z początku kolejki
K05:   Q.pop() ; usuwamy pobrany element z kolejki
K06:   Odwiedź węzeł wskazywany przez v ; przetwarzamy węzeł
K07:   Jeśli v→left ≠ nil, ; jeśli węzeł ma lewego syna, 
       to Q.push(v→left) ; to umieszczamy jego wskazanie w kolejce
K08:   Jeśli v→right ≠ nil, ; jeśli węzeł ma prawego syna, 
       to Q.push(v→right) ; to umieszczamy jego wskazanie w kolejce
K09: 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 strukturę drzewa binarnego jak w przykładzie powyżej. Danymi węzłów są znaki A, B, C, … Po utworzeniu drzewa program przechodzi je za pomocą algorytmu BFS. Wykorzystuje obiekt prostej kolejki.

Pascal

// 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 q_empty : boolean;
      function q_front : PBTnode;
      procedure push(v : PBTnode);
      procedure q_pop;
  end;

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

// Konstruktor - tworzy tablicę dla kolejki
//-----------------------------------------
constructor Queue.init(x : integer);
begin
  n := x; // rozmiar kolejki
  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.q_empty : boolean;
begin
  if qcnt = 0 then
    q_empty := true
  else
    q_empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to nil
//-----------------------------
function Queue.q_front : PBTnode;
begin
  if qcnt = 0 then
    q_front := nil
  else
    q_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.q_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');

  KK : Queue; // kolejka
  v : PBTnode; // wskazanie węzła

begin
  KK.init(8); // rozmiar kolejki równy 2^3, 
  // gdzie 3 jest wysokością drzewa
  KK.push(@A); // w kolejce umieszczamy
  // wskazanie węzła A
  while not KK.q_empty do
  begin
    v := KK.q_front; // pobieramy z kolejki
    KK.q_pop; // pobrany element usuwamy
    write(v^.data, ' '); // odwiedzamy węzeł
    // w kolejce umieszczamy synów
    // węzła wskazywanego przez v
    if v^.left  <> nil then
      KK.push(v^.left); // lewy syn 
    if v^.right <> nil then
      KK.push(v^.right); // prawy syn 
  end;
  writeln;
  KK.destroy;
end.

C++

// 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 KK(8); // rozmiar kolejki równy 2^3, 
  // gdzie 3 jest wysokością drzewa
  BTnode * v; // wskazanie węzła
  KK.push(&A); // w kolejce umieszczamy
  // wskazanie węzła A
  while(!KK.empty())
  {
    v = KK.front(); // pobieramy element
    // z kolejki
    KK.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)
      KK.push(v->left); // lewy syn 
    if(v->right)
      KK.push(v->right); // prawy syn 
  }
  cout << endl;
  return 0;
}

Basic

' 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
    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 q_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
    q_front = 0
  Else
    q_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 KK As Queue = 8 ' rozmiar kolejki
' równy 2^3, gdzie 3 jest wysokością drzewa
Dim As BTnode Ptr v  ' wskazanie węzła
KK.push(@A) ' w kolejce umieszczamy
              ' wskazanie węzła A
While KK.empty() = 0
  v = KK.front() ' pobieramy element
  ' z kolejki
  KK.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 _
    KK.push(v->left) ' lewy syn 
  If v->Right Then _
    KK.push(v->right) ' prawy syn 
Wend
Print
End

Python (dodatek)

# Przechodzenie drzew binarnych BFS
# Data: 5.07.2024
# (C)2024 mgr Jerzy Wałaszek
# ----------------------------------


# Klasa węzłów drzewa
class BTnode:

    def __init__(self, l, r, v):
        self.left = l
        self.right = r
        self.data = v


# Klasa kolejki Queue
# ---------------------
class Queue:


    # Konstruktor
    def __init__(self, x):
        self.n = x
        self.q = [None] * x
        self.qptr = 0
        self.qcnt = 0


    # Destruktor
    def __del__(self):
        self.q = None


    # sprawdza, czy kolejka jest pusta
    def empty(self):
        return not self.qcnt


    # zwraca początek kolejki.
    # wartość specjalna to None
    def front(self):
        if self.qcnt:
            return self.q[self.qptr]
        return None


    # zapisuje do kolejki
    def push(self, v):
        if self.qcnt < self.n:
            i = self.qptr + self.qcnt
            if i >= self.n:
                i -= self.n
            self.q[i] = v
            self.qcnt += 1


    # usuwa z kolejki
    def pop(self):
        if self.qcnt:
            self.qcnt -= 1
            self.qptr += 1
            if self.qptr == self.n:
                self.qptr = 0


# tworzenie struktury drzewa
# rozpoczynamy od liści
g = BTnode(None, None, "G")
h = BTnode(None, None, "H")
i = BTnode(None, None, "I")
j = BTnode(None, None, "J")
k = BTnode(None, None, "K")
# tworzymy kolejnych ojców
d = BTnode(h, i, "D")
e = BTnode(j, None, "E")
f = BTnode(k, None, "F")
b = BTnode(d, e, "B")
c = BTnode(f, g, "C")
# tworzymy korzeń drzewa
a = BTnode(b, c, "A")
qq = Queue(8)  # rozmiar kolejki
# równy 2^3, gdzie 3
# jest wysokością drzewa
qq.push(a)  # w kolejce umieszczamy
# wskazanie węzła A
while not qq.empty():
    v = qq.front()  # pobieramy element
    # z kolejki
    qq.pop()  # pobrany element usuwamy
    # z kolejki
    print(v.data, end=" ")  # odwiedzamy węzeł
    # w kolejce umieszczamy synów węzła
    # wskazywanego przez v
    if v.left:
        qq.push(v.left)  # lewy syn
    if v.right:
        qq.push(v.right)  # prawy syn
print()

Wynik:

A B C D E F G H I J K

Na początek: podrozdziału 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.

Przechodzenie drzew binarnych – BFS