Prezentacja drzew binarnych


Tematy pokrewne
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych

Problem

Przedstawić w oknie konsoli strukturę drzewa binarnego.



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

 


    ┌─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
Elementy 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: ssp ; 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: ssp[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: ssp ; 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.

Program

Ważne:

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.
 
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
 
Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe