Algorytmy i Struktury Danych - Przechodzenie drzew binarnych: DFS

W przejściu wzdłużnym (ang. preorder traversal) najpierw odwiedzamy korzeń poddrzewa, a następnie przechodzimy kolejno lewe i prawe poddrzewo. Prześledź poniższy przykład:

Stan przejścia	Przetworzone węzły	Opis
	A	Odwiedzamy korzeń A i przechodzimy do lewego syna B, który jest korzeniem lewego poddrzewa dla węzła A.
	A B	Odwiedzamy korzeń B poddrzewa i przechodzimy do lewego syna D, który jest korzeniem poddrzewa dla węzła B.
	A B D	Odwiedzamy D i przechodzimy do H.
	A B D H	Odwiedzamy H. Węzeł nie ma dzieci, zatem lewe poddrzewo dla węzła D (ojca H) zostało przebyte. Wracamy do węzła D i przechodzimy do I, który jest korzeniem prawego poddrzewa dla węzła D.
	A B D H I	Odwiedzamy I. Węzeł jest liściem, zatem prawe drzewo węzła D zostało przebyte. Jednocześnie zostało przebyte całe lewe poddrzewo węzła B. Wracamy do B i przechodzimy do E, które jest korzeniem prawego poddrzewa węzła B.
	A B D H I E	Odwiedzamy węzeł E i przechodzimy do lewego poddrzewa, czyli do węzła J.
	A B D H I E J	Wracamy do korzenia A, ponieważ całe lewe poddrzewo zostało przebyte. Teraz w analogiczny sposób odwiedzamy prawe poddrzewo, rozpoczynając od jego korzenia C.
	A B D H I E J C	Odwiedzamy C i przechodzimy do lewego poddrzewa.
	A B D H I E J C F	Odwiedzamy F i przechodzimy do lewego poddrzewa.
	A B D H I E J C F K	Odwiedzamy K i wracamy do C (lewe poddrzewo węzła C jest przebyte), a następnie przechodzimy do prawego poddrzewa.
	A B D H I E J C F K G	Odwiedzamy G. Drzewo zostało przebyte.

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

→ preorder →

Algorytm rekurencyjny DFS:preorder dla drzewa binarnego

Wejście:

s : wskazanie węzła startowego drzewa binarnego.

Wyjście:

Przetworzenie wszystkich węzłów drzewa w kolejności preorder.

Lista kroków:

K01: Jeśli s = nil, ; koniec rekurencji?
     to zakończ
K02: Odwiedź węzeł wskazany przez s
K03: preorder(s→left) ; przejdź rekurencyjnie
     ; przez lewe poddrzewo
K04: preorder(s→right) ; przejdź rekurencyjnie
     ; przez prawe poddrzewo
K05: 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 preorder, wypisując odwiedzane kolejno węzły.

Pascal

// Przechodzenie drzew binarnych
// rekurencyjne DFS:preorder
// Data: 17.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program DFS_preorder;

// Typ węzłów drzewa
type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: char;
  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');

  // Tworzymy korzeń drzewa
  A : BTnode = (left: @B; right: @C; data: 'A');


// Rekurencyjna procedura DFS:preorder
procedure preorder(v : PBTnode);
begin
  if v <> nil then
  begin
    write(v^.data, ' '); // przetwarzamy dane węzła
    preorder(v^.left);  // przechodzimy lewe poddrzewo
    preorder(v^.right); // przechodzimy prawe poddrzewo
  end;
end;

begin
  preorder(@A); // przejście rozpoczynamy od korzenia
  writeln;
end.

C++

// Przechodzenie drzew binarnych
// Rekurencyjne DFS:preorder
// Data: 17.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;
};

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

// Rekurencyjna funkcja preorder
void preorder(BTnode * v)
{
  if(v)
  {
    cout << v->data << " "; // przetwarzamy węzeł
    preorder(v->left); // przechodzimy lewe poddrzewo
    preorder(v->right); // przechodzimy prawe poddrzewo
  }
}

int main()
{
  preorder(&A); // przejście rozpoczynamy od korzenia
  cout << endl;
  return 0;
}

Basic

' Przechodzenie drzew binarnych DFS:preorder
' Data: 17.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

' 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")

' Rekurencyjna procedura preorder
Sub preorder(ByVal v As BTnode Ptr)
  If v Then
    Print v->Data;" "; ' odwiedzamy węzeł
    preorder(v->left)  ' przechodzimy lewe poddrzewo
    preorder(v->right) ' przechodzimy prawe poddrzewo
  End If
End Sub

preorder(@A) ' przejście rozpoczynamy od korzenia
Print

End

Python (dodatek)

# Przechodzenie drzew binarnych
# Rekurencyjne DFS:preorder
# Data: 3.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


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


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


# Rekurencyjna funkcja preorder
def preorder(v):
    if v:
        print(v.data, end=" ") # przetwarzamy węzeł
        preorder(v.left) # przechodzimy lewe poddrzewo
        preorder(v.right) # przechodzimy prawe poddrzewo


# 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')
preorder(a) # przejście rozpoczynamy od korzenia
print()

Wynik:

A B D H I E J C F K G

Algorytm stosowy DFS:preorder dla drzewa binarnego

Wejście:

v : wskazanie węzła startowego drzewa binarnego.

Wyjście:

Przetworzenie wszystkich węzłów drzewa w kolejności preorder.

Elementy pomocnicze:

S : stos wskazań węzłów, rozmiar stosu nie przekracza podwójnej wysokości drzewa.

Lista kroków:

K01: Utwórz pusty stos S
K02: S.push(v) ; zapamiętujemy wskazanie węzła startowego na stosie
K03: Dopóki S.empty() = false, ; w pętli przetwarzamy kolejne węzły
     wykonuj kroki K04…K08
K04:   v ← S.top() ; pobieramy ze stosu wskazanie węzła
K05:   S.pop() ; pobrane wskazanie usuwamy ze stosu
K06:   Odwiedź węzeł wskazany przez v ; przetwarzamy węzeł
K07:   Jeśli v→right ≠ nil, ; umieszczamy na stosie wskazanie
       to S.push(v→right)    ; prawego syna, jeśli istnieje
K08:   Jeśli v→left ≠ nil, ; to samo dla lewego syna 
       to S.push(v→left)     ; i kontynuujemy pętlę K03
       ; aż do wyczerpania stosu
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. Danymi węzłów są znaki A, B, C, … Po utworzeniu drzewa program przechodzi je za pomocą algorytmu preorder, wypisując odwiedzane kolejno węzły. Przy przechodzeniu drzewa korzysta z prostego stosu.

Pascal

// Przechodzenie drzew binarnych
// Stosowe DFS:preorder
// Data: 17.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program DFS_preorder;

// Typ węzłów drzewa
type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: char;
  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');

  S    : array [0..6] of PBTnode; // stos
  sptr : Integer; // wskaźnik stosu
  v    : PBTnode; // węzeł

begin

  S[0] := @A; // na stosie umieszczamy adres korzenia
  sptr := 1; // stos zawiera 1 element

  while sptr > 0 do
  begin
    dec(sptr);
    v := S[sptr]; // pobieramy ze stosu wskazanie węzła
    write(v^.data, ' '); // przetwarzamy węzeł

    // Na stosie umieszczamy wskazania synów, 
    // jeśli istnieją
    if v^.right <> nil then
    begin
      S[sptr] := v^.right;
      inc(sptr);
    end;
    if v^.left  <> nil then
    begin
      S[sptr] := v^.left;
      inc(sptr);
    end;
  end;
  writeln;
end.

C++

// Przechodzenie drzew binarnych
// Stosowe DFS:preorder
// Data: 17.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;
};

// 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()
{
  BTnode *v, *S[7]; // węzeł i stos
  int sptr; // wskaźnik stosu

  S[0] = &A; // na stosie umieszczamy wskazanie korzenia
  sptr = 1; // stos zawiera 1 element

  while(sptr) // dopóki stos coś zawiera
  {
    v = S[--sptr]; // pobieramy ze stosu wskazanie węzła
    cout << v->data << " ";  // przetwarzamy węzeł
    // na stosie umieszczamy wskazania synów, 
    // jeśli istnieją
    if(v->right) S[sptr++] = v->right;
    if(v->left)  S[sptr++] = v->left;
  }
  cout << endl;
  return 0;
}

Basic

' Przechodzenie drzew binarnych
' Stosowe DFS:preorder
' Data: 17.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

' 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 S(6) As BTnode Ptr ' stos
Dim sptr As Integer ' wskaźnik stosu
Dim v As BTnode Ptr ' wskaźnik węzła
 
S(0) = @A ' na stosie umieszczamy
          ' wskazanie korzenia
sptr = 1  ' stos zawiera 1 element

While sptr > 0
  sptr -= 1
  v = S (sptr) ' pobieramy ze stosu
               ' wskazanie węzła

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

  ' na stosie umieszczamy wskazania dzieci, 
  ' jeśli istnieją
  If v->Right Then
    S (sptr) = v->Right
    sptr += 1
  End If
  If v->Left Then
    S (sptr) = v->Left
    sptr += 1
  End If

Wend
Print
End

Python (dodatek)

# Przechodzenie drzew binarnych
# Stosowe DFS:preorder
# Data: 3.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


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


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


# 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')
s = [None]*6 # stos
# na stosie umieszczamy wskazanie korzenia
s[0] = a
sptr = 1 # stos zawiera 1 element
while sptr:
    sptr -= 1
    # pobieramy ze stosu wskazanie węzła
    v = s[sptr]
    # przetwarzamy węzeł
    print(v.data, end=" ")
    # na stosie umieszczamy wskazania dzieci, 
    # jeśli istnieją
    if v.right:
        s[sptr] = v.right
        sptr += 1
    if v.left:
        s[sptr] = v.left
        sptr += 1
print()

Wynik:

A B D H I E J C F K G

do podrozdziału do strony

W przejściu poprzecznym (ang. in-order traversal) najpierw przechodzimy lewe poddrzewo danego węzła, następnie odwiedzamy węzeł i na koniec przechodzimy prawe poddrzewo.

Stan przejścia	Przetworzone węzły	Opis
	H	Rozpoczynamy w korzeniu A. Jednakże węzła A nie przetwarzamy, lecz przechodzimy do lewego syna B. Tutaj dalej przechodzimy do D i H. Węzeł H nie ma synów, więc przechodzenie do lewego poddrzewa się kończy i węzeł H zostaje przetworzony jako pierwszy.
	H D	Lewe poddrzewo węzła D zostało przebyte, zatem przetwarzamy węzeł D i przechodzimy do prawego poddrzewa, którego korzeniem jest węzeł I.
	H D I	Węzeł I jest liściem, zatem nie posiada lewego poddrzewa. Przetwarzamy węzeł I.
	H D I B	Lewe poddrzewo węzła B zostało przebyte. Przetwarzamy węzeł B i przechodzimy do jego prawego poddrzewa rozpoczynającego się w węźle E.
	H D I B J	Będąc w węźle E najpierw przechodzimy jego lewe poddrzewo, czyli idziemy do węzła J. Węzeł J jest liściem i nie posiada dalszych poddrzew. Przetwarzamy J i wracamy do E.
	H D I B J E	Lewe poddrzewo węzła E zostało przebyte. Przetwarzamy węzeł E. Ponieważ nie posiada on prawego poddrzewa, wracamy do A.
	H D I B J E A	Lewe poddrzewo węzła A zostało przebyte. Przetwarzamy A i przechodzimy do prawego poddrzewa rozpoczynającego się od węzła C.
	H D I B J E A K	Będąc w węźle C przechodzimy do lewego poddrzewa rozpoczynającego się od węzła F, a tam dalej przechodzimy do następnego lewego poddrzewa, czyli do węzła K. Ten węzeł jest liściem i nie posiada dalszych poddrzew. Przetwarzamy K i wracamy do F.
	H D I B J E A K F	Lewe poddrzewo węzła F zostało przebyte. Przetwarzamy F. Ponieważ brak prawego poddrzewa, wracamy do C.
	H D I B J E A K F C	Lewe poddrzewo węzła C zostało przebyte, przetwarzamy C i przechodzimy do prawego poddrzewa, czyli do węzła G.
	H D I B J E A K F C G	Węzeł G jest liściem, przetwarzamy G i kończymy. Drzewo zostało przebyte.

→ inorder →

Algorytm rekurencyjny DFS:inorder dla drzewa binarnego

Wejście:

v : wskazanie węzła startowego drzewa binarnego.

Wyjście:

Przetworzenie wszystkich węzłów drzewa w kolejności inorder.

Lista kroków:

K01: Jeśli v = nil, ; koniec rekurencji
     to zakończ
K02:   inorder(v→left) ; przejście rekurencyjne
       ; przez lewe poddrzewo
K03:   Odwiedź węzeł wskazany przez v
K04:   inorder(v→right) ; przejście rekurencyjne
       ; przez prawe poddrzewo
K05: 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 poprzednim. Danymi węzłów są znaki A, B, C, … Po utworzeniu drzewa program przechodzi je za pomocą algorytmu inorder, wypisując odwiedzane kolejno węzły.

Pascal

// Przechodzenie drzew binarnych
// Rekurencyjne DFS:inorder
// Data: 17.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program DFS_inorder;

// Typ węzłów drzewa
type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: char;
  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');

  // Tworzymy korzeń drzewa
  A : BTnode = (left: @B; right: @C; data:'A');


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

begin
  inorder(@A); // przejście rozpoczynamy od korzenia
  writeln;
end.

C++

// Przechodzenie drzew binarnych
// Rekurencyjne DFS:inorder
// Data: 17.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;
};

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

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

int main()
{
  inorder(&A); // przejście rozpoczynamy od korzenia
  cout << endl;
  return 0;
}

Basic

' Przechodzenie drzew binarnych
' Rekurencyjne DFS:inorder
' Data: 17.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

' 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")

' Rekurencyjna procedura inorder
Sub inorder (ByVal v As BTnode Ptr)
  If v Then
    inorder(v->left)   ' przechodzimy lewe poddrzewo
    Print v->Data;" "; ' odwiedzamy węzeł
    inorder(v->right)  ' przechodzimy prawe poddrzewo
  End If
End Sub

inorder(@A) ' przejście rozpoczynamy od korzenia
Print
End

Python (dodatek)

# Przechodzenie drzew binarnych
# Rekurencyjne DFS:inorder
# Data: 3.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


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


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


# Rekurencyjna funkcja inorder
def inorder(v):
    if v:
        # przechodzimy lewe poddrzewo
        inorder(v.left)
        # przetwarzamy węzeł
        print(v.data, end=" ")
        # przechodzimy prawe poddrzewo
        inorder(v.right)


# 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')
# przejście rozpoczynamy od korzenia
inorder(a)
print()

Wynik:

H D I B J E A K F C G

Algorytm stosowy DFS:inorder dla drzewa binarnego

Algorytm wykorzystuje stos oraz dodatkowy wskaźnik cp, którym przemieszczamy się po drzewie.

Wejście:

v : wskazanie węzła startowego drzewa binarnego.

Wyjście:

Przetworzenie wszystkich węzłów drzewa w kolejności inorder.

Elementy pomocnicze:

S : stos wskazań węzłów, rozmiar stosu nie przekracza podwójnej wysokości drzewa.
cp : wskaźnik bieżącego węzła.

Lista kroków:

K01: Utwórz pusty stos S
K02: cp ← v ; bieżącym węzłem jest korzeń drzewa
K03: Dopóki (S.empty() = false)  (cp ≠ nil), ; pętla jest wykonywana, 
     wykonuj kroki K04…K11 ; jeśli jest coś na stosie
     ; lub cp wskazuje węzeł drzewa
K04:   Jeśli cp = nil, ; sprawdzamy, czy wyszliśmy poza liść drzewa
       to idź do kroku K07
K05:   S.push(cp) ; jeśli nie, to umieszczamy wskazanie bieżącego
       ; węzła na stosie
