Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Prezentacja drzew binarnych

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy przedstawić w oknie konsoli strukturę drzewa binarnego.

Rozwiązanie

W rozdziale zaprojektujemy prosty sposób prezentacji drzew binarnych. Przedstawiamy go na poniższym rysunku

obrazek
    ┌─L
  ┌─G
┌─C
│ │ ┌─K
│ └─F 
A
│ ┌─E
│ │ └─J
└─B
  │ ┌─I
  └─D
    └─H

     
Znaki pomocnicze
Kod ASCII Znak
   179
   192
   195
   196
   218  
  └
 ├
 ─
 ┌

Każdy węzeł drzewa znajduje się w osobnym wierszu okna konsoli. Jeśli przyjrzymy się ich kolejności, to zauważymy, że są one w porządku odwrotnym do przejścia in-order. Taką kolejność przejścia węzłów uzyskamy przez odwrócenie w algorytmie in-order kolejności odwiedzania poddrzew:

zwykłe in-order   odwrotne in-order
K01: Jeśli v = nil, to zakończ
K02: inorder ( v→left )
K03: Odwiedź węzeł wskazany przez v
K04: inorder ( v→right )
K05: Zakończ
  K01: Jeśli v = nil, to zakończ
K02: inorder ( v→right )
K03: Odwiedź węzeł wskazany przez v
K04: inorder ( v→left )
K05: Zakończ

Położenie węzła w wierszu zależy od jego poziomu. Korzeń znajduje się w kolumnie 0. Węzły pierwszego poziomu znajdują się w kolumnie 2, węzły drugiego poziomu w kolumnie 4, następne w kolumnie 6, itd.

Od kolumny węzła do kolumny poprzedzającej syna jest zawsze wypisywany tekst:

┌─ dla prawego syna

└─ dla lewego syna

Dodatkowo musimy umieszczać znaki │ ponad i poniżej węzła, jeśli posiada on synów. Problem ten rozwiążemy łatwo zapamiętując w osobnej zmiennej sp  tekst, który należy wyświetlić w wierszach pośrednich. Poniżej przedstawiamy odpowiedni algorytm wraz z opisem poszczególnych operacji.

Algorytm drukowania drzewa binarnego w oknie konsoli printBT

Wejście:

sp  –  tekst do wyświetlenia w wierszu pośrednim
sn  –  tekst do wyświetlenia przed węzłem
v  –  wskazanie bieżącego węzła drzewa

Wyjście:

Wydruk drzewa
Zmienne pomocnicze:
s  –  tekst do wyświetlenia w wierszach pośrednich dla synów

Lista kroków:

K01: Jeśli v  = nil,
to zakończ
otrzymaliśmy puste wskazanie, nic nie robimy
K02: s  ← sp w s umieszczamy tekst dla wierszy pośrednich
K03: Jeśli sn  = "┌─",
to s [ | s | - 2 ] ← " "
dla prawego syna usuwamy z sn ostatni znak |
K04: printBT ( s + "│ ", "┌─", ( vright  ) ) wywołujemy algorytm rekurencyjnie dla prawego syna
K05: s  ← sp [ 0 : | s | - 2 ] w s umieszczamy sn bez ostatnich dwóch znaków, które zastąpi tekst przed węzłem
K06: Pisz s, sn, ( vdata  ) wypisujemy wiersz węzła
K07: s  ← sp powtarzamy operacje dla lewego syna
K08: Jeśli sn  = "└─",
to s [ | s | - 2 ] ← " "
dla lewego syna usuwamy z sn ostatni znak |
K09: printBT ( s + "│ ", "└─", ( vleft  ) ) wywołujemy algorytm rekurencyjnie dla lewego syna
K10: Zakończ  

Pierwsze wywołanie algorytmu powinno być z pustymi tekstami sp  i sn  oraz z v  wskazującym korzeń drzewa.


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 odczytuje ze standardowego wejścia definicję drzewa. Definicja składa się z liczby n  określającej ilość węzłów oraz n  trójek, które dla kolejnych węzłów oznaczają odpowiednio: zawartość węzła, numery lewego i prawego syna. Brak syna oznaczany jest liczbą 0. Na podstawie tej definicji program tworzy odpowiednie drzewo binarne, wyświetla je, a na koniec usuwa z pamięci.
Przykładowe dane ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek  
12
5 1 2
2 3 4
7 5 6
3 7 8
8 9 0
9 0 10
1 0 11
6 0 0
5 0 0
3 0 0
0 0 0
2 0 0
Pascal
// Prezentacja drzewa binarnego
// Data: 03.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program show_BT;