K06:   cp ← cp→left ; bieżącym węzłem staje się lewy syn 
K07:   Następny obieg pętli K02 ; wracamy na początek pętli
K08:   cp ← S.top() ; wyszliśmy poza liść, wracamy do węzła, 
       ; pobierając jego wskazanie ze stosu
K09:   S.pop() ; wskazanie usuwamy ze stosu
K10:   Odwiedź węzeł wskazany przez cp ; przetwarzamy dane w węźle
K11:   cp ← cp→right ; bieżącym węzłem staje się prawy syn 
K12: 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. Danymi węzłów są znaki A, B, C, … Po utworzeniu drzewa program przechodzi je za pomocą algorytmu inorder, wypisując odwiedzane kolejno węzły. Przy przechodzeniu drzewa korzysta z prostego stosu.

Pascal

// Przechodzenie drzew binarnych
// Stosowe DFS:inorder
// Data: 18.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program DFS_preorder;

// Typ węzłów drzewa
type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: char;
  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');

  S    : array [0..6] of PBTnode; // stos
  sptr : Integer; // wskaźnik stosu
  cp   : PBTnode; // wskaźnik bieżącego węzła

begin

  sptr := 0; // pusty stos
  cp := @A;  // cp ustawiamy na korzeń drzewa
  while(sptr > 0) or (cp <> nil) do
    if cp <> nil then
    begin
      S[sptr] := cp;  // umieszczamy cp na stosie
      inc(sptr);
      cp := cp^.left; // cp staje się lewym synem 
    end
    else
    begin
      dec(sptr);
      cp := S[sptr]; // pobieramy wskazanie ze stosu
      write(cp^.data, ' ');
      cp := cp^.right; // cp staje się prawym synem 
    end;
  writeln;
end.

C++

// Przechodzenie drzew binarnych
// Stosowe DFS:inorder
// Data: 18.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;
};

// 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()
{
  BTnode * cp, * S[7]; // stos
  int sptr = 0; // wskaźnik stosu

  cp = &A; // cp ustawiamy na korzeń drzewa

  while(sptr || cp)
    if(cp)
    {
      S[sptr++] = cp; // umieszczamy cp na stosie
      cp = cp->left;  // cp staje się lewym synem 
    }
    else
    {
      cp = S[--sptr]; // pobieramy wskazanie ze stosu
      cout << cp->data << " ";
      cp = cp->right; // cp staje się prawym synem 
    }
  cout << endl;
  return 0;
}

Basic

' Przechodzenie drzew binarnych
' Stosowe DFS:inorder
' Data: 17.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

' 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 S(6) As BTnode Ptr ' stos
Dim sptr As Integer  ' wskaźnik stosu
Dim cp As BTnode Ptr ' wskaźnik bieżącego węzła
 
sptr = 0 ' pusty stos
cp = @A ' cp ustawiamy na korzeń drzewa
while(sptr > 0) Or (cp <> 0)
  If cp Then
    S(sptr) = cp ' umieszczamy cp na stosie
    sptr += 1
    cp = cp->left ' cp staje się lewym synem 
  Else
    sptr -= 1
    cp = S (sptr) ' pobieramy wskazanie ze stosu
    Print cp->data;" ";
    cp = cp->right ' cp staje się prawym synem 
  End If
Wend
Print
End

Python (dodatek)

# Przechodzenie drzew binarnych
# Stosowe DFS:inorder
# Data: 4.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


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


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


# 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')
s = [None]*6
# pusty stos
sptr = 0
# cp ustawiamy na korzeń drzewa
cp = a
while sptr or cp:
    if cp:
        # umieszczamy cp na stosie
        s[sptr] = cp
        sptr += 1
        # cp staje się lewym synem
        cp = cp.left 
    else:
        sptr -= 1
        # pobieramy wskazanie ze stosu
        cp = s[sptr]
        print(cp.data, end=" ")
        # cp staje się prawym synem
        cp = cp.right 
print()

Wynik:

H D I B J E A K F C G

do podrozdziału do strony

W przejściu wstecznym (ang. postorder traversal) najpierw przechodzimy lewe poddrzewo, następnie prawe, a dopiero na końcu przetwarzamy węzeł.

Stan przejścia	Przetworzone węzły	Opis
	H	Rozpoczynamy w korzeniu A. Najpierw przechodzimy lewe poddrzewo. Idziemy do B. Tutaj również przechodzimy lewe poddrzewo i idziemy do D, a następnie do H. Węzeł H jest liściem i nie posiada poddrzew. Przetwarzamy H i wracamy do D.
	H I	Lewe poddrzewo węzła D jest przebyte, przechodzimy poddrzewo prawe. Idziemy do węzła I. Ponieważ jest on liściem, to nie posiada poddrzew. Przetwarzamy I. Wracamy do D.
	H I D	Oba poddrzewa węzła D zostały przebyte, przetwarzamy D i wracamy do B.
	H I D J	Dla węzła B przebyte zostało poddrzewo lewe. Teraz przechodzimy przez jego prawe poddrzewo. Idziemy do E i do J (lewe poddrzewo E). J jest liściem i nie posiada dalszych poddrzew, zatem przetwarzamy J i wracamy do E.
	H I D J E	Lewe poddrzewo węzła E zostało przebyte. Nie ma prawego poddrzewa dla E, zatem przetwarzamy E i wracamy do B.
	H I D J E B	Lewe i prawe poddrzewo węzła B jest przebyte. Przetwarzamy węzeł B i wracamy do A.
	H I D J E B K	Lewe poddrzewo węzła A zostało przebyte. Przechodzimy do prawego poddrzewa, czyli do węzła C, następnie do F (lewe poddrzewo C) i do K (lewe poddrzewo F). K jest liściem i nie posiada poddrzew. Przetwarzamy K i wracamy do F.
	H I D J E B K F	Lewe poddrzewo węzła F jest przebyte, a prawego poddrzewa brak. Przetwarzamy F i wracamy do C.
	H I D J E B K F G	Lewe poddrzewo węzła C jest przebyte, przechodzimy do poddrzewa prawego, czyli do węzła G. Węzeł G jest liściem i nie posiada poddrzew. Przetwarzamy G i wracamy do C.
	H I D J E B K F G C	Oba poddrzewa węzła C zostały przebyte. Przetwarzamy C i wracamy do A.
	H I D J E B K F G C A	Oba poddrzewa węzła A zostały przebyte. Przetwarzamy A i kończymy. Drzewo zostało przebyte.

→ postorder →

Algorytm rekurencyjny DFS:postorder dla drzewa binarnego

Wejście:

v : wskazanie węzła startowego drzewa binarnego.

Wyjście:

Przetworzenie wszystkich węzłów drzewa w kolejności postorder.

Lista kroków:

K01: Jeśli v = nil, ; koniec rekurencji?
     to zakończ
K02: postorder(v→left) ; przejdź rekurencyjnie przez
     ; lewe poddrzewo
K03: postorder(v→right) ; przejdź rekurencyjnie przez
     ; prawe poddrzewo
K04: Odwiedź węzeł wskazany przez v
K05: 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 postorder, wypisując odwiedzane kolejno węzły.

Pascal

// Przechodzenie drzew binarnych
// Rekurencyjne DFS:postorder
// Data: 19.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program DFS_postorder;

// Typ węzłów drzewa
type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: char;
  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');

  // Tworzymy korzeń drzewa
  A : BTnode = (left: @B; right: @C; data:'A');

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

begin
  postorder(@A); // przejście rozpoczynamy od korzenia
  writeln;
end.

C++

// Przechodzenie drzew binarnych
// Rekurencyjne DFS:postorder
// Data: 19.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;
};

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

// Rekurencyjna funkcja postorder
void postorder(BTnode * v)
{
  if(v)
  {
    postorder(v->left); // przechodzimy lewe poddrzewo
    postorder(v->right); // przechodzimy prawe poddrzewo
    cout << v->data << " "; // odwiedzamy węzeł
  }
}

int main()
{
  postorder (&A);  // przejście rozpoczynamy od korzenia
  cout << endl;
  return 0;
}

Basic

' Przechodzenie drzew binarnych
' Rekurencyjne DFS:postorder
' Data: 19.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

' 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")

' Rekurencyjna procedura postorder
Sub postorder(ByVal v As BTnode Ptr)
  If v Then
    postorder(v->left)  ' przechodzimy lewe poddrzewo
    postorder(v->right) ' przechodzimy prawe poddrzewo
    Print v->Data;" ";  ' odwiedzamy węzeł
  End If
End Sub

postorder(@A)  ' przejście rozpoczynamy od korzenia
Print
End

Python (dodatek)

# Przechodzenie drzew binarnych
# Rekurencyjne DFS:postorder
# Data: 4.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


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


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


# Rekurencyjna funkcja postorder
def postorder(v):
  if v:
    # przechodzimy lewe poddrzewo
    postorder(v.left)
    # przechodzimy prawe poddrzewo
    postorder(v.right)
    # odwiedzamy węzeł
    print(v.data, end=" ")


# 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')
# przejście rozpoczynamy od korzenia
postorder(a)
print()

Wynik:

H I D J E B K F G C A

Algorytm stosowy DFS:postorder dla drzewa binarnego

Algorytm wykorzystuje stos oraz dwa wskaźniki: pp – wskazanie poprzedniego węzła i cp – wskazanie bieżącego węzła. Są one używane do określenia, czy oba poddrzewa danego węzła zostały przebyte.

Wejście:

v : wskazanie węzła startowego drzewa binarnego.

Wyjście:

Przetworzenie wszystkich węzłów drzewa w kolejności postorder.

Elementy pomocnicze:

S : stos wskazań węzłów, rozmiar stosu nie przekracza podwójnej wysokości drzewa.
pp : wskaźnik węzła poprzedniego.
cp : wskaźnik węzła bieżącego.

Lista kroków:

K01: Utwórz pusty stos S
K02: S.push(v) ; węzeł startowy umieszczamy na stosie
K03: pp ← nil  ; zerujemy wskaźnik węzła poprzedniego
K04: Dopóki S.empty() = false, 
     wykonuj kroki K05…K14
K05:   cp ← S.top() ; ustawiamy cp na węzeł
       ; przechowywany na stosie
K06:   Jeśli (pp = nil)  (pp→left = cp)  (pp→right = cp), 
       to idź do kroku K11 ; sprawdzamy, czy idziemy
       ; w głąb drzewa
K07:   Jeśli cp→left = pp, ; sprawdzamy, czy wróciliśmy
       to idź do kroku K13   ; z lewego poddrzewa
K08:   Odwiedź węzeł wskazany przez cp ; oba poddrzewa przebyte, 
       ; przetwarzamy węzeł
K09:   S.pop() ; i usuwamy jego wskazanie ze stosu
K10:   Idź do kroku K14
K11:   Jeśli cp→left ≠ nil, ; jeśli istnieje lewy syn cp, 
       to S.push(cp→left) ; umieszczamy go na stosie
       inaczej jeśli cp→right ≠ nil, ; inaczej umieszczamy
               to S.push(cp→right) ; na stosie prawego syna, 
               ; jeśli istnieje
K12:   Idź do kroku K14
K13:   Jeśli cp→right ≠ nil, ; jeśli istnieje prawy syn, 
       to S.push(cp→right) ; to umieszczamy go na stosie
K14:   pp ← cp ; zapamiętujemy cp w pp
       ; i wykonujemy kolejny obieg pętli
K15: 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. Danymi węzłów są znaki A, B, C, … Po utworzeniu drzewa program przechodzi je za pomocą algorytmu postorder, wypisując odwiedzane kolejno węzły. Przy przechodzeniu drzewa korzysta z prostego stosu.

Pascal

// Przechodzenie drzew binarnych
// Stosowe DFS:postorder
// Data: 19.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program DFS_postorder;

// Typ węzłów drzewa
type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: char;
  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');

  S     : array [0..6] of PBTnode; // stos
  sptr  : Integer; // wskaźnik stosu
  pp, cp : PBTnode;

begin
  S[0] := @A; // węzeł startowy
  sptr := 1;
  pp := nil;

  while sptr > 0 do
  begin
    cp := S[sptr-1];
    if(pp = nil) or (pp^.left = cp) or
                    (pp^.right = cp) then
    begin
      if cp^.left <> nil then
      begin
        S[sptr] := cp^.left;
        inc(sptr);
      end
      else
        if cp^.right <> nil then
        begin
          S[sptr] := cp^.right;
          inc(sptr);
        end
    end
    else
      if cp^.left = pp then
      begin
        if cp^.right <> nil then
        begin
          S[sptr] := cp^.right;
          inc(sptr)
        end
      end
      else
      begin
        write(cp^.data, ' ');
        dec(sptr);
      end;
    pp := cp;
  end;
  writeln;
end.

C++

// Przechodzenie drzew binarnych
// Stosowe DFS:postorder
// Data: 19.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;
};

// 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()
{
  BTnode * S[7]; // stos
  int sptr; // wskaźnik stosu
  BTnode *pp, *cp;

  S[0] = &A; // węzeł startowy
  sptr = 1;
  pp = NULL;
  while(sptr)
  {
    cp = S[sptr-1];
    if(!pp || pp->left  == cp ||
              pp->right == cp)
    {
      if(cp->left)
        S[sptr++] = cp->left;
      else
        if(cp->right)
          S[sptr++] = cp->right;
    }
    else
      if(cp->left == pp)
      {
        if(cp->right)
          S[sptr++] = cp->right;
      }
      else
      {
        cout << cp->data << " ";
        sptr--;
      }
    pp = cp;
  }
  cout << endl;
  return 0;
}

Basic

' Przechodzenie drzew binarnych DFS:postorder
' Data: 19.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

' 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 S(6) As BTnode Ptr ' stos
Dim sptr As Integer ' wskaźnik stosu
Dim As BTnode Ptr pp, cp

S(0) = @A ' węzeł startowy
sptr = 1
pp = 0
While sptr > 0
  cp = S(sptr-1)
  if(pp = 0) OrElse (pp->left = cp) OrElse _
                    (pp->right = cp) Then
    If cp->Left Then
      S(sptr) = cp->Left
      sptr += 1
    ElseIf cp->Right Then
      S(sptr) = cp->Right
      sptr += 1	
    End If
  ElseIf cp->left = pp Then
    If cp->Right Then
      S(sptr) = cp->Right
      sptr += 1
    End If
  Else
    Print cp->data;" ";
    sptr -= 1
  End If
  pp = cp
Wend
Print
End

Python (dodatek)

# Przechodzenie drzew binarnych
# Stosowe DFS:postorder
# Data: 4.07.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


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


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


# 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')
s = [None]*6 # stos
s[0] = a # węzeł startowy
sptr = 1
pp = None
while sptr:
    cp = s[sptr-1]
    if not pp or pp.left  is cp or \
                 pp.right is cp:
        if cp.left:
            s[sptr] = cp.left
            sptr += 1
        elif cp.right:
            s[sptr] = cp.right
            sptr += 1	
    elif cp.left is pp:
        if cp.right:
            s[sptr] = cp.right
            sptr += 1
    else:
        print(cp.data, end=" ")
        sptr -= 1
    pp = cp
print()

Wynik:

H I D J E B K F G C A

do podrozdziału do strony

Drzewo binarne

przejście preorder

przejście inorder

przejście postorder

do podrozdziału do 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 – DFS

Problem

Algorytm DFS

DFS: preorder – przejście wzdłużne

Algorytm rekurencyjny DFS:preorder dla drzewa binarnego

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Algorytm stosowy DFS:preorder dla drzewa binarnego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

DFS: in-order – przejście poprzeczne

Algorytm rekurencyjny DFS:inorder dla drzewa binarnego

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Algorytm stosowy DFS:inorder dla drzewa binarnego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

DFS: postorder – przejście wsteczne

Algorytm rekurencyjny DFS:postorder dla drzewa binarnego

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Algorytm stosowy DFS:postorder dla drzewa binarnego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Podsumowanie