// Typ węzłów drzewa

type
  PBTNode = ^BTNode;      // wskazanie węzła

  BTNode  = record        // rekord węzła
    left  : PBTNode;      // lewy syn
    right : PBTNode;      // prawy syn
    data  : integer;      // dane węzła
  end;

// Zmienne globalne

var
  n    : integer; // liczba węzłów
  root : PBTNode; // wskazanie korzenia drzewa
  cr, cl, cp : string; // łańcuchy do znaków ramek

// Procedura inicjuje dane, odczytuje definicję drzewa
// ze standardowego wejścia i tworzy jego strukturę w
// pamięci. Na wyjściu w zmiennej root zostaje umieszczony
// adres korzenia drzewa
//--------------------------------------------------------
procedure readBT;
var
  vp : array of PBTNode; // tablica wskaźników
  i, d, l, r : integer;
begin
  read ( n );            // odczytujemy liczbę węzłów drzewa binarnego

  SetLength ( vp, n );   // tworzymy tablicę dynamiczną wskaźników

  for i := 0 to n - 1 do
    new ( vp [ i ] );    // tworzymy dynamicznie węzeł

  for i := 0 to n - 1 do
  begin
    read ( d, l, r );    // odczytujemy dane węzła i numery synów

    vp [ i]^.data  := d; // wprowadzamy do węzła dane

    if l > 0 then vp [ i]^.left  := vp [ l ]  // ustawiamy lewego syna
    else          vp [ i]^.left  := nil;   // jeśli istnieje

    if r > 0 then vp [ i]^.right := vp [ r ]  // ustawiamy prawego syna
    else          vp [ i]^.right := nil;   // jeśli istnieje
  end;

  root := vp [ 0 ];         // zapamiętujemy korzeń drzewa

  SetLength ( vp, 0 );      // usuwamy tablicę wskaźników
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease ( v : PBTNode );
begin
  if v <> nil then
  begin
    DFSRelease ( v^.left );  // usuwamy lewe poddrzewo
    DFSRelease ( v^.right ); // usuwamy prawe poddrzewo
    dispose ( v );           // usuwamy sam węzeł
  end;
end;

// Procedura wypisuje drzewo
//--------------------------
procedure printBT ( sp, sn : string; v : PBTNode );
var
  s : string;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then s [ length ( s ) - 1 ] := ' ';
    printBT ( s + cp, cr, v^.right );

    s := Copy ( sp, 1, length ( sp ) - 2 );
    writeln ( s, sn, v^.data );

    s := sp;
    if sn = cl then s [ length ( s ) - 1 ] := ' ';
    printBT ( s + cp, cl, v^.left );
  end;
end;

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

begin

  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  readBT;              // odczytujemy drzewo
  printBT ( '', '', root ); // wyświetlamy drzewo
  DFSRelease ( root );    // usuwamy drzewo z pamięci
end.
C++
// Prezentacja drzewa binarnego
// Data: 03.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>

using namespace std;

// Typ węzłów drzewa

struct BTNode
{
  BTNode * left;      // lewy syn
  BTNode * right;     // prawy syn
  int data;           // dane węzła
};

// Zmienne globalne

int n;                // liczba węzłów
BTNode * root;        // wskazanie korzenia drzewa
string cr, cl, cp;    // łańcuchy do ramek

// Procedura inicjuje dane, odczytuje definicję drzewa
// ze standardowego wejścia i tworzy jego strukturę w
// pamięci. Na wyjściu w zmiennej root zostaje umieszczony
// adres korzenia drzewa
//--------------------------------------------------------
void readBT( )
{
  BTNode ** vp;          // tablica wskaźników
  int i, d, l, r;

  cin >> n;              // odczytujemy liczbę węzłów drzewa binarnego

  vp = new BTNode * [ n ]; // tworzymy tablicę dynamiczną wskaźników

  for( i = 0; i < n; i++ )
    vp [ i ] = new BTNode; // tworzymy dynamicznie węzeł

  for( i = 0; i < n; i++ )
  {
    cin >> d >> l >> r;    // odczytujemy dane węzła i numery synów

    vp [ i ] ->data = d;   // wprowadzamy do węzła dane

    if( l ) vp [ i ] ->left = vp [ l ]; // ustawiamy lewego syna
    else  vp [ i ] ->left = NULL; // jeśli istnieje

    if( r ) vp [ i ] ->right = vp [ r ]; // ustawiamy prawego syna
    else  vp [ i ] ->right = NULL; // jeśli istnieje
  }

  root = vp [ 0 ];         // zapamiętujemy korzeń drzewa

  delete [ ] vp;           // usuwamy tablicę wskaźników

}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease ( BTNode * v )
{
  if( v )
  {
    DFSRelease ( v->left );  // usuwamy lewe poddrzewo
    DFSRelease ( v->right ); // usuwamy prawe poddrzewo
    delete v;                // usuwamy sam węzeł
  }
}

// Procedura wypisuje drzewo
//--------------------------
void printBT ( string sp, string sn, BTNode * v )
{
  string s;

  if( v )
  {
    s = sp;
    if( sn == cr ) s [ s.length( ) - 2 ] = ' ';
    printBT ( s + cp, cr, v->right );

    s = s.substr ( 0, sp.length( ) - 2 );
    cout << s << sn << v->data << endl;

    s = sp;
    if( sn == cl ) s [ s.length( ) - 2 ] = ' ';
    printBT ( s + cp, cl, v->left );
  }
}

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

int main( )
{
  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr [ 0 ] = 218; cr [ 1 ] = 196;
  cl [ 0 ] = 192; cl [ 1 ] = 196;
  cp [ 0 ] = 179;

  readBT( );            // odczytujemy drzewo
  printBT ( "", "", root ); // wyświetlamy drzewo
  DFSRelease ( root );  // usuwamy drzewo z pamięci

  return 0;
}
Basic
' Prezentacja drzewa binarnego
' Data: 03.02.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa

Type BTNode
  left As BTNode Ptr
  right As BTNode Ptr
  data As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n           ' liczba węzłów
Dim Shared As BTNode Ptr root  ' wskazanie korzenia drzewa
Dim Shared As String * 2 cr, cl, cp ' łańcuchy do ramek

' Procedura inicjuje dane, odczytuje definicję drzewa
' ze standardowego wejścia i tworzy jego strukturę w
' pamięci. Na wyjściu w zmiennej root zostaje umieszczony
' adres korzenia drzewa
'--------------------------------------------------------
Sub readBT( )

  Dim As BTNode Ptr Ptr vp  ' tablica wskaźników
  Dim As Integer i, d, l, r

  Open Cons For Input As #1
  
  Input #1, n               ' odczytujemy liczbę węzłów drzewa binarnego

  vp = new BTNode Ptr [ n ] ' tworzymy tablicę dynamiczną wskaźników

  For i = 0 To n - 1
    vp [ i ] = new BTNode   ' tworzymy dynamicznie węzeł
  Next

  For i = 0 To n - 1
    Input #1, d, l, r       ' odczytujemy trójkę liczb

    vp [ i ] ->data = d     ' wprowadzamy do węzła dane

    ' ustawiamy lewego syna, jeśli istnieje
    
    If l > 0 Then
    	vp [ i ] ->left = vp [ l ] 
    Else
    	vp [ i ] ->Left = 0
    End If

    ' ustawiamy prawego syna, jeśli istnieje
    
    If r > 0 Then
    	vp [ i ] ->right = vp [ r ] 
    Else
    	vp [ i ] ->Right = 0
    End If
  Next
  
  Close #1

  root = vp [ 0 ]         ' zapamiętujemy korzeń drzewa

  delete [ ] vp           ' usuwamy tablicę wskaźników
  
End Sub

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease ( v As BTNode Ptr )
  If v Then
    DFSRelease ( v->left )  ' usuwamy lewe poddrzewo
    DFSRelease ( v->right ) ' usuwamy prawe poddrzewo
    Delete v                ' usuwamy sam węzeł
  End If
End Sub

' Procedura wypisuje drzewo
'--------------------------
Sub printBT ( sp As String, sn As String, v As BTNode Ptr )

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then Mid ( s, Len ( s ) - 1, 1 ) = " "
    printBT ( s + cp, cr, v->right )

    s = Mid ( s, 1, Len ( sp ) - 2 )
    Print Using "&&&";s;sn;v->Data

    s = sp
    If sn = cl Then Mid ( s, Len ( s ) - 1, 1 ) = " "
    printBT ( s + cp, cl, v->Left )
  End If
End Sub

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

' ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr ( 218 ) + Chr ( 196 )
cl = Chr ( 192 ) + Chr ( 196 )
cp = Chr ( 179 ) + " "

readBT( )            ' odczytujemy drzewo
printBT ( "", "", root ) ' wyświetlamy drzewo
DFSRelease ( root )    ' usuwamy drzewo z pamięci

End
Wynik:
    ┌─2
  ┌─1
┌─7
│ │ ┌─0
│ └─9
5
│ ┌─8
│ │ └─3
└─2
  │ ┌─5
  └─3
    └─6
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